LC 146 - LRU Cache

Question

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // cache is {1=1} lRUCache.put(2, 2); // cache is {1=1, 2=2} lRUCache.get(1); // return 1 lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3} lRUCache.get(2); // returns -1 (not found) lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3} lRUCache.get(1); // return -1 (not found) lRUCache.get(3); // return 3 lRUCache.get(4); // return 4

Constraints:

• 1 <= capacity <= 3000
• 0 <= key <= 104
• 0 <= value <= 105
• At most 2 * 105 calls will be made to get and put.

Links

Question here and solution here

Solution

concept

The main idea is to use a linked list (double linked) to keep track of least used node and most used node: dummy node (left) <-> LRU <-> ... <-> MRU <-> dummy node (right) In addition, we have a hashmap to map key -> node

1. whenever we get a key, we will remove this node from the linked list and re-add to the MRU position
2. whenever we put in a key, we will also remove it (if it exist) and re-add into the MRU position.
   1. even the cache exceed capacity, we will remove the node at LRU position.

code

class ListNode():
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:

    def __init__(self, capacity: int):
        self.cache = {} # key -> nodes, i.e. the val act as pointer
        self.capacity = capacity
        # 2 dummy node to indicate least used side (left) and most used side
        # self.left.next is the least used node
        # self.right.prev is the most used node
        self.left = ListNode(0,0)
        self.right = ListNode(0,0)
        # connect them first
        self.left.next = self.right
        self.right.prev = self.left
    
    def remove(self, node):
        """
        helper func
        remove node from the linked list
        """
        prev = node.prev 
        nxt = node.next

        prev.next = nxt
        nxt.prev = prev

    def insert_right(self, node):
        """
        helper func
        insert the node from at the right (making it the most recent used)
        """
        prev = self.right.prev
        nxt = self.right

        prev.next = node
        node.prev = prev
        node.next = nxt
        nxt.prev = node


    def get(self, key: int) -> int:
        if key in self.cache:
            # move this node to the most recent used end
            self.remove(self.cache[key])
            self.insert_right(self.cache[key])
            return self.cache[key].val
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.remove(self.cache[key]) # instead of updating, just remove first and we re-create and re-add
        self.cache[key] = ListNode(key, value) # create if new, recreate if old anyway
        self.insert_right(self.cache[key]) # add to the most used end
        # remove LRU if capacity is exceeded
        if len(self.cache) > self.capacity:
            lru = self.left.next
            self.remove(lru)
            del self.cache[lru.key]

Complexity

time: $O(1)$
space: $O(n)$