Build a Fixed-Capacity Least-Recently-Used Cache with Constant-Time Get and Put

Implement a least-recently-used (LRU) cache that holds at most `capacity` entries. It supports two operations: - `get(key)`: return the value stored for `key` and mark `key` as the most recently used entry. - `put(key, value)`: insert `key` with `value`, or update the value if `key` is already present, and mark `key` as the most recently used entry. If the cache now holds more than `capacity` entries, evict the least recently used one. Both operations should run in constant average time, independent of how many entries the cache holds. The round was mostly conversation rather than typing: the problem was taken apart in detail from the very beginning, and comparatively little code was written. Expect to explain what "least recently used" means operationally, why each data structure is there, and how every operation keeps them consistent, before and while you code. ```text capacity = 2 put(1, "a") cache holds 1 put(2, "b") cache holds 1, 2 get(1) -> "a" 1 is now the most recently used put(3, "c") evicts 2, the least recently used get(2) -> missing ``` ```hint Where the time goes Try a hash map on its own, then an ordered list on its own, and name the operation that stops being constant time in each. The fix has to let the two structures reach each other directly. ``` ```hint Unlink in place Promoting an entry from the middle of the recency order must not require a search. Ask what each element of the order needs to know to remove itself, and how to avoid special cases when it is first or last. ``` ### Clarifying Questions - What should `get` return for a key that is not in the cache: a sentinel value, `None`, or an error? - Does updating the value of an existing key count as a use, so that it becomes the most recently used entry? - Is `capacity` fixed at construction, and what should happen if it is zero or negative? - Will the cache be called from several threads at once? - Are keys arbitrary hashable values, and is capacity counted in entries rather than bytes? ### What a Strong Answer Covers - Pins down the semantics before coding: what counts as a use, the missing-key result, updates of existing keys, and invalid capacities - Explains from first principles why neither a hash map nor an ordered list alone meets the time bound, and arrives at a combined structure with a stated invariant that links the two - Correct `get`, `put` and eviction, including updating an existing key without creating a duplicate and removing an evicted entry from both structures - Time per operation and memory overhead per entry, including why the bound is average-case rather than worst-case - A trace and test cases: capacity 1, repeated puts of one key, a get after eviction, an update while the cache is full - Clear, structured explanations when every step is questioned, with code that matches what was described ### Follow-up Questions - Make the cache safe for many concurrent threads. Why does `get` need more than a read lock, and how would you reduce contention? - Capacity is now a byte budget and values have different sizes. What changes in `put`? - Add a time-to-live for each entry. How do expired entries interact with least-recently-used eviction? - A workload occasionally reads a large set of keys exactly once, in sequence. What does that do to the hit rate, and how could the eviction policy resist it?