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 round

Requirements

  • Functional: get/put with per-entry TTL, lazy expiry, LRU eviction at capacity, updating a key resets its TTL.
  • Non-functional: get must 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 expires

Rules. 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
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

3 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. RecruiterCharacter joke · No posting date

    We loved your energy. We went with the candidate whose code compiled.

  2. TryGetValueCharacter joke · No posting date

    My solution passed all the tests. All zero of them. I forgot to run them.

  3. TryGetValueCharacter joke · No posting date

    I solved this in O(1). Then I remembered I actually have to write the code. O(n) regrets.