Implement LRU without an ordered-map helper

A dictionary plus list of keys gives fast lookup but O(C) removal or recency search at capacity C. A linked list alone gives O(1) movement once a node is known, but O(C) lookup. Combine the two: a map points to the same nodes linked between head and tail sentinels. Sentinels eliminate special cases for first/last real nodes.

On a hit, unlink the node and append just before tail. On overwrite, update its value and perform the same movement. On a new key, allocate one node, register it, and append it; if oversized, unlink head.next and remove its map entry. Clearing removed pointers makes accidental reuse easier to diagnose.

every map entry corresponds to exactly one real list node, every real node appears in the map, adjacent next/previous pointers agree, and the list orders keys from least to most recent. Both structures must change within one operation. Forgetting the map deletion leaves a ghost hit on an evicted node.

Expected map lookup plus constant pointer work gives O(1) time per get/put, subject to ordinary hash-table assumptions. State is O(C) nodes/map entries plus two sentinels. Each operation uses O(1) auxiliary space. The inspection helper items_lru() costs O(C) time/output space and is not part of the constant-time API.

Follow-up 1 — capacity is bytes. Predict what happens when c alone occupies eight bytes in a ten-byte cache containing a=4 and b=4. Evicting one is insufficient; remove least-recent entries until used bytes fit. Define oversized-object rejection and whether an unsuccessful overwrite preserves the old value before coding.

Follow-up 2 — concurrent readers. A get is a mutation because it changes recency. One mutex can cover map lookup and list movement as a single critical section. Do not run user loaders while holding it. Per-key load coordination is a separate requirement; a locked cache alone does not prevent duplicate computation.

Senior depth includes pointer-integrity checks after mixed operations and a simple list-based oracle. Lead depth distinguishes cache policy, load ownership, and memory accounting. The supplied cache intentionally makes no thread-safety claim.

Reference: solution.py (download file, source below). Tests cover middle removal, capacity 0/1, overwrite/None/miss behavior, eviction, and every link after seeded operations.

"""LRU implemented with a dict and explicit doubly linked sentinel list."""


class Node:
    __slots__ = ("key", "value", "prev", "next")

    def __init__(self, key=None, value=None):
        self.key, self.value = key, value
        self.prev = self.next = None


class LRUCache:
    def __init__(self, capacity):
        if not isinstance(capacity, int) or capacity < 0:
            raise ValueError("capacity must be a nonnegative integer")
        self.capacity = capacity
        self.nodes = {}
        self.head, self.tail = Node(), Node()
        self.head.next, self.tail.prev = self.tail, self.head

    @staticmethod
    def _unlink(node):
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = node.next = None

    def _append_recent(self, node):
        previous = self.tail.prev
        previous.next = node
        node.prev, node.next = previous, self.tail
        self.tail.prev = node

    def get(self, key):
        node = self.nodes[key]
        self._unlink(node)
        self._append_recent(node)
        return node.value

    def put(self, key, value):
        """Return an evicted (key, value), or None; overwrite refreshes recency."""
        if key in self.nodes:
            node = self.nodes[key]
            node.value = value
            self._unlink(node)
            self._append_recent(node)
            return None
        if self.capacity == 0:
            return key, value
        node = Node(key, value)
        self.nodes[key] = node
        self._append_recent(node)
        if len(self.nodes) > self.capacity:
            victim = self.head.next
            self._unlink(victim)
            del self.nodes[victim.key]
            return victim.key, victim.value
        return None

    def items_lru(self):
        result = []
        node = self.head.next
        while node is not self.tail:
            result.append((node.key, node.value))
            node = node.next
        return result

python -m unittest discover -s curriculum/04-scale-and-evolution/01-data-at-scale/problems/28-manual-lru-cache -p 'test_*.py'