LRU Cache: Implementation & The Follow-up Ladder
The most-asked LLD question, done properly: where an LRU sits in a real system, the hash map + hand-written doubly linked list with sentinels and its pointer moves, a generic TypeScript implementation and how to test it. Then every rung of the follow-up ladder: weight, TTL, thread safety, O(1) LFU, scan resistance, pluggable policies, stats, listeners, write-back and distribution.
About 140 minutes · 18 exam questions · 14 interview questions · 2 code labs
What you will learn
- HLD first: where an LRU actually lives, and what the interviewer is really asking
- The data structure: why a hash map AND a doubly linked list
- Pointer moves step by step: get, put-new, put-evict
- Full TypeScript implementation with generics
- The JS Map shortcut: why it works and why interviewers may reject it
- Testing an LRU: examples, invariants and a differential test
- Follow-up 1: capacity by bytes (weight), and the real memory cost per entry
- Follow-up 2: TTL with lazy and active expiry
- Follow-up 3: thread safety in Java, async safety in Node, and multiple pods
- Follow-up 4: LFU in O(1) with frequency buckets and a min-frequency pointer
- Follow-up 5: scan resistance with LRU-K, 2Q, SLRU and W-TinyLFU
- Follow-up 6: pluggable eviction via Strategy, plus stats and hit ratio
- Follow-up 7: write-through and write-back hooks, and eviction listeners that persist
- Follow-up 8: distributed LRU, consistent hashing, and how Redis approximates LRU
Previous: Design Patterns & Concurrency for LLD · Next: LLD Case Studies I: Parking Lot, Elevator, BookMyShow & Splitwise