map / coding / lru-cache

Coding · principle 6 of 6

LRU cache

A hash map plus a doubly linked list gives O(1) lookup and O(1) eviction of the least recently used entry.

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

1get(key)2Hash maplookupkey → list node,O(1)3Move to frontmost recentlyused, O(1)4Full on put?evict from theback, O(1)Two structures together: a hash map finds the node, a doubly linked list keeps the orderof use.
1get(key)2Hash map lookupkey → list node, O(1)3Move to frontmost recently used, O(1)4Full on put?evict from the back, O(1)Two structures together: a hash mapfinds the node, a doubly linked listkeeps the order of use.
LRU = hash map for lookup + linked list for recency.

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

  1. Hash map from key to node, plus a doubly linked list with the most recent at the head.
  2. 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.
  3. Handle the edge cases: updating an existing key, capacity 1, and thread safety (a lock around both structures).
  4. 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.