Object-oriented design of a fixed-capacity LRU cache with O(1) get and put

In an object-oriented design round, design and implement a least-recently-used (LRU) cache with a fixed capacity: - `get(key)` returns the value stored under `key` and marks the key as the most recently used. If the key is not in the cache, it reports a miss. - `put(key, value)` inserts the key, or updates its value if it is already present, and marks it as the most recently used. If an insert makes the cache exceed its capacity, the least recently used key is evicted. Present the design the way an object-oriented round expects: the classes, what each one is responsible for, and their public interfaces, then implement them. Both operations are expected to run in constant average time, which is the usual expectation for this exercise; confirm it with the interviewer. ```hint One structure is not enough A hash map finds a key in constant time but knows nothing about recency. Think about what second structure can move any entry to the most-recent end, and remove the entry at the least-recent end, in constant time. ``` ```hint Name the responsibilities Separate what the cache promises to its callers from how it tracks recency, and decide which class owns each piece of state. ``` ### Constraints and Clarifications - The capacity is fixed when the cache is created. - One process, data in memory. - Keys are hashable; values are arbitrary objects. ### Clarifying Questions - How should `get` report a miss: a sentinel such as `-1`, `None`, or an exception? Can a stored value itself be `None`? - Does updating an existing key count as a use, and can an update ever cause an eviction? - What should a capacity of zero or less mean: an error, or a cache that stores nothing? - Will several threads share the cache? - May I use a built-in ordered map, or should the recency structure be written by hand? ### What a Strong Answer Covers - A clear class decomposition: the public cache interface, the recency structure and its nodes, with internals encapsulated - Correct constant-time `get` and `put`, including updates of existing keys and eviction at capacity - Edge cases: misses, capacity one, repeated puts of the same key, and invalid capacities - A short test trace that exercises the eviction order - Awareness of extension points such as other eviction policies and thread safety, without over-engineering the first version ### Follow-up Questions - Make the cache safe for many threads. Why does a read-write lock not help much here, and how would sharding change the guarantees? - Switch the eviction policy to least-frequently-used without changing the callers. What in your design changes? - Bound the cache by the total size of its values instead of the number of entries. - Add an expiry time per entry. How does it interact with the recency order?