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

  1. HLD first: where an LRU actually lives, and what the interviewer is really asking
  2. The data structure: why a hash map AND a doubly linked list
  3. Pointer moves step by step: get, put-new, put-evict
  4. Full TypeScript implementation with generics
  5. The JS Map shortcut: why it works and why interviewers may reject it
  6. Testing an LRU: examples, invariants and a differential test
  7. Follow-up 1: capacity by bytes (weight), and the real memory cost per entry
  8. Follow-up 2: TTL with lazy and active expiry
  9. Follow-up 3: thread safety in Java, async safety in Node, and multiple pods
  10. Follow-up 4: LFU in O(1) with frequency buckets and a min-frequency pointer
  11. Follow-up 5: scan resistance with LRU-K, 2Q, SLRU and W-TinyLFU
  12. Follow-up 6: pluggable eviction via Strategy, plus stats and hit ratio
  13. Follow-up 7: write-through and write-back hooks, and eviction listeners that persist
  14. 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