Cache with TTL
medium · LRU eviction + time-based expiry
Brief-reported interview attribution (unverified): Amazon ("LRU Cache with a time constraint"), Microsoft
How to approach an LLD roundRequirements
- Functional: get/put with per-entry TTL, lazy expiry, LRU eviction at capacity, updating a key resets its TTL.
- Non-functional:
getmust return None (not a sentinel) for a missing or expired key; expiry must free space before eviction runs; the eviction policy must be replaceable. - Out of scope: distributed caching, persistence, write-through.
Statement
Design a cache with a fixed capacity. Every entry may carry a TTL
in seconds (None = never expires). get returns None for a missing or expired
key and refreshes the recency of a live key (LRU). put on an existing key
updates its value and TTL and refreshes its recency. When the cache is full, insert
evicts the least recently used entry — but an expired entry is evicted first and
does not force a live entry out. Time comes from a clock callable passed to the
constructor (default: time.time).
class TTLCache:
def __init__(self, capacity, clock=None):
def get(self, key):
# -> value, or None if missing or expired
def put(self, key, value, ttl_seconds=None):
# insert or update; ttl_seconds=None means the entry never expiresRules. Expiry is checked as now >= inserted_at + ttl_seconds. Expired
entries are removed lazily (on access, and before eviction). put with a TTL
starts the TTL at the time of the put.
Tests use explicit inputs and injected clocks/callbacks. No network, real threads or application-server execution is involved.
Class design (SOLID)
CacheEntry (value + expiry; SRP). EvictionPolicy (ABC interface; chooses the victim; SRP) with LruEviction (OCP — LFU swaps in). TTLCache orchestrates and depends on the policy and the injected clock (DIP) — the clock is what makes the tests deterministic. Expiry is tracked in a min-heap keyed by (expire_at, seq, key), so _purge_expired touches only the expired entries; stale heap entries left by re-puts are skipped by comparing expire_at. Pattern: Strategy (eviction).
Public demo
# Public demo: run after implementing the class API above.
now = [1000.0]
c = TTLCache(2, clock=lambda: now[0])
c.put('a', 1, ttl_seconds=10)
now[0] = 1009.0
print(c.get('a'))
now[0] = 1010.0
print(c.get('a'))Reference solution and hidden tests
Locked. Open the interactive editor and attempt the problem; the reference, hidden test descriptions, pattern explanation and complexity are available only after an explicit reveal.
Concurrency
A cache is the canonical concurrent data structure: get must not return a value that expires mid-read, and put must not evict an entry another thread just refreshed. Guard get/put with one lock (or a read-write lock). In production this is a threading.Lock around the OrderedDict plus the purge. The reference is single-threaded; the lock is described here.
Trade-offs & extensions
Lazy expiry (purge on access) is cheap but can leave dead entries in memory until the next access; a background sweeper would fix that. Stale heap entries from re-puts are skipped, not removed, so the heap can hold dead entries until they reach the top. Extending: a CacheLoader (read-through) and per-key TTL stats.
Starter code
import heapq
import time
from abc import ABC, abstractmethod
from collections import OrderedDict
class CacheEntry:
def __init__(self, value, expire_at):
"""Initialize the state described in the problem."""
pass
def is_expired(self, now):
"""Implement the return value and rules in the API contract."""
pass
class EvictionPolicy(ABC):
@abstractmethod
def choose(self, data, now):
"""Implement the return value and rules in the API contract."""
pass
class LruEviction(EvictionPolicy):
def choose(self, data, now):
"""Implement the return value and rules in the API contract."""
pass
class TTLCache:
def __init__(self, capacity, clock=None, policy=None):
"""Initialize the state described in the problem."""
pass
def get(self, key):
"""-> value, or None if missing or expired"""
pass
def put(self, key, value, ttl_seconds=None):
"""insert or update; ttl_seconds=None means the entry never expires"""
pass
Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.
Return to the Python interpreter