12. LRU Semantic Cache for Repeated Queries

Problem

A lab's serving layer sees many exact-repeat queries in a short span — users re-asking the same canonical prompt, or an eval harness replaying the same fixture. Rather than re-running an expensive model call each time, cache recent responses and serve repeats straight from memory.

Implement a bounded-capacity cache with true O(1) get/put where the least-recently-used entry is evicted once capacity is exceeded — a hashmap plus a doubly linked list, not a wrapper around collections.OrderedDict.

Source: src/12_lru_semantic_cache.py

class LRUQueryCache:
    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

>>> cache = LRUQueryCache(2)
>>> cache.put("query_a", 101)
>>> cache.put("query_b", 102)
>>> cache.get("query_a")
101
>>> cache.put("query_c", 103)   # capacity 2 is full, query_b is LRU -> evicted
>>> cache.get("query_b")
-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) reordering-by-recency plus O(1) eviction of the least-recently-used item (needs a doubly linked list, since arrays/lists cost O(n) to remove from the middle).
2. Maintain a hashmap from key to linked-list node, and a doubly linked list ordered by recency: most-recently-used at the front, least-recently-used at the back.
3. Use two sentinel nodes (a dummy head and dummy tail) so every real node always has both a prev and a next — this removes every None-check that would otherwise litter the remove/insert logic.
4. Implement two small helpers first: _remove(node) unlinks a node from wherever it sits, and _add_to_front(node) splices a node in right after the head. Every other operation is built from these two.
5. get(key): if the key is missing, return -1. Otherwise, touching a key makes it most-recently-used — remove the node and re-add it to the front, then return its value.
6. put(key, value): if the key already exists, update its value and move it to the front (same recency-refresh as get). Otherwise, if the cache is at capacity, evict the node just before the tail sentinel (the true LRU); then create and front-insert the new node.

The key insight is that a doubly linked list turns "move this node to the front" into a constant number of pointer rewrites regardless of where the node currently sits, and pairing it with a hashmap turns "find this node by key" into O(1) as well — together they give O(1) worst-case (not amortized) time for both operations.

Reference solution

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


class LRUQueryCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map: dict = {}
        # sentinel head/tail so every real node always has both neighbors -- no None-checks
        self.head = _Node()
        self.tail = _Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        # O(1): unlink node from wherever it currently sits
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node):
        # O(1): splice node in right after head (the MRU 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.map:
            return -1
        node = self.map[key]
        # touching a key makes it most-recently-used
        self._remove(node)
        self._add_to_front(node)
        return node.value

    def put(self, key, value):
        if key in self.map:
            node = self.map[key]
            node.value = value
            self._remove(node)
            self._add_to_front(node)
            return
        if len(self.map) >= self.capacity:
            # tail.prev is the least-recently-used real node -- evict it
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]
        node = _Node(key, value)
        self.map[key] = node
        self._add_to_front(node)

Key Functions & Tricks

• Sentinel head/tail nodes — eliminate every edge-case None-check around list boundaries
• _remove(node) / _add_to_front(node) — two small O(1) primitives that every public method composes
• self.tail.prev — the LRU entry is always exactly the node just before the tail sentinel
• Hashmap of key → node — turns "find by key" from O(n) list traversal into O(1)
• Refreshing recency on both get and put-on-existing-key — a common spec detail that's easy to miss

How to Recognize This Pattern