Live Coding Interview Prep

Course Content

Live Coding Interview Prep

7 sections · 50 lessons

Build a caching layer for LLM responses.

What you need to know

The same prompt is sent far more often than you would expect: FAQ questions, nightly batch jobs re-run on unchanged rows, retries after a timeout. An exact-match cache returns the stored answer in about a millisecond, for nothing.

The key must include every input that changes the output. Forget temperature in the key and a creative-writing request at 1.0 gets served the answer generated at 0.0. Hash a canonical JSON of everything:

  • sort_keys=True so {"a":1,"b":2} and {"b":2,"a":1} hash the same;
  • compact separators so whitespace changes do not matter.

LRU (least recently used) eviction drops the entry that has gone longest without a read. An OrderedDict keeps insertion order and can move a key to the end in O(1), which makes it a ready-made LRU.

TTL (time to live) expires entries after a fixed time, so a changed policy document does not keep producing old answers forever.

Response cache (this question)

  • Your code stores the whole answer
  • Hit: no model call at all, near-zero cost
  • Only for identical requests

Provider prompt caching

  • The provider stores the processed prompt prefix
  • Hit: cheaper, faster input; the answer is still generated
  • Works for any request sharing a long prefix
Python
import hashlib, json, timefrom collections import OrderedDictfrom collections.abc import Callabledef cache_key(model: str, messages: list[dict], **params) -> str:    """Stable hash of every input that affects the output."""    payload = json.dumps({"model": model, "messages": messages, "params": params},                         sort_keys=True, separators=(",", ":"), ensure_ascii=False)    return hashlib.sha256(payload.encode("utf-8")).hexdigest()_MISS = object()class TTLCache:    """LRU cache with per-entry expiry. get/set are O(1)."""    def __init__(self, maxsize: int = 1000, ttl: float = 3600,                 clock: Callable[[], float] = time.monotonic) -> None:        self.maxsize, self.ttl, self.clock = maxsize, ttl, clock        self.store: OrderedDict[str, tuple[float, object]] = OrderedDict()        self.hits = self.misses = 0    def get(self, key: str):        entry = self.store.get(key)        if entry is None or entry[0] <= self.clock():            self.store.pop(key, None)                  # drop it if it had expired            self.misses += 1            return _MISS        self.store.move_to_end(key)                    # now the most recently used        self.hits += 1        return entry[1]    def set(self, key: str, value) -> None:        self.store[key] = (self.clock() + self.ttl, value)        self.store.move_to_end(key)        if len(self.store) > self.maxsize:            self.store.popitem(last=False)             # evict the least recently useddef cached_call(model: str, messages: list[dict], call_fn: Callable, cache: TTLCache, **params):    key = cache_key(model, messages, **params)    if (hit := cache.get(key)) is not _MISS:        return hit    value = call_fn(model=model, messages=messages, **params)    cache.set(key, value)    return value

The tricky parts:

  • _MISS sentinel. Returning None for a miss makes it impossible to cache a legitimate None or empty result; a private sentinel object cannot collide with real data.
  • time.monotonic for expiry, injectable as clock so tests can move time forward.
  • ensure_ascii=False keeps Hindi or Tamil text as UTF-8 in the key payload; the hash is the same either way, but the payload is readable when debugging.

Complexity: cache_key is O(size of the request) to serialise and hash. get and set are O(1): dict lookup, move_to_end and popitem(last=False) are constant time in an OrderedDict. Space is O(maxsize × response size).

A real-life example

A fake clock and a counting model show hits, a parameter change, LRU eviction and expiry:

Python
now = [0.0]cache = TTLCache(maxsize=2, ttl=60, clock=lambda: now[0])calls = []def model_call(model, messages, **params):    calls.append(messages[-1]["content"])    return f"answer to {messages[-1]['content']}"ask = lambda q, **p: cached_call("claude-opus-5", [{"role": "user", "content": q}],                                 model_call, cache, **p)ask("refund time?", temperature=0)      # miss -> modelask("refund time?", temperature=0)      # hitask("refund time?", temperature=1)      # different key -> model; cache now full (2)ask("cod available?", temperature=0)    # model; evicts the least recently used entrynow[0] = 61.0ask("cod available?", temperature=0)    # expired -> model againprint(len(calls), cache.hits, cache.misses)   # 4 1 4
callkeycache state after (oldest first)result
1refund, t=0[refund/0]miss
2refund, t=0[refund/0]hit
3refund, t=1[refund/0, refund/1]miss
4cod, t=0[refund/1, cod/0] — refund/0 evictedmiss
5 (t = 61 s)cod, t=0[refund/1] — cod/0 expired and droppedmiss

A railway enquiry bot answering "what is the Tatkal booking time?" thousands of times a day serves almost all of them from this cache.

Follow-up questions to expect

  • "Hit rate is zero in production — why?" — Something unique is in the key: a timestamp or request id in the system prompt, or unsorted JSON. Log the key payload for two identical-looking requests and diff them.
  • "Can you cache per-user answers?" — Only with the user or tenant id inside the key. Otherwise one customer's order details are served to another.
  • "A popular key expires and 500 requests miss at once — what happens?" — A cache stampede. Use a per-key lock (single-flight) so one request refills the cache while the others wait for it.