46. LRU Semantic Embedding Cache

Problem

Cartesia's realtime WebSocket API confirms that each streaming context carries appended history across chunks, so prosody stays continuous without reprocessing the whole transcript. A plausible extension of that design is a bounded, in-memory cache of precomputed context/embedding state keyed by context id, evicting the least-recently-used entry once the cache is full.

Implement an LRU (Least-Recently-Used) cache from scratch — a hashmap plus a doubly linked list, not a wrapper around collections.OrderedDict — so that both get and put run in true O(1) time regardless of how many entries the cache holds.

Source: src/46_lru_semantic_embedding_cache.py

class LRUEmbeddingCache:
    def __init__(self, capacity: int): ...
    def get(self, key) -> int: ...  # returns -1 if key not present
    def put(self, key, value) -> None: ...  # evicts LRU entry if over capacity

>>> c = LRUEmbeddingCache(2)
>>> c.put("ctx-1", 101)
>>> c.put("ctx-2", 102)
>>> c.get("ctx-1")
101
>>> c.put("ctx-3", 103)   # capacity 2 is full, ctx-2 is least-recently-used -> evicted
>>> c.get("ctx-2")
-1

Step-by-Step Approach

1. Recognize the two requirements that rule out simpler structures: O(1) lookup by key (needs a hashmap) and O(1) "move to most-recently-used" plus O(1) eviction of the least-recently-used entry (needs a doubly linked list, since arrays can't reorder in O(1)).
2. Build a doubly linked list with two sentinel nodes, head and tail, so every real node always has a non-null prev/next — this removes edge-case branching for the first/last real node.
3. Maintain the invariant that the list is ordered most-recently-used (right after head) to least-recently-used (right before tail).
4. Back the list with a hashmap from key to its node, so any node can be located and unlinked in O(1) without scanning the list.
5. On get: if the key is missing, return -1. Otherwise unlink the node and re-insert it right after head (a read counts as a "use"), then return its value.
6. On put: if the key exists, update its value and move it to the front, same as a read. Otherwise, if the cache is at capacity, evict the node just before tail (the true LRU entry) from both the hashmap and the list before inserting the new node at the front.
7. Every operation touches only a constant number of pointers and one hashmap lookup, so both get and put are O(1) regardless of cache size.

The key insight is that recency order needs a structure that supports O(1) arbitrary-position removal and O(1) front-insertion — a doubly linked list — while key-based lookup needs O(1) addressing — a hashmap. Combining them (hashmap of key to node) gets both properties at once.

Reference solution

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


class LRUEmbeddingCache:
    # hashmap (key -> node) for O(1) lookup + doubly linked list with sentinel
    # head/tail for O(1) reorder; get() and put() are both O(1) time, O(n) space
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key -> _Node
        self.head = _Node()  # sentinel; head.next = most recently used
        self.tail = _Node()  # sentinel; tail.prev = least recently used
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        # unlink node from its current position, O(1) given the node reference
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node):
        # splice node in right after head, i.e. the most-recently-used slot
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        # a read counts as a "use" too, so move the node to the front
        self._remove(node)
        self._add_to_front(node)
        return node.value

    def put(self, key, value):
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self._remove(node)
            self._add_to_front(node)
            return
        if len(self.cache) >= self.capacity:
            # evict the least-recently-used entry, which sits right before tail
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]
        node = _Node(key, value)
        self.cache[key] = node
        self._add_to_front(node)

Key Functions & Tricks

• Sentinel head/tail nodes — eliminate null checks for the first/last real node during insert and remove.
• dict[key] -> _Node — hashmap of key to linked-list node gives O(1) addressing into an otherwise O(n)-to-search list.
• _remove(node) / _add_to_front(node) — the two primitive O(1) pointer operations every get/put composes from.
• "Move to front on both read and write" — the core LRU invariant: any touch, not just insertion, refreshes recency.
• self.tail.prev — always the true least-recently-used node, the eviction target when over capacity.

How to Recognize This Pattern