ORIGINAL TECHNICAL PRACTICE
Design a bounded LRU cache
Describe an LRU cache supporting get and put in expected O(1) time. What must remain consistent after every operation?
Written for independent practice. The model answer presents one approach; clarify constraints and explain alternatives.
A REASONED APPROACH
Model answer.
Combine a key-to-node map with a doubly linked list ordered from most to least recently used. The map locates nodes; the list updates recency and identifies the eviction candidate.
Work through it
- A successful get moves the same node to the most-recent end. A miss must not add a phantom entry or change capacity.
- Updating an existing key changes its value and recency without increasing the number of entries. A new key exceeding capacity evicts the least-recent node from both structures.
- Test zero capacity, repeated updates, eviction after a get, and alternating hits and misses. If operations can interleave, protect the compound map/list update rather than just one structure.
Tradeoffs to discuss
- Expected O(1) operations rely on hash-map behavior. LRU has bookkeeping overhead and can perform poorly for scan-heavy workloads compared with frequency-aware policies.
Common pitfalls
- Leaving an evicted node in the map or duplicating a node in the list breaks later operations. Thread-safe individual containers do not make the combined cache atomic.