deepSWE.io

LRU Cache

Hash MapLinked List

MediumLeetCode #146

25-30 min

Problem Statement

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

Implement the LRUCache class:

LRUCache(int capacity) Initializes 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.

Example

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);       // returns 1, cache is {2=2, 1=1}
lruCache.put(3, 3);    // LRU key 2 was evicted, cache is {1=1, 3=3}
lruCache.get(2);       // returns -1 (not found)
lruCache.put(4, 4);    // LRU key 1 was evicted, cache is {3=3, 4=4}
lruCache.get(1);       // returns -1 (not found)
lruCache.get(3);       // returns 3, cache is {4=4, 3=3}
lruCache.get(4);       // returns 4, cache is {3=3, 4=4}

Constraints

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 10^5
At most 2 * 10^5 calls will be made to get and put.

Solution

Approach: Hash Map + Doubly Linked List

The most efficient way to implement an LRU Cache is by combining a hash map and a doubly linked list. The hash map provides O(1) time complexity for get operations, while the doubly linked list maintains the order of recently used items, allowing for O(1) insertions and deletions.

Insertion

Empty

MRU

Empty

LRU

Deletion (Eviction)

Empty

MRU

Empty

LRU

Update (On Get)

Empty

MRU

Empty

LRU

Algorithm Steps

Use a hash map to store keys and their corresponding nodes in the linked list.
Use a doubly linked list to keep track of the most recently used items. The most recently used item will be at the tail, and the least recently used at the head.
When an item is accessed (get or put), move it to the tail of the list.
When the cache is full and a new item is added, remove the item at the head of the list (the least recently used).

Hash Map + Doubly Linked List Solution


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

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}  # map key to node

        # Left=LRU, Right=MRU
        self.left, self.right = Node(0, 0), Node(0, 0)
        self.left.next, self.right.prev = self.right, self.left

    # remove node from list
    def remove(self, node):
        prev, nxt = node.prev, node.next
        prev.next, nxt.prev = nxt, prev

    # insert node at right
    def insert(self, node):
        prev, nxt = self.right.prev, self.right
        prev.next = nxt.prev = node
        node.next, node.prev = nxt, prev

    def get(self, key: int) -> int:
        if key in self.cache:
            self.remove(self.cache[key])
            self.insert(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])
        self.cache[key] = Node(key, value)
        self.insert(self.cache[key])

        if len(self.cache) > self.cap:
            # remove from the list and delete the LRU from the hashmap
            lru = self.left.next
            self.remove(lru)
            del self.cache[lru.key]