The problem
Design a fixed-capacity cache where get(key) and put(key, value) both run in O(1); on overflow evict the least-recently-used entry.
Stuck? Reveal hints one at a time
How to approach it
- 1Build a doubly linked list with sentinel head (MRU side) and tail (LRU side).
- 2get: missing → −1; else unlink the node, re-insert after head, return its value.
- 3put existing: update value, move to front.
- 4put new at capacity: remove the node before tail (LRU) and delete its map entry, then insert the new node at front.
Key insight
Sentinels head/tail mean insert and unlink never branch on "am I at an end" — the whole trick is O(1) recency updates via stored node references.
The solution
Watch out for
- Nodes must store their KEY too — eviction needs it to delete the map entry.
- A get() counts as a "use": forgetting to move the node on reads breaks the LRU order invisibly.