TL;DR: Combine a hashmap (key to node, O(1) lookup) with a doubly linked list ordered by recency (move-to-front on access, evict from the tail). Both get and put are O(1). For production use, guard it with a lock for thread safety and store an expiry timestamp per entry for TTL, checking it on read.
How to approach it. Lead with the hard constraint: both get and put must be O(1), which immediately kills any list scan for recency. Name the structure that hits it (hashmap plus doubly linked list) before you write a line. Mention OrderedDict as the idiomatic Python shortcut, but make clear you know the pointer machinery underneath.
A strong answer. The move is to pair two structures. A hashmap gives O(1) key lookup. A doubly linked list orders entries by recency, so you move a node to the front on access and evict from the tail, both O(1). The dict points straight at the node, so you never walk the list to find anything. Python's OrderedDict is exactly this under the hood:
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.d = OrderedDict() # key -> value, ordered by recency
def get(self, key):
if key not in self.d:
return -1
self.d.move_to_end(key) # mark most-recently used
return self.d[key]
def put(self, key, value):
if key in self.d:
self.d.move_to_end(key)
self.d[key] = value
if len(self.d) > self.cap:
self.d.popitem(last=False) # evict least-recently used (front)
Both operations are O(1): the dict gives O(1) lookup, and move_to_end/popitem are O(1) on the linked structure. Narrate why the linked list earns its keep: a plain dict finds a key in O(1) but finding the least-recently-used to evict would be O(n) without the recency ordering baked into the list.
For the usual follow-ups: wrap each public method in a threading.Lock for thread safety, and for TTL store (value, expires_at) and treat an entry as a miss (and delete it) if time.monotonic() > expires_at on read.
The recency invariant in one picture, where the head is most-recently-used and the tail is the eviction target:
| Operation | Without linked list | With hashmap + DLL |
|---|---|---|
get(k) | O(1) lookup, O(n) recency update | O(1) |
put(k,v) | O(n) to find LRU victim | O(1) |
| Evict LRU | O(n) scan | O(1) pop tail |
Key takeaways
- The hashmap buys O(1) lookup; the doubly linked list buys O(1) recency reordering and eviction. Neither alone is enough.
- A read counts as a use:
getmust move the node to the front, or your LRU degrades to a random-eviction cache. - TTL is a per-entry expiry checked lazily on read; thread safety is a lock per method, sharded by key hash under contention.
What interviewers probe next.
- "Implement it without OrderedDict." A dict mapping key to a node in a hand-rolled doubly linked list with sentinel head/tail; show the unlink/insert-at-front pointer surgery.
- "Make it thread-safe." A lock around get/put; for high contention, shard by key hash so locks are independent.
- "Add TTL." Store expiry per entry, lazily evict on access; optionally a background sweep for memory.
- "LRU vs LFU vs ARC?" LRU evicts by recency; LFU by frequency (better for skewed access but heavier); ARC adapts between them. Choose by access pattern.
Common mistakes.
- Using a list/array for recency, making eviction O(n).
- Forgetting to update recency on
get(a read must count as a use). - Off-by-one on capacity (evicting before or after insert inconsistently).
- Claiming thread safety without a lock, then racing on the shared structure.