146. LRU Cache

[#hashmap, #linked-list]

## description

## 146. LRU Cache

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:

plain text

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

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

Constraints:

## notes

### Intuition

We need removal from anywhere and insertion at either end to all be O(1). Thus, we can use a hashmap with a doubly-linked list.

### Implementation

In a nutshell, we store list nodes by key in a hashmap as well as keep track of our doubly-linked list with head and tail pointers.

On get, we check if the node exists, if it does, we disconnect (remove) that node from the list and add it to the most-recently used (MRU) end which we can define as the tail. Both of these operations can be done in O(1) time as it is doubly-linked and the node is stored in a hashmap. If the node doesn't exist, simply return -1.

On put, we check if the node exists, it it does, we update the value stored in the node. Then we disconnect (remove) that node from the list and add it to the MRU end. If it does not exist, we create a new node, add it to the hashmap, and then add the node to the MRU end. After this, we check if the length of our hashmap exceeds the capacity (need to evict), if so, we remove the node at the head of the list (LRU end), and delete the node from the hashmap using the key stored in the node.

### Edge-cases

To remove a bunch of edge-cases, we can use sentinel (dummy) nodes at the head and tail so that we don't have to deal with many null pointer checks. This makes removals and insertions quite trivial.

We should also ensure to store the key as well as the value in the list node so that we can easily delete the node from the hashmap on eviction.

–
Time: O(1): Since we use a hashmap to store nodes and a doubly-linked list, node lookup is O(1), removal is O(1), insertion is O(1)
–
Space: O(n): where n is the capacity. At most we store the n nodes as they get evicted when capacity is reached.

### Complexity

## solution

python

from typing import List, Optional

class Node:
    def __init__(
        self,
        key: int,
        val: int,
        next: Optional['Node'] = None,
        prev: Optional['Node'] = None,
    ):
        self.key = key
        self.val = val
        self.next = next
        self.prev = prev


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.nodes: dict[int, Node] = {}
        self.head = Node(-1, -1)
        self.tail = Node(-1, -1)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: Node):
        """Disconnects a node from the list (guranteed it exists)"""
        prev = node.prev
        nxt = node.next
        if prev:
            prev.next = nxt
        if nxt:
            nxt.prev = prev
        node.prev = node.next = None

    def _add_to_mru(self, node: Node):
        """Adds a node to the MRU (tail) end"""
        last = self.tail.prev
        node.prev = last
        node.next = self.tail
        if last:
            last.next = node
        self.tail.prev = node

    def _move_to_mru(self, node: Node):
        """Moves an existing node to the MRU position"""
        self._remove(node)
        self._add_to_mru(node)

    def _evict_lru(self):
        """Evicts the node at the LRU position (head)"""
        lru = self.head.next
        if not lru or lru is self.tail:
            return
        self._remove(lru)
        del self.nodes[lru.key]
        

    def get(self, key: int) -> int:
        if key in self.nodes:
            node = self.nodes[key]
            self._move_to_mru(node)
            return node.val
        return -1
        

    def put(self, key: int, value: int) -> None:
        if key in self.nodes:
            node = self.nodes[key]
            node.val = value
            self._move_to_mru(node)
        else:
            node = Node(key, value)
            self.nodes[key] = node
            self._add_to_mru(node)

        if len(self.nodes) > self.capacity:
            self._evict_lru()


if __name__ == "__main__":
    cache = LRUCache(2)

--EOF--