#1Low-Level DesignSep 22, 2026
Design an LRU Cache
Starts from a classic interview problem and keeps changing the requirements until the textbook answer stops being the right one.
20 attendees
- Designing from operations first: what must be fast decides the data structure, not the other way round.
- Why O(1) is not the end: rebuilding the hash-map-plus-linked-list solution as a contiguous array with index links and a free list, because Big-O counts operations, not cache misses.
- Capacity in bytes instead of entries, and TTL expiry, where one cache has to keep two orderings at once.
- Concurrency: get() is logically a read but writes to the recency list, so 64 threads contend on every hit.
- Cache pollution from crawlers, and fixing it with 2Q / Segmented LRU so new keys must earn a place.
- Scaling out: key ownership across servers, adding and removing nodes, and surviving a crashed shard.