19. LRU Cache for Voice Session State

Problem

A voice agent keeps a small in-memory blob of per-session state (detected language, turn count, running transcript offset) so it doesn't have to re-derive it from scratch on every audio chunk. Memory is bounded, so only the most recently touched sessions can be kept warm; the rest fall back to a colder store (out of scope here).

Implement a fixed-capacity cache where both reading and writing a session count as "recently used," and the least-recently-used session is evicted first when the cache is full.

Source: src/19_voice_session_lru_cache.py

class VoiceSessionCache:
    def __init__(self, capacity: int): ...
    def get(self, session_id: str) -> dict | None: ...
    def put(self, session_id: str, state: dict) -> None: ...

>>> c = VoiceSessionCache(2)
>>> c.put("s1", {"lang": "en"})
>>> c.put("s2", {"lang": "fr"})
>>> c.get("s1")
{'lang': 'en'}
>>> c.put("s3", {"lang": "de"})
>>> c.get("s2")

Step-by-Step Approach

1. Recognize that both operations need O(1) time: a plain dict alone gives O(1) lookup but no ordering, and a plain list gives ordering but O(n) reordering — the classic fix is a hash map plus a structure that supports O(1) move-to-front/back.
2. In Python, collections.OrderedDict gives both for free: it's a hash map that also remembers insertion/move order, with move_to_end as an O(1) reordering primitive.
3. On get: if the key is missing, return None; otherwise call move_to_end to mark it most-recently-used, then return its value.
4. On put: if the key already exists, move it to the end first (so overwriting a value still refreshes its recency); then set/overwrite the value.
5. After inserting, check if the cache exceeds capacity; if so, evict the entry at the front of the ordering (popitem(last=False)) — that's always the true least-recently-used entry because every touch moves a key to the back.

The key insight is that "least recently used" is really just "maintain a total order by recency with O(1) reordering," and a doubly linked list (which is what OrderedDict is internally) is exactly the structure that supports moving an arbitrary node to either end in O(1), while a companion hash map gives O(1) access to that node by key.

Reference solution

from collections import OrderedDict


class VoiceSessionCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        # OrderedDict tracks insertion/access order directly: front = LRU,
        # back = MRU. get/put both call move_to_end to mark "recently used".
        self.store: OrderedDict[str, dict] = OrderedDict()

    def get(self, session_id: str) -> dict | None:
        if session_id not in self.store:
            return None
        self.store.move_to_end(session_id)  # mark as most-recently-used
        return self.store[session_id]

    def put(self, session_id: str, state: dict) -> None:
        if session_id in self.store:
            self.store.move_to_end(session_id)
        self.store[session_id] = state
        if len(self.store) > self.capacity:
            # popitem(last=False) removes the front of the ordering, i.e. the LRU entry
            self.store.popitem(last=False)

Key Functions & Tricks

• collections.OrderedDict — hash map with a built-in doubly-linked ordering; the go-to Python primitive for LRU without hand-rolling a linked list.
• move_to_end(key) — O(1) relocation of a key to the most-recently-used end.
• popitem(last=False) — O(1) pop from the least-recently-used end.
• Touching order on both get and put — the detail that makes it LRU rather than FIFO; forgetting to refresh on read is the most common bug.

How to Recognize This Pattern