Code an LRU cache

In one minute

• An LRU cache holds at most N entries and, when full, evicts the one that was used least recently. The interview goal is get and put in O(1) time, and code that stays correct at the edges.
• The standard design pairs a hash map (key to node, for O(1) lookup) with a doubly linked list (nodes in recency order, for O(1) move and remove). Each structure alone is too slow at one of the two jobs.
• Sentinel head and tail nodes remove every "is this the first or last node" branch, which is where most hand-written versions break.
• TTL is a second, independent reason to drop an entry. Inject the clock so expiry is testable, and check expiry lazily on read.
• A read on an LRU is also a write (it moves a node), so concurrent LRUs need a lock on every get. That one fact explains why Redis samples, why Caffeine buffers reads and why big caches shard.

Requirements

Functional

• get(key) returns the value and marks the key most recently used, or reports a miss.
• put(key, value, ttl) inserts or updates. Updating an existing key marks it most recently used and does not grow the cache.
• When a put adds a new key to a full cache, the least recently used entry is evicted first.
• Optional per-entry TTL: an entry older than its TTL is never returned. A TTL of zero (or none) means no expiry.
• delete(key), a size, and the keys in recency order for debugging and tests.

Non-functional

• get, put and delete in O(1) average time; memory O(capacity).
• Deterministic and testable: no direct reads of the wall clock.
• Safe for concurrent use in the Go version.

Out of scope

• Distribution across machines (see the distributed cache lesson), persistence, size-in-bytes weighting and loaders. Extensibility covers how they would fit.

Entities and relationships

• LRUCache: the public type. It owns the map, the list, the capacity and the clock.
• Node: key, value, expiry time, prev and next. The node stores its key so that evicting the tail can also delete the map entry in O(1).
• Recency list: a doubly linked list with two sentinels. The node after head is the most recently used; the node before tail is the least.
• Index: a hash map from key to node. It answers "is it here" and "where is it in the list".
• Clock: a function returning the current time in milliseconds. Production passes a monotonic clock; tests pass a fake one they can advance.

The cache composes one index and one list, and they always hold the same set of nodes. That invariant is what every operation must preserve: if the map and list disagree, the cache leaks memory or returns a node that is no longer linked.

Class diagram

classDiagram
    class LRUCache {
        -int capacity
        -Map index
        -Node head
        -Node tail
        -Clock clock
        +get(key) value
        +put(key, value, ttl)
        +delete(key) bool
        +size() int
        +keys() List
        -unlink(node)
        -pushFront(node)
    }
    class Node {
        +key
        +value
        +int expiresAt
        +Node prev
        +Node next
    }
    class Clock {
        <<interface>>
        +now() int
    }
    LRUCache "1" *-- "many" Node
    LRUCache ..> Clock
    Node --> Node : prev, next

Key flows

sequenceDiagram
    participant C as Caller
    participant L as LRUCache
    participant M as Index map
    participant D as Recency list
    C->>L: put("c", 3) with cache full
    L->>M: lookup "c"
    M-->>L: miss
    L->>D: lru = tail.prev
    L->>D: unlink(lru)
    L->>M: delete lru.key
    L->>D: pushFront(new node c)
    L->>M: index["c"] = node
    C->>L: get("a")
    L->>M: lookup "a"
    M-->>L: node
    L->>L: expired? compare clock.now() with expiresAt
    L->>D: unlink(node), pushFront(node)
    L-->>C: value of a

get on a hit does three things: look up, check expiry, move to front. If the entry has expired, get unlinks it, deletes it from the map and reports a miss. put on an existing key updates the value and expiry in place and moves the node to the front. put on a new key evicts first if full, then links the new node at the front. Eviction before insertion matters: inserting first briefly holds capacity + 1 entries, which breaks the invariant a test can observe.

Design patterns used and why

• Composition over inheritance. Subclassing a built-in ordered map (Python's OrderedDict, Java's LinkedHashMap with removeEldestEntry) works and is fine in production. In an interview, composing your own map and list shows you know where the O(1) comes from.
• Sentinel nodes (null object). Dummy head and tail mean every real node always has a non-null prev and next. unlink and pushFront become four pointer writes with no branches.
• Dependency injection for the clock. The cache never calls the system time. Tests advance a fake clock across an expiry boundary in microseconds, with no sleeps and no flakiness.
• Strategy for eviction (extension point). LRU is one policy. Hiding "which node to evict next" behind an interface lets you swap in LFU or a segmented LRU without touching the API.
• Decorator. Memoisation (functools.lru_cache) wraps a function with this exact structure. The cache is the mechanism; the decorator is the delivery.

Concurrency and edge cases

• Reads mutate. get relinks a node. Two goroutines calling get without a lock can corrupt the list (a node whose prev.next no longer points to it). A read-write lock does not help, because a hit needs the write side. Use a plain sync.Mutex, as the Go solution does.
• Lock scope. Hold the lock for the map and list work only. Never call user code (a loader, an eviction callback) while holding it, or a slow callback stalls every reader.
• Capacity of zero or less. Reject it at construction. A cache of capacity zero would evict the item it just inserted, which is almost always a configuration bug.
• Updating a key. Must not count as a new entry, and must reset the TTL. Forgetting either is the most common test failure.
• Expiry boundary. Decide whether an entry is dead at exactly expiresAt. This design treats now >= expiresAt as expired, so a TTL of 100 ms gives exactly 100 ms of life.
• Expired but not evicted. Lazy expiry means dead entries can occupy slots until touched or until they reach the tail. That is a deliberate trade: O(1) operations instead of a background sweep. Redis and Memcached combine lazy checks with a periodic sampler for the same reason.
• Clock going backwards. Use a monotonic clock in production. A wall clock adjusted by NTP can make entries live longer or die early.

Down the stack

Extensibility

• Weighted capacity. Replace the entry count with a byte budget. put evicts from the tail until the new entry fits, and refuses entries larger than the whole budget.
• Eviction listener. Call a callback with the evicted key and value, after releasing the lock, so callers can close file handles or write back dirty data.
• Loader with single-flight. get_or_load(key, fn) runs fn once per missing key even if 100 callers ask at the same moment. This prevents a stampede on the backing store after a mass expiry.
• Better policies. LRU loses to a single large scan: one pass over cold keys flushes the hot set. Segmented LRU or W-TinyLFU (Caffeine) keeps a frequency sketch and admits new keys only if they are likely to be hit again.
• Sharding. Hash keys into 16 or 64 independent caches, each with its own mutex. Recency becomes per-shard, which is a fine approximation in practice.

Leadership lens

• Measure before tuning. Ask for hit ratio, eviction rate and p99 latency per cache before anyone debates policies. Most "cache problems" are a capacity or TTL setting.
• Prefer the library. Production code should usually use functools.lru_cache, Caffeine, Ristretto or a well-tested package. Hand-rolled caches are where subtle concurrency bugs live; reserve them for when a measured need exists.
• TTL is a correctness setting. A TTL decides how stale data can be. The owning product team should set it with the data's owner, not leave a default someone copied.
• Stampedes are an availability risk. In design review, ask what happens to the database when the cache restarts empty or a popular key expires. Require single-flight or staggered expiry for anything hot.

Check yourself

1. Why does the node store its key when the map already maps key to node?

   Show answer

   Eviction starts from the list tail, not from a key. To delete the evicted node from the map in O(1), you need its key on the node.

2. Why does a read-write lock not speed up a concurrent LRU?

   Show answer

   A get hit moves the node to the front, which mutates shared pointers. Every hit therefore needs the exclusive lock, so readers never run in parallel.

3. A TTL of 100 ms is set at time 0. Is the entry returned at time 100 in this design?

   Show answer

   No. Entries are expired when now >= expiresAt, so the entry lives during [0, 100) and is gone at 100.

4. What workload makes LRU perform badly, and what fixes it?

   Show answer

   A one-off scan over many cold keys pushes out the hot working set. Segmented LRU or frequency-aware admission such as W-TinyLFU protects frequently used keys.

Watch

• LRU Cache, Leetcode 146 (NeetCode): a clear walk through the hash map plus doubly linked list solution with sentinel nodes.

Free resources

• Cache replacement policies (Wikipedia): LRU alongside CLOCK, LFU, ARC, SLRU and others, with the trade-offs of each.
• Key eviction (Redis docs): how Redis approximates LRU and LFU with sampling and what the policies mean.
• Caffeine design (Ben Manes): read buffers, W-TinyLFU admission and how a high-throughput concurrent cache avoids the LRU lock.
• groupcache lru.go (Go): a compact production LRU built on a map and container/list.
• functools.lru_cache (Python docs): the standard library memoising LRU and its options.
• Multi-Gen LRU (Linux kernel docs): how the kernel approximates LRU for page reclaim at scale.