Designing a Thread-Safe LRU Cache
A low-level design walkthrough of an O(1) LRU cache — a hash map plus a doubly linked list — how eviction works, the locking story, and the full browsable implementation.
Swipe up to your phone's app switcher. The app you used two minutes ago resumes instantly, exactly where you left it. The one from last Tuesday? It restarts from its splash screen. Your phone didn't forget it out of spite — memory filled up, something had to go, and it chose the app you'd gone longest without touching. That eviction policy has a name — Least Recently Used — and building an LRU cache is one of the great low-level design interviews, because it comes in two acts. Act one: make get and put run in O(1). Act two, where senior candidates are made: keep it correct when many threads ha…
What’s inside
Read this one free
Sign in and your first premium article is on us — read Designing a Thread-Safe LRU Cache free.