Cache Trade-offs and a Constant-Time Least-Recently-Used Cache

This round opened with a short conversation about the trade-offs of caching and later asked you to design a least-recently-used (LRU) cache. Work through both parts. ### Clarifying Questions - Is the cache local to one process, or shared by several service instances? - What is behind the cache (a database, a remote service, an expensive computation), and how stale may a cached value be? - Roughly how does the working set compare with the memory available for the cache? ### Part 1 — Cache Trade-offs Discuss the main trade-offs you weigh when deciding whether and how to put a cache in front of a slower data source. This was a brief discussion rather than a full design, so concentrate on the decisions an interviewer is most likely to probe: what to cache, how large the cache should be, which entries to evict, and how to keep cached data acceptably fresh. ```hint Tie each choice to a cost For every caching decision, say what it buys (lower latency, less load on the source) and what it costs (memory, staleness, operational complexity) instead of listing policies. ``` #### What This Part Should Cover - Benefits against costs: hit rate, latency, memory, and load on the backing store. - Freshness and consistency: expiry or invalidation, and how writes interact with the cache. - Eviction policy choice, including workloads where LRU performs poorly. ### Part 2 — Design an LRU Cache Implement a cache with a fixed positive capacity that supports `get(key)` and `put(key, value)`, both in O(1) average time. - `get(key)` returns the value stored for `key`, or reports a miss if the key is absent. A successful `get` counts as a use of that key. - `put(key, value)` inserts a new key or updates an existing one, and counts as a use of that key. - When inserting a new key would exceed the capacity, evict the least recently used key first. ```hint Two questions per operation Every operation must answer "where is this key?" and "how do I make it the most recently used?" in constant time. Choose a structure for each question and keep them consistent. ``` #### Clarifying Questions for this Part - What should `get` return on a miss: a sentinel value, `None`, or an exception? - Is capacity counted in entries or in bytes? - Must the cache be safe for concurrent callers? #### What This Part Should Cover - Structures that give constant-time lookup and constant-time recency updates, and the invariant between them. - Correct `get` and `put` sequencing, including updating an existing key and eviction at capacity. - Edge cases such as capacity 1, repeated `put` calls for one key, and `get` on a missing key. ### What a Strong Answer Covers - A clear link between the trade-off discussion and the implementation: when LRU is the right policy and what it costs. - Correct complexity analysis, including average-case hashing and per-entry memory overhead. - A walkthrough or tests that exercise eviction order and updates. - Awareness of production concerns such as concurrency, expiry, and memory accounting. ### Follow-up Questions 1. How would you make this cache thread-safe, and where would lock contention appear? 2. How would you add a per-entry time-to-live without scanning every entry? 3. What access pattern makes LRU perform badly, and which alternative policy would you choose for it?