Implement an LRU cache with per-entry TTL

The question

Implement a cache with a fixed capacity. When it’s full, evict the least recently used entry. Each entry also expires after a time-to-live. get and put should be O(1).

This is a warm-up, so the bar for execution is high: clean code, tests written as you go, and crisp answers to the follow-ups. It comes up in LLM loops because caches are everywhere in LLM systems: prompt results, embeddings, tool responses, permission lookups.

Clarify first

• Does a get refresh the TTL, or only the recency? (I’ll say recency only; the TTL is set on put.)
• When full, should an expired entry be evicted before a live LRU one? (Yes. Evicting live data while dead data sits there is wasteful.)
• Thread safety? (Not in the first version; it’s a follow-up.)
• Can I inject the clock? Always ask this. It makes the TTL testable without sleep.

Approach

An OrderedDict gives O(1) lookup and O(1) move-to-end, which is exactly an LRU list plus a hash map. Store (value, expires_at) and check expiry lazily on read.

from collections import OrderedDict
import time


class LRUTTLCache:
    """Least-recently-used cache where each entry also expires after a TTL."""

    def __init__(self, capacity: int, ttl_seconds: float, clock=time.monotonic):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.capacity = capacity
        self.ttl = ttl_seconds
        self._clock = clock
        self._data: OrderedDict = OrderedDict()  # key -> (value, expires_at)

    def get(self, key, default=None):
        item = self._data.get(key)
        if item is None:
            return default
        value, expires_at = item
        if self._clock() >= expires_at:
            del self._data[key]
            return default
        self._data.move_to_end(key)  # mark as most recently used
        return value

    def put(self, key, value, ttl_seconds: float | None = None) -> None:
        ttl = self.ttl if ttl_seconds is None else ttl_seconds
        if key in self._data:
            self._data.move_to_end(key)
        self._data[key] = (value, self._clock() + ttl)
        if len(self._data) > self.capacity:
            self._evict()

    def _evict(self) -> None:
        # Prefer dropping an expired entry; otherwise drop the least recently used.
        now = self._clock()
        for k, (_, expires_at) in self._data.items():
            if expires_at <= now:
                del self._data[k]
                return
        self._data.popitem(last=False)

    def __len__(self) -> int:
        return len(self._data)

One caveat to say out loud: _evict scans for an expired entry, which is O(n) in the worst case. If the interviewer pushes on it, see the first follow-up.

Tests

The fake clock makes every timing case deterministic and instant.

import pytest

from lru_ttl_cache import LRUTTLCache


class FakeClock:
    def __init__(self):
        self.t = 0.0

    def __call__(self):
        return self.t


def make(capacity=2, ttl=10):
    clock = FakeClock()
    return LRUTTLCache(capacity, ttl, clock=clock), clock


def test_get_returns_value_before_expiry():
    cache, clock = make()
    cache.put("a", 1)
    clock.t = 9.9
    assert cache.get("a") == 1


def test_entry_expires_at_ttl():
    cache, clock = make()
    cache.put("a", 1)
    clock.t = 10
    assert cache.get("a") is None
    assert len(cache) == 0


def test_evicts_least_recently_used():
    cache, _ = make(capacity=2)
    cache.put("a", 1)
    cache.put("b", 2)
    cache.get("a")  # "b" is now least recently used
    cache.put("c", 3)
    assert cache.get("b") is None
    assert cache.get("a") == 1 and cache.get("c") == 3


def test_prefers_evicting_expired_entry_over_lru():
    cache, clock = make(capacity=2)
    cache.put("a", 1)
    cache.put("b", 2, ttl_seconds=1)
    cache.get("b")  # "a" is LRU, but "b" is about to expire
    clock.t = 2
    cache.put("c", 3)
    assert cache.get("a") == 1
    assert cache.get("b") is None


def test_put_existing_key_updates_value_and_ttl():
    cache, clock = make()
    cache.put("a", 1)
    clock.t = 8
    cache.put("a", 2)
    clock.t = 15
    assert cache.get("a") == 2


def test_rejects_non_positive_capacity():
    with pytest.raises(ValueError):
        LRUTTLCache(0, 10)

Complexity

• get and put: O(1) on average, except the expired-entry scan during eviction, which is O(n) in the worst case.
• Space: O(capacity).

Follow-ups the interviewer will ask

1. Make eviction of expired entries O(log n). Keep a min-heap of (expires_at, key) alongside the dict. Heap entries go stale when a key is overwritten, so on pop, check that the heap entry still matches the dict before deleting (lazy deletion).
2. Make it thread-safe. A single lock around get and put is correct and usually enough. Note that get changes the order, so reads need the lock too. Under high contention, shard the cache by key hash with one lock per shard.
3. Expired entries waste memory if nobody reads them. Add a background sweep, or check a few random entries on each put, the way Redis samples keys for expiry.
4. Cache semantic results for an LLM. The key is no longer exact: you embed the query and look for a neighbour above a similarity threshold. The hard parts are choosing the threshold and making the key include tenant and permissions, so a cached answer is never served to someone who couldn’t see its sources.
5. Bound by bytes, not entries. Track each value’s size and evict until under the byte budget.

Common mistakes

• Calling time.time() directly and testing with sleep.
• Forgetting that get must update recency.
• Updating an existing key without moving it to the end.
• Returning an expired value because expiry is only checked during eviction.