LRU Cache

Implement a fixed-capacity LRU cache supporting `get` and `put` in O(1). Bloomberg asks it both as a standard cache implementation and as an OOP design discussion, with follow-ups around thread safety, persistence, eviction callbacks, TTL, and class boundaries. In the AI-role R2 phone screen, the implementation may be provided and the task becomes refactoring it behind a generic eviction-policy abstraction that can also accommodate LFU. Requirements Implement a class: class LRUCache: def __init__(self, capacity: int): ... def get(self, key: int) -> int: ... def put(self, key: int, value: int) -> None: ... get(key) returns the value if present (and counts as a recent use), otherwise -1. put(key, value) inserts or updates. If the cache is at capacity and the key is new, evict the least-recently-used entry first. Both operations run in O(1) average time. Follow-ups Bloomberg interviewers actually push (often several in a row): Explain the object model: cache, node, list helpers, and whether the linked-list operations should be private methods. Make it thread-safe. Discuss read-write locks vs a single mutex vs lock-free / segmented approaches. Add a TTL per entry: how does eviction interact with the LRU order? Lazy expiration vs background sweep. Add a callback fired on eviction (e.g., write-back to disk). Replace LRU with LFU. Compare the data-structure cost. Persist the cache to disk and recover after restart. What invariants must the on-disk layout maintain? Minority variant: Start from a provided LRU implementation and refactor the eviction logic behind a generic abstraction that can support policies such as LFU. Clarify before coding whether the expected artifact is a cache service, a local cache library, or a refactor of the supplied code. Examples LRUCache(2) put(1, 1) put(2, 2) get(1) -> 1 put(3, 3) // evicts key 2 get(2) -> -1 put(4, 4) // evicts key 1 get(1) -> -1 get(3) -> 3 get(4) -> 4 Notes The canonical structure is a HashMap from key to node + a doubly linked list of nodes ordered by recency. get and put both move the touched node to the head; eviction removes the tail node and its map entry. Always use a doubly linked list, not singly — removal must be O(1) and a singly linked list forces a scan. Use sentinel head / tail nodes to eliminate null checks on the list edges. This single change cuts a major source of bugs. Time and space: O(1) average per operation, O(capacity) space. The OOP-flavored version grades encapsulation as much as mechanics. Keep remove(node), addToFront(node), and moveToFront(node) small and private; avoid leaking linked-list details through the public cache API. For the thread-safety follow-up, the simplest correct answer is a single mutex around every operation. A more sophisticated answer uses a read-write lock plus deferred LRU updates (mark touched, reorder on a lazy schedule). Preparation Implement the DLL + HashMap from scratch without looking at boilerplate. Be able to draw the structure on paper. Refactor the implementation into an OOP-clean version with helper methods and sentinel nodes; Bloomberg may frame the same prompt as a class-design exercise rather than a pure LeetCode clone. Practice articulating the follow-up answers: thread safety, TTL, persistence, eviction callbacks. Bloomberg interviewers chain three to five of these and a calm structured answer matters more than a perfect one. Drill the LFU variant (LeetCode 460) — it is the most common follow-up after a clean LRU answer. Starting from a completed LRU implementation, extract a pluggable eviction-policy interface and wire in LRU and LFU policies without changing the public cache API. Practice explaining which state belongs to the cache and which belongs to each policy.