What Stays Warm

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

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.

Memory is small and the stream never stops. Keep only what was just asked for, in the order it was asked.

Example 1

Input:

ops = [["access","home"],["access","cart"],["snapshot"],["access","home"],["snapshot"],["access","search"],["snapshot"]], capacity = 2

Output:

[["cart","home"],["home","cart"],["search","home"]]

Example 2

Input:

ops = [["access","img"],["snapshot"],["access","css"],["access","img"],["snapshot"]], capacity = 3

Output:

[["img"],["img","css"]]

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
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

Common follow-up questions