Debug a Linked-List LRU Cache That Evicts the Wrong Keys and Crashes

You are handed a fixed-capacity least-recently-used (LRU) cache and asked to debug it. The intended behavior: - `LRUCache(capacity)` creates a cache that holds at most `capacity` keys. - `get(key)` returns the stored value, or `-1` if the key is absent. A successful `get` counts as a use of that key. - `put(key, value)` inserts or updates a key; an update also counts as a use. Inserting a new key into a full cache first evicts the least recently used key. - Both operations should run in constant average time. The code and language used in the interview are not reported. The Python version below is a stand-in written for practice: it uses a dictionary plus a doubly linked list with sentinel nodes, and it contains several defects. ```python class Node: def __init__(self, key, value): self.key = key self.value = value self.prev = None self.next = None class LRUCache: def __init__(self, capacity): self.capacity = capacity self.nodes = {} # key -> Node self.head = Node(None, None) # sentinel before the most recently used entry self.tail = Node(None, None) # sentinel after the least recently used entry self.head.next = self.tail self.tail.prev = self.head def _unlink(self, node): node.prev.next = node.next node.next.prev = node.prev def _push_front(self, node): node.prev = self.head node.next = self.head.next self.head.next = node def get(self, key): node = self.nodes.get(key) if node is None: return -1 return node.value def put(self, key, value): if key in self.nodes: node = self.nodes[key] node.value = value self._unlink(node) self._push_front(node) return if len(self.nodes) > self.capacity: lru = self.tail.prev self._unlink(lru) node = Node(key, value) self.nodes[key] = node self._push_front(node) ``` This test fails: ```python cache = LRUCache(2) cache.put(1, 1) cache.put(2, 2) assert cache.get(1) == 1 cache.put(3, 3) # should evict key 2 assert cache.get(2) == -1 cache.put(4, 4) # should evict key 1 assert cache.get(1) == -1 assert cache.get(3) == 3 assert cache.get(4) == 4 ``` ### Constraints and Clarifications - Keys and values are non-negative integers. - Assume single-threaded use unless you ask otherwise. - Keep the dictionary-plus-linked-list design: the goal is to fix it, not to replace it with a library class. ### Clarifying Questions - What should a cache with capacity 0 do on `put`? - Is the cache ever shared between threads? - Can `-1` ever be a legitimate stored value? ### Part 1 — Find the defects Trace the failing test through the code, explaining exactly what happens at each step, then list every defect, including those the test has not reached yet. For each one, describe the symptom a caller would see. ```hint Check both directions For every pointer a helper changes, ask which pointer on the neighboring node should have changed with it. ``` #### What This Part Should Cover - A step-by-step trace that explains the first wrong result and what happens after it - Defects in the list wiring, the recency update, the eviction condition and the dictionary bookkeeping - How some defects mask others until the first one is fixed ### Part 2 — Fix it and prove it Write the corrected class, then describe the checks and tests that would have caught these defects early. ```hint Make corruption loud Think of a check you could run after every operation that fails the moment the list and the dictionary disagree. ``` #### What This Part Should Cover - Corrected code that keeps constant-time operations - An explicit decision for capacity 0 - An invariant check and a test strategy that goes beyond the single sample test ### What a Strong Answer Covers - Systematic debugging: reproduce, trace, form a hypothesis, verify, rather than guessing - Finds every defect, not only the first failing assertion - Understands why the sentinel nodes exist and how a missing back pointer corrupts eviction - Keeps the dictionary and the list consistent on every code path - Adds tests that check invariants and compare against a simple reference model ### Follow-up Questions - How would you make this cache safe for concurrent use, and what does locking cost on a hot path? - How would you add a per-entry time-to-live without losing constant-time operations? - Why might a production cache prefer an approximate eviction policy over exact LRU?