Design an LRU cache with constant-time operations

A strong answer

An LRU cache needs three operations in O(1): look up a key, mark an entry as just used, and evict the entry used longest ago.

I would combine two structures. A doubly linked list keeps entries ordered by recency: most recent next to a head sentinel, least recent next to a tail sentinel. A hash map maps each key to its list node, so any entry can be reached without a search.

• get(key): look up the node; if it exists, unlink it and reinsert it after head, then return its value. Unlinking is O(1) because the node knows both neighbors.
• put(key, value): if the key exists, update the value and move the node to the front. Otherwise create a node, insert it after head and add it to the map. If the size now exceeds capacity, take the node before tail, unlink it and delete its key from the map.

Every step is a constant number of pointer updates and map operations, so both operations are O(1) on average. Sentinels remove the null checks for an empty list or a one-element list. Each node stores its key so that eviction can delete it from the map. Edge cases to state: whether put on an existing key counts as a use (usually yes), and capacity 0.

For concurrency, one lock around both structures is correct but becomes a bottleneck, because every get writes to the list. Real caches shard the key space into independent LRUs, or approximate LRU: Redis samples a few keys and evicts the oldest among them, and some caches use the CLOCK algorithm, which sets a "recently used" bit instead of moving nodes.

What the interviewer is listening for

• Why neither structure alone is enough.
• O(1) unlink because the list is doubly linked, and why nodes keep their keys.
• Sentinels and clean edge-case handling.
• Awareness of concurrency and approximate LRU in real systems.

Common mistakes

• Using a singly linked list, which needs O(n) to find a predecessor.
• Forgetting to remove the evicted key from the map.
• Updating an existing key without moving it to the front.