Design an LRU cache with O(1) get and put
What interviewers are testing
LRU is the most common design question in coding rounds because it forces you to combine two data structures instead of pattern-matching one. Interviewers watch whether you decompose the operations first - lookup, unlink, move to front, evict - and whether your node management makes get and put O(1) without leaking stale links. It also reveals production awareness: the same design appears in Redis and database buffer pools, where approximation and concurrency change the answer.
Mental model
Two independent requirements must hold at once: find any key node in O(1) with a hash map, and reorder recency in O(1) with a doubly linked list. The map stores key to node, so you never search a list. The list stores recency order with the most recently used node at the head and the least recently used at the tail; a get unlinks its node and re-inserts it at the head, and a put at capacity evicts the tail. Sentinels remove null checks at both ends.
Step-by-step solution
Step 1 of 5
One structure cannot do both
Start by ruling out the obvious single structures. An array gives O(1) access by index, but a cache is keyed by arbitrary keys, so a get first has to find the key with a linear scan; even after that, removing an item from the middle shifts every later element, which is O(n) again. A plain object or dictionary gives O(1) keyed access, but it offers no supported move-to-front operation: deleting and re-adding a key is engine-dependent, integer-like keys iterate in numeric order rather than recency order, and nothing in the contract promises that iteration reflects access time. The animation shows each candidate operation and its cost: indexOf to locate, splice to unlink, unshift to promote. The pattern that emerges is the hint: one structure is good at lookup by key, another at reordering by position. Use one for each job and let node references connect them.
Animation — One structure cannot do both
// Naive: recency tracked in an array, MRU at index 0.const order = ['c', 'b', 'a']; // most recent firstfunction get(key) { const i = order.indexOf(key); // O(n) scan if (i === -1) return -1; order.splice(i, 1); // O(n) shift left order.unshift(key); // O(n) shift right return store.get(key);}Variables
get('a') scans the array from the front; the key sits at index 2.
Edge cases & traps
- Capacity 0: put must be a no-op (or evict immediately) instead of inserting a node and then evicting it; decide the contract and document it.
- Capacity 1: an insert-then-evict order would remove the node just added - evict before inserting so the new node survives.
- Updating an existing key must not count as a new entry or trigger eviction, but it must still refresh recency by moving the node to the front.
- get on a missing key returns -1 and must leave the order untouched, or a read storm reshapes the cache and evicts hot data.
- Languages without GC: an unlinked node can still be reachable from elsewhere, so clear prev/next and erase the map entry to avoid dangling pointers and leaks.