📖 Book · coding problems · high
🧩 LRU Cache, end to end
Design an O(1) LRU cache — from why it's hard to a hand-rolled implementation you can run.
Design an LRU cache with O(1) get and put — the canonical interview question — built from first principles. Why a single container can't do it, the hash-map-plus-doubly-linked-list design, two complete runnable implementations (std::list and a hand-rolled sentinel list), complexity and the sync gotchas, plus thread-safety, LFU and TTL follow-ups.
7 chapters▶ runnable code✦ in-depth animation
▶ See it animated:LRU Cache: Hash Map + Doubly-Linked List →
What this book covers
- 01The problem, and why it's THE cache question
- 02Why the obvious approaches don't make it
- 03The design: hash map + doubly linked list
- 04Full implementation with the STL — run it
- 05From scratch — no std::list (what they often want)
- 06Complexity, edge cases & the gotchas
- 07Follow-ups: thread safety, LFU, TTL
Read it in full — runnable C++ + step-through animations
Every chapter of LRU Cache, end to end ships complete, editable code you compile and run in the browser, plus the same in-depth animations as the lessons.