LRU cache with TTL

Q: Why not a background thread that deletes expired keys?

You can add one, but it does not replace the lazy checks: between sweeps a reader could still see a dead entry, so get must check expiry anyway. A sweeper also brings locking and shutdown concerns. The lazy design is correct on its own, and a periodic purge is only an optimisation to return memory from keys nobody reads again.

Q: How would this look in Go, and in production?

In Go: a map[K]*list.Element with container/list for recency and container/heap over a slice of expiry records, all behind one sync.Mutex. Take a func() time.Time (or a small Clock interface) in the constructor so tests can control time. Production caches often add jitter to TTLs so a batch of entries loaded together does not expire at the same moment and stampede the backend. They also export a metric for expirations separate from evictions.

Q: Why inject the clock instead of calling time.monotonic()?

Tests become deterministic and fast: you set the clock to 10 instead of sleeping for 10 seconds. Use a monotonic clock in production, because wall-clock time can jump backwards on an NTP correction and suddenly make every entry look fresh or expired.

mediumCaches

Extend the LRU cache so every entry also has a time to live. A service that caches tokens or service-discovery results needs both limits: a size cap so memory is bounded, and an expiry so a popular entry cannot stay stale forever.

API (Java: TTLCache<K, V>, same method names, put(key, value) and put(key, value, ttl) overloads)

◈ DIAGRAM

TTLCache(capacity: int, default_ttl: float, clock=time.monotonic)
get(key) -> value or None
put(key, value, ttl=None) -> evicted key or None
size() -> int

clock is a zero-argument function returning seconds (Java: DoubleSupplier). Tests pass a fake clock so time is under their control. Never call time.time() directly inside the class.

Rules

An entry written at time t with TTL d is alive while now < t + d. At exactly t + d it is expired.
get on an expired entry removes it and returns None. A successful get marks the entry most recently used.
put on an existing key replaces the value, resets its expiry, and marks it most recently used. It never evicts.
put on a new key when the cache is full must first drop expired entries. Only if the cache is still full does it evict the least recently used live entry. It returns that evicted key. Removing expired entries does not count as an eviction.
size() counts live entries only.
capacity < 1 or a TTL <= 0 raises ValueError (Java IllegalArgumentException).

In the examples, t= is the fake clock's value when the call runs. Outputs are the return values of the calls after the constructor, in order.

Examples

Example 1

Input: t=0 c = TTLCache(capacity=2, default_ttl=10) t=0 c.put("a", 1) t=0 c.put("b", 2, ttl=3) t=4 c.get("b") t=4 c.size() t=4 c.put("c", 3) t=4 c.get("a") t=4 c.put("d", 4) t=10 c.get("a") t=10 c.size()

Output: null null null 1 null 1 c null 1

Explanation: "b" expired at t=3. At t=4 the cache holds "a" and "c", neither expired, and "a" was just read, so "d" evicts "c". At t=10 "a" reaches its expiry.

Example 2

Input: t=0 c = TTLCache(capacity=2, default_ttl=10) t=0 c.put("a", 1, ttl=5) t=0 c.put("b", 2, ttl=50) t=6 c.put("c", 3) t=6 c.get("b") t=6 c.size()

Output: null null null 2 2

Explanation: "b" is the least recently used entry, but "a" is already expired, so dropping "a" makes room and nothing is evicted.

Hints

Approach

Optimal

Keep two views of the same entries:

An ordered map in recency order, for LRU eviction and O(1) lookup. Since you built the linked list by hand in the previous problem, OrderedDict / LinkedHashMap(accessOrder=true) is fine here. Say that to the interviewer.
A min-heap of (expires_at, seq, key), for finding expired entries in order.

Each map entry stores (value, expires_at, seq). seq is a counter bumped on every write.

get: if the entry's expires_at <= now, delete it and return None (lazy expiry). Otherwise move it to the recent end and return the value.
put of a new key into a full cache: pop heap entries whose time has passed. For each, delete the map entry only if its seq still matches, because an overwritten key leaves a stale heap record. If the cache is still full, pop the least recently used entry.
Write the entry with a new seq, push it onto the heap, and mark it most recent.
size() purges expired entries first, so it never counts dead data.

Every heap entry is pushed once and popped at most once, so purging costs O(log n) amortised per write.

ComplexityTime O(log n) amortised per put, O(1) per getSpace O(n) (heap may hold stale records until popped)

Python

import heapq
import itertools
import time
from collections import OrderedDict
 
 
class TTLCache:
    def __init__(self, capacity, default_ttl, clock=time.monotonic):
        if capacity < 1:
            raise ValueError("capacity must be at least 1")
        if default_ttl <= 0:
            raise ValueError("ttl must be positive")
        self.capacity = capacity
        self.default_ttl = default_ttl
        self.clock = clock
        self.data = OrderedDict()        # key -> (value, expires_at, seq); last = most recent
        self.expiry = []                 # min-heap of (expires_at, seq, key)
        self.seq = itertools.count()
 
    def _alive(self, entry, now):
        return now < entry[1]
 
    def _purge_expired(self, now):
        while self.expiry and self.expiry[0][0] <= now:
            expires_at, seq, key = heapq.heappop(self.expiry)
            entry = self.data.get(key)
            if entry is not None and entry[2] == seq:   # skip stale heap entries
                del self.data[key]
 
    def get(self, key):
        entry = self.data.get(key)
        if entry is None:
            return None
        if not self._alive(entry, self.clock()):
            del self.data[key]           # its heap entry becomes stale
            return None
        self.data.move_to_end(key)
        return entry[0]
 
    def put(self, key, value, ttl=None):
        """Insert or update. Returns the key evicted for space, or None."""
        ttl = self.default_ttl if ttl is None else ttl
        if ttl <= 0:
            raise ValueError("ttl must be positive")
        now = self.clock()
        evicted = None
        if key not in self.data and len(self.data) >= self.capacity:
            self._purge_expired(now)                  # free space from dead entries first
            if len(self.data) >= self.capacity:
                evicted, _ = self.data.popitem(last=False)   # then the least recently used
        seq = next(self.seq)
        self.data[key] = (value, now + ttl, seq)
        self.data.move_to_end(key)
        heapq.heappush(self.expiry, (now + ttl, seq, key))
        return evicted
 
    def size(self):
        self._purge_expired(self.clock())
        return len(self.data)

Follow-up questions

Add a delete(key) method. What happens to its heap entry?
Refresh-ahead: serve the stale value once and trigger a background reload instead of returning a miss.
Make it thread-safe without one global lock (sharding by key hash).

Frequently asked questions

You can add one, but it does not replace the lazy checks: between sweeps a reader could still see a dead entry, so get must check expiry anyway. A sweeper also brings locking and shutdown concerns. The lazy design is correct on its own, and a periodic purge is only an optimisation to return memory from keys nobody reads again.

In Go: a map[K]*list.Element with container/list for recency and container/heap over a slice of expiry records, all behind one sync.Mutex. Take a func() time.Time (or a small Clock interface) in the constructor so tests can control time. Production caches often add jitter to TTLs so a batch of entries loaded together does not expire at the same moment and stampede the backend. They also export a metric for expirations separate from evictions.

Tests become deterministic and fast: you set the clock to 10 instead of sleeping for 10 seconds. Use a monotonic clock in production, because wall-clock time can jump backwards on an NTP correction and suddenly make every entry look fresh or expired.

Problem statement