Implement an O(1) LRU Cache, Then Extend It into an LFU Cache

Implement an in-memory key-value cache with a fixed capacity that evicts the least recently used entry when it is full, then extend it so that it evicts the least frequently used entry instead. Both `get` and `put` must run in O(1) time, and you are expected to explain your data structure choices, the edge cases and the complexity. ### Clarifying Questions - What should `get` return for a missing key: a sentinel such as `-1`, `None`, or an exception? - Does a `put` on a key that is already cached count as a use of that key? - What should happen when the capacity is `0`? - May you use a built-in ordered map, or should you build the underlying structure yourself? - Must the cache be safe for concurrent use? ### Part 1 — Least recently used cache Implement `LRUCache(capacity)` with two methods: - `get(key)` returns the value stored for `key`, or the agreed miss value, and makes `key` the most recently used entry. - `put(key, value)` inserts or updates the entry and makes it the most recently used. If inserting a new key would exceed the capacity, the least recently used entry is evicted first. Both operations must be O(1). ```hint Check every step List the steps that `get` and `put` perform (find the entry, mark it as most recent, remove the oldest) and make sure each one is constant time in your design, not only the lookup. ``` #### What This Part Should Cover - A structure that supports constant-time lookup, recency update and eviction, with the reason for each piece - Correct behaviour for misses, updates of existing keys and evictions - Edge cases such as capacity 0 or 1 and repeated `put` of the same key - Time and space complexity ### Part 2 — Extend it into a least frequently used cache Implement `LFUCache(capacity)` with the same `get` and `put`, but change the eviction policy: each entry counts how many times it has been accessed, and when a new key is inserted into a full cache, the entry with the lowest count is evicted. `get` and `put` must still be O(1). ```hint Finding the minimum Each access raises one entry's count by exactly one. Think about what that implies for how the smallest count can change, so that you never have to search for it. ``` ```hint Equal counts Several entries can share the lowest count. Decide which of them goes, and make sure your structure finds it without a scan. ``` #### Clarifying Questions for this Part - When several entries share the lowest count, which one is evicted? - Does a new entry start with a count of 1, and does a key that was evicted and later inserted again start over? #### What This Part Should Cover - How entries are grouped by access count and how the smallest count is tracked in constant time - The tie-break rule among entries with the same count and how the structure enforces it - What is reused from the first cache and what changes - Edge cases such as updating an existing key in a full cache and evicting immediately before an insertion ### What a Strong Answer Covers - Both caches meet O(1) for `get` and `put`, with a clear argument for every step - Correct pointer handling when entries are moved, inserted and removed - Miss, update, capacity and tie-break semantics fixed before coding - Tests or a walked-through trace that exercise the eviction order - Awareness of practical concerns such as memory overhead per entry and concurrent access ### Follow-up Questions - How would you make either cache safe for concurrent use, and what does a single lock cost under heavy load? - An LFU cache can keep entries that were popular long ago but are no longer used. How would you let counts age so the cache adapts? - How would you add a per-entry time-to-live? - What is the memory overhead per entry of each design, and how could you reduce it?