Implement an LRU Cache, Then Add TTL Expiry and Thread Safety

Implement an in-memory cache with a fixed capacity that evicts the least recently used entry when it is full. Then extend it in two steps: entries that expire after a time-to-live (TTL), and safe use from multiple threads. ### Clarifying Questions - What should `get` return for a missing key, and can a stored value itself be `None`? - Does `put` on an existing key count as a use for recency purposes? - What types are keys and values, and is capacity counted in entries or in bytes? ### Part 1 — LRU cache Implement a class constructed with a positive `capacity` that supports: - `get(key)`: return the value stored for `key` and mark the entry as most recently used, or report a miss. - `put(key, value)`: insert or update the entry and mark it as most recently used. If inserting a new key would exceed `capacity`, first evict the least recently used entry. Both operations should run in O(1) average time. ```hint Two jobs, two structures One structure has to find a key quickly and another has to keep entries in recency order. Consider how to make moving a single entry to the front cost O(1). ``` #### What This Part Should Cover - A structure that supports lookup, move-to-front and eviction in constant time. - Correct recency updates on both `get` and `put`, including an update to an existing key. - Handling of the empty and single-entry cases without special-case bugs. ### Part 2 — Add TTL expiry Extend the cache so that entries expire after a time-to-live. An expired entry must behave as if it were absent. ```hint Expired but still resident An expired entry can still occupy a slot. Think about when it should be removed, and what should happen when the cache is full while some entries have already expired. ``` #### Clarifying Questions for this Part - Is the TTL one value for the whole cache, or can each `put` set its own? - Does the TTL count from the last write only, or does a `get` extend it as well? - When the cache is full, should an expired entry be evicted before a live least recently used one? - Should expired entries be removed lazily on access, by a background task, or both? #### What This Part Should Cover - Where the expiry time is stored and when it is checked. - How expired entries are cleaned up, and how that interacts with capacity-based eviction. - A controllable time source, so expiry can be tested without sleeping. ### Part 3 — Make it thread-safe Make the cache safe to call from many threads at once. ```hint Reads are writes here Look at what a `get` does to the internal structures before deciding which operations need exclusive access. ``` #### What This Part Should Cover - Which operations need mutual exclusion, and why a reader-writer lock gives little benefit here. - Lock scope: what runs inside and outside the critical section, including expiry cleanup. - How the design behaves under contention, and what a more scalable variant gives up. ### What a Strong Answer Covers - Correct O(1) LRU mechanics, with the complexity of every operation restated after each extension. - Explicit decisions for each open semantic question: the miss value, TTL scope, and whether expiry or recency decides eviction. - Extensions layered onto the Part 1 structure rather than a rewrite for each part. - Tests that pin down eviction order, the expiry boundary, and a concurrent smoke test that checks internal consistency. ### Follow-up Questions - How would you split the cache into independently locked segments, and what does that do to the global LRU guarantee? - If loading a missing value is slow, how do you stop many threads from loading the same key at the same time? - How would you bound memory by total bytes instead of entry count? - How would you expose hit rate, eviction and expiry counts without adding lock contention?