LRU Cache
Design a cache with a fixed capacity supporting get(key) and put(key, value) in constant time. When inserting into a full cache, evict the entry that was accessed least recently (both gets and puts count as access).
- 1 ≤ capacity ≤ 3000
- 0 ≤ key, value ≤ 10^5
- At most 2 · 10^5 operations
- O(1) lookup and O(1) reordering by recency
- Need to move an arbitrary node to the front and remove from the back
- Hash map to nodes + doubly linked list
Pointer surgery problems are about maintaining prev, curr, and next so no node becomes unreachable, and a dummy head removes the special case of modifying the first node. Doubly linked lists paired with a hash map give O(1) move-to-front, which is the basis of LRU caches.
Combine a hash map from key to node with a doubly linked list ordered by recency, with sentinel head and tail nodes. get looks up the node, unlinks it and reinserts it right after the head. put updates and moves an existing node, or creates one at the front; if the size exceeds capacity, unlink the node before the tail and delete its key from the map. Every step is a constant number of pointer changes.
- Languages with insertion-ordered maps (Python
OrderedDict, JSMap) let you delete and reinsert a key to move it to the end, which hides the list. An LFU cache needs frequency buckets on top of this.