LRU Cache
Hash map for O(1) lookup plus a doubly linked list for recency order. Least-recently-used evicts first.
What is an LRU cache?
A fixed-size cache that evicts the least recently used item when it is full. It keeps hot data fast and drops cold data.
Where you will see it
Real systems that use this exact idea. Tap a card to open it.
Common traps
The mistakes interviewers watch for. Guess the fix, then reveal it.
FixRemoving an arbitrary node needs its prev pointer - a singly list forces an O(n) search. Doubly linked is mandatory for O(1).
Fixput on an existing key must UPDATE, not evict-then-insert. Check existence first, then promote.
FixThe list loses the node but the map still points at it - a ghost entry that corrupts future gets. Evict from BOTH structures.
Interview prep
Questions you could be asked, with the depth an interviewer wants to hear.
Combine a hash map for O(1) lookup with a doubly linked list for O(1) recency ordering. On a hit, move the node to the head. On a miss, return -1. On put over capacity, evict the tail.
get/put O(1)
Real worldThis is one of the most-asked interview questions, and it appears in real caches and OS page replacement.
DeeperThe doubly linked list matters: removing a node in O(1) needs both previous and next pointers.