01 · Why it’s true
A cache keeps recent results in fast memory so repeated requests skip slow work. Because space is limited, it needs a rule for what to evict; least-recently-used (LRU) evicts the item that hasn’t been used for the longest time, betting that recent items are most likely to be used again.
The classic implementation uses two structures together: a hash map for O(1) lookup by key, and a doubly linked list ordered by use. On each access the item moves to the front; when full, the item at the back is evicted. Both operations are O(1).
02 · Picture it
03 · In the interview
- A very common coding question: implement an LRU cache with O(1) get and put.
- Caching in design: hit rate, TTLs, and what happens when the cache is empty or fails.
- Explaining the risk of a cold cache sending all traffic to the backend at once.
04 · Practice question
“Implement an LRU cache with O(1) get and put. Then: what happens to the backend when this cache restarts?”
A strong answer covers
- Hash map from key to node, plus a doubly linked list with the most recent at the head.
- get: look up, move the node to the head, return it. put: insert or update at the head; if over capacity, remove the tail and delete it from the map.
- Handle the edge cases: updating an existing key, capacity 1, and thread safety (a lock around both structures).
- After a restart the cache is empty, so every request goes to the backend; warm it up gradually or rate-limit misses to avoid overloading it.