# What Stays Warm > Memory is small and the stream never stops. Keep only what was just asked for, in the order it was asked. Canonical URL: Domain: Python · Difficulty: medium · Seniority: L3 ## Problem An edge cache keeps only the `capacity` most recently requested keys live at once. Replay the request log in `ops`: an `['access', key]` entry marks that key as the most recently used, adding it when it is new and dropping the least recently used key whenever a new arrival would push the window past `capacity`; an `['snapshot']` entry records the keys held at that moment, most recently used first. Return one list per `['snapshot']` in order, and an empty list overall when the log holds no snapshots. ## Worked solution and explanation ### What this really is This is an LRU window wearing a cache costume. The skill being probed: can you keep a stream of keys ordered by recency so that touching a key already in the window moves it to the front in constant time? Anyone can store the keys. The trick is the move-to-front. Reach for a Python list and every access becomes a remove-then-reinsert that shifts O(n) elements, so the hot path you built to be fast turns quadratic. Two quieter misses also bite: only snapshots produce output, so appending on the access branch pollutes the result with junk, and an evicted key that comes back must re-enter as brand new, not resurrect its old position. ### Why an array betrays you here **Plain Python list** Promoting a key means list.remove(key), an O(n) scan, then insert at index 0, an O(n) shift. Eviction pops the tail cheaply, but every access already paid for a full pass. Replaying m events over a window of n keys is O(m*n). **Doubly linked node window** Each node carries prev and next. Promoting unlinks the node from between its neighbors and splices it behind the head in a fixed number of pointer writes. With a key to node dict for lookup, both promote and evict are O(1), so the whole replay is O(m). The dict tells you WHERE a key is in O(1); the linked order tells you WHICH key is least recent in O(1). Neither alone is enough: a set has no order, and a plain list has order but no cheap interior move. You need both working together. #### Step 1: Anchor the window with sentinels The node is given to you: a key plus prev and next. Build the list with two sentinel nodes, a head and a tail, so head.next is always the most recent key and tail.prev is always the least recent. Sentinels erase the empty-window and single-node special cases. Keep a dict mapping each live key to its node. #### Step 2: Promote a known key in O(1) When an accessed key is already live, look up its node, unlink it from between its current neighbors, and splice it in right behind the head. That is the constant-time interior move an array cannot do without shifting. #### Step 3: Admit a new key, evict the coldest When the key is new, make a node, register it in the dict, and push it to the front. If that pushed the window past capacity, the node at tail.prev is the least recently used: unlink it and delete its key from the dict. #### Step 4: Snapshot by walking the order A snapshot walks from head.next to the tail sentinel, collecting keys most-recent-first into a fresh list. Access entries mutate the window silently and contribute nothing; only snapshots append to the result. Return the collected snapshots. **Dict-indexed doubly linked recency window** ```python class ListNode: def __init__(self, key): self.key = key self.prev = None self.next = None def hot_key_window(ops, capacity): head = ListNode(None) # sentinel: head.next is most recent tail = ListNode(None) # sentinel: tail.prev is least recent head.next = tail tail.prev = head nodes = {} def unlink(node): node.prev.next = node.next node.next.prev = node.prev def push_front(node): node.prev = head node.next = head.next head.next.prev = node head.next = node results = [] for entry in ops: kind = entry[0] if kind == "access": key = entry[1] if key in nodes: node = nodes[key] unlink(node) push_front(node) else: node = ListNode(key) nodes[key] = node push_front(node) if len(nodes) > capacity: lru = tail.prev unlink(lru) del nodes[lru.key] elif kind == "snapshot": order = [] current = head.next while current is not tail: order.append(current.key) current = current.next results.append(order) return results ``` > **Time and Space Complexity** > > The dict makes lookup O(1); the doubly linked order makes promote and evict O(1). Each access is constant work, so replaying m events is O(m) regardless of how large the window is. A snapshot costs O(k) for the k keys it lists. Space is O(capacity) for the live window plus its dict entries. > **Interviewers Watch For** > > The tell of seniority is two structures cooperating: a dict for O(1) lookup and a doubly linked list for O(1) reordering. A candidate who keeps only a list and calls remove on every access has built something that passes the examples and collapses under load. The sentinel head and tail are the other quiet signal: they kill the empty-window and single-node branches before they exist. > **Common Pitfall** > > Three classic misses. Appending a value on the access branch: only snapshots emit, so an access must mutate silently. Forgetting that a snapshot taken while the window is empty is an empty list, not a skipped result. And resurrecting an evicted key: once a key falls off the tail it is gone, so accessing it again admits a fresh most-recent entry that may itself trigger an eviction. ## Common follow-up questions - How would you add a remove(key) operation that drops a key from the window immediately? _(Tests unlinking an arbitrary interior node through its neighbors and cleaning the lookup dict in the same step.)_ - What changes if a snapshot must list keys least recently used first instead? _(Tests walking from the tail sentinel forward, or otherwise reversing the traversal direction.)_ - When would a plain dict with move_to_end have been enough, and what are you really reimplementing in this solution? _(Tests awareness that an insertion-ordered dict with move_to_end is itself a hash map layered over a doubly linked list, which is exactly the structure being built by hand here.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/what_stays_warm) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.