LRU Cache with TTL: Solution Walkthrough
High Priority20 min readUpdated November 11, 2026
The LRU Cache problem starts with an implementation most engineers have written at least once: a dictionary and a doubly linked list that together evict the least recently used entry when the cache reaches capacity. This version adds a time-to-live for each entry, and later a get_or_load method that many threads call at once.
The round has four phases:
- Phase 0: Understand the code. Fill in three blanks and answer three open questions about the existing implementation.
- Phase 1: Fix a bug. Prices cached for 60 seconds still show last week's values for the busiest products.
- Phase 2: Add a feature. Implement per-key
ttl,peek,deleteandstatswhile following seven rules. - Phase 3: Make it thread-safe and fast. Introduce one lock, a heap of expiry times, and a single-flight
get_or_loadwhere callers requesting the same key share one load, without holding the lock while the loader runs.
The main challenge is that expiration affects almost every part of the cache. Reading an entry updates its recency but doesn't extend its lifetime. Expired entries must give up their slots before any live entry is evicted, and they don't count as evictions. And if someone writes to a key while a load for it is still running, the load must not overwrite that newer value.