visual walkthrough
LRU Cache
One of the most-asked design questions at every FAANG company.
The idea
An LRU cache needs two things fast: finding a key, and knowing which entry was used longest ago.
A hash map does the first. A doubly linked list in order of use does the second: move a node to the front when it's used, and evict from the back. The map stores nodes, so a node can be unlinked from the middle without searching.
Complexity
| approach | time | space |
|---|---|---|
| Ordered list, searched | O(n) per op | O(n) |
| Hash map + doubly linked list | O(1) per op | O(capacity) |