Design an LRU cache

Question

Design a fixed-capacity key-value cache (think: instrument metadata in front of a slow reference-data service) supporting:

get(key), return the value, or -1 if absent;
put(key, value), insert or update; if capacity is exceeded, evict the least recently used entry.

Both get and put count as "uses" of the touched key.

c = LRUCache(2)
c.put(1, 1); c.put(2, 2)
c.get(1) -> 1          # 1 is now most recent
c.put(3, 3)            # evicts 2 (least recent)
c.get(2) -> -1

Both operations must run in $O(1)$ .

Accepted Answer

Combine a hash map with a doubly linked list ordered by recency: the map takes you from key to node in O(1); the list supports O(1) unlink (thanks to prev pointers) and O(1) push-to-front. Every access unlinks the touched node and reinserts it at the front; eviction removes the node before the tail sentinel. Sentinels at both ends eliminate all "is this the head/tail?" edge cases. Tracing the example: after get(1), order (most→least recent) is 1, 2; put(3, 3) evicts 2; get(2) returns -1. The node storing its own key is the subtle requirement, eviction discovers the victim via the list, then m…

Design an LRU cache

Your answer

More Coding questions