LRU Cache with Fewer Recency Writes and Concurrent Access

Implement a least-recently-used (LRU) cache with a fixed capacity. It supports `get(key)`, which returns the value stored for the key or reports a miss, and `put(key, value)`, which inserts the key or updates its value. Both operations count as a use of the key. When inserting a new key would exceed the capacity, the cache first evicts the least recently used key. After the base implementation, the interviewer discussed two follow-ups: reducing the write traffic that recency tracking causes, and making the cache concurrent. ### Clarifying Questions - What should `get` return on a miss: a sentinel such as `-1`, a null value, or an exception? - What should happen with a capacity of 0? - Are keys and values arbitrary objects, or fixed types such as integers? - Is the cache used by a single thread in the base version? ### Part 1 — Base implementation Implement the cache so that `get` and `put` both run in constant time on average. ```hint Two questions per operation Every operation must find the key's entry quickly and also know which entry is the oldest. Ask whether a single structure can answer both questions in constant time. ``` #### What This Part Should Cover - Data structures that give constant-time lookup, recency update and eviction - Correct handling of updates to existing keys, eviction order and capacity edge cases - Clean code with the complexity of each operation ### Part 2 — Reduce write throughput In the base design, every `get` changes the recency order, so a read-heavy workload turns every read into a write to shared state. How would you reduce those recency writes, and what does each option cost? ```hint How exact must recency be Ask whether the cache must evict exactly the least recently used key, or whether a key that is nearly the least recently used would do. ``` #### What This Part Should Cover - Why recency updates are writes, and where those writes hurt - At least two concrete techniques that cut recency writes, with how each one works - The effect of each technique on eviction accuracy and hit rate ### Part 3 — Make it concurrent Many threads now call `get` and `put` at the same time. Make the cache thread-safe while keeping its throughput high. ```hint Reads are writes too Before reaching for a read-write lock, check whether `get` really leaves the shared state unchanged in your design. ``` ```hint Split the state Think about what you would gain, and what you would lose, if different keys were managed by independent pieces of state. ``` #### Clarifying Questions for this Part - Must eviction follow the exact global LRU order, or is an approximate order acceptable under concurrency? - What is the read-to-write ratio, and roughly how many threads use the cache? #### What This Part Should Cover - The correctness and the bottleneck of a single global lock - A finer-grained scheme, and how it divides keys and capacity - How eviction order changes once the state is split, and when that is acceptable - How the concurrency design combines with the write reduction from Part 2 ### What a Strong Answer Covers - A correct constant-time implementation with its edge cases - A clear explanation of why reads mutate shared state in an exact LRU - Concrete techniques for fewer recency writes, with their accuracy cost - A concurrency design whose locking granularity and eviction semantics are explicit - Trade-offs between exact LRU order, hit rate and throughput ### Follow-up Questions - How would you add a time-to-live per entry on top of LRU eviction? - A scan reads a million keys once each and flushes your hot entries. How would you protect them? - With sixteen shards, one shard ends up holding all the hot keys. What happens, and how would you respond? - How would you measure whether an approximate policy costs hit rate in production?