Design a Cache (LRU/LFU)

Design a fixed-size, thread-safe cache supporting O(1) get/put with pluggable LRU and LFU eviction — the classic data-structure-heavy LLD problem.

August 11, 2026

lldcacheLRULFUthread-safetyeviction

Design a Cache (LRU/LFU)

Unlike most LLD problems, which are dominated by class modeling, this one is dominated by data structure design: getting get() and put() to both run in O(1) is the entire interview. The class design around it (a pluggable eviction policy, thread safety, TTL) is what separates a "I memorized LRU" answer from a design that could plausibly back a real service like a CDN edge cache or an in-process query cache.

1. Requirements

Functional requirements

Fixed maximum capacity, set at construction.
get(key) returns the value or a sentinel/null/Optional.empty() if absent — O(1).
put(key, value) inserts or updates a value — O(1). If at capacity, evicts one entry per the configured policy first.
Support two eviction policies, selectable at construction: LRU (evict the least-recently-used, where both get and put count as "use") and LFU (evict the least-frequently-used; ties broken by least-recently-used among equal frequency).
Optional: TTL per entry — an entry is treated as absent once expired, even if still physically present.
Expose cache statistics: hit count, miss count, hit rate, eviction count.

Non-functional requirements

Both operations O(1) amortized — this is graded explicitly; an O(log n) heap-based LFU is a partial-credit answer, not a full one.
Thread-safe under concurrent get/put from multiple threads.
Bounded memory: the cache must never grow past its configured capacity even transiently (aside from brief eviction bookkeeping).
Eviction should be observable (a caller can be notified which key was evicted, e.g. to also evict it from a write-behind store).

Out of scope: distributed/multi-node cache coherence (that's a distributed-systems problem, not an LLD one — see a "Design Redis" or "Design a Distributed Cache" system-design question for that layer), persistence to disk.

2. Actors & Use Cases

Actors

Client code — calls get/put (e.g., a service layer caching DB query results).
Eviction listener — optionally notified when an entry is evicted (for write-back or cleanup).
Background reaper (only if using active TTL expiration) — periodically sweeps expired entries.

Primary use cases

Client calls put("user:42", user) on an empty-enough cache → entry inserted, no eviction.
Cache is full; client calls put("user:99", user) → the eviction policy selects a victim, removes it (optionally notifying a listener), inserts the new entry.
Client calls get("user:42") → cache hit; for LRU, this entry becomes "most recently used"; for LFU, its frequency counter increments.
Client calls get("user:404") → cache miss, null/Optional.empty() returned, miss counter increments.
An entry's TTL expires; the next get on it treats it as a miss and physically removes it (lazy expiration), or a background reaper removes it proactively.

3. Class Diagram

4. Core Class Design

Common interface

java

public interface Cache<K, V> {
    V get(K key);
    void put(K key, V value);
    void remove(K key);
    int size();
    CacheStats stats();
}
 
public final class CacheStats {
    private final AtomicLong hits = new AtomicLong();
    private final AtomicLong misses = new AtomicLong();
    private final AtomicLong evictions = new AtomicLong();
 
    void recordHit() { hits.incrementAndGet(); }
    void recordMiss() { misses.incrementAndGet(); }
    void recordEviction() { evictions.incrementAndGet(); }
 
    public double hitRate() {
        long h = hits.get(), m = misses.get();
        return (h + m) == 0 ? 0.0 : (double) h / (h + m);
    }
    public long hits() { return hits.get(); }
    public long misses() { return misses.get(); }
    public long evictions() { return evictions.get(); }
}
 
public interface EvictionListener<K, V> {
    void onEvict(K key, V value);
}

LRU — HashMap + doubly linked list, from scratch

Implementing this manually (rather than subclassing LinkedHashMap with accessOrder=true, which is the one-liner shortcut) is what interviewers actually want to see, since it proves you understand why the combination gives O(1):

java

public final class LRUCache<K, V> implements Cache<K, V> {
    private final int capacity;
    private final Map<K, Node<K, V>> index = new HashMap<>();
    private final Node<K, V> head = new Node<>(null, null); // sentinel: most-recent side
    private final Node<K, V> tail = new Node<>(null, null); // sentinel: least-recent side
    private final CacheStats stats = new CacheStats();
    private EvictionListener<K, V> listener;
 
    public LRUCache(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }
 
    public synchronized V get(K key) {
        Node<K, V> node = index.get(key);
        if (node == null || isExpired(node)) {
            stats.recordMiss();
            return null;
        }
        stats.recordHit();
        moveToFront(node);
        return node.value;
    }
 
    public synchronized void put(K key, V value) {
        Node<K, V> existing = index.get(key);
        if (existing != null) {
            existing.value = value;
            moveToFront(existing);
            return;
        }
        if (index.size() >= capacity) {
            evictLeastRecentlyUsed();
        }
        Node<K, V> node = new Node<>(key, value);
        index.put(key, node);
        addToFront(node);
    }
 
    public synchronized void remove(K key) {
        Node<K, V> node = index.remove(key);
        if (node != null) unlink(node);
    }
 
    public synchronized int size() { return index.size(); }
    public CacheStats stats() { return stats; }
 
    // --- doubly linked list helpers, all O(1) ---
 
    private void addToFront(Node<K, V> node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
 
    private void unlink(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
 
    private void moveToFront(Node<K, V> node) {
        unlink(node);
        addToFront(node);
    }
 
    private void evictLeastRecentlyUsed() {
        Node<K, V> victim = tail.prev; // sentinel-adjacent = actual least-recent node
        unlink(victim);
        index.remove(victim.key);
        stats.recordEviction();
        if (listener != null) listener.onEvict(victim.key, victim.value);
    }
 
    private boolean isExpired(Node<K, V> node) {
        return node.expiresAt != 0 && System.nanoTime() > node.expiresAt;
    }
 
    static final class Node<K, V> {
        K key; V value;
        long expiresAt;
        Node<K, V> prev, next;
        Node(K key, V value) { this.key = key; this.value = value; }
    }
}

LFU — HashMap + frequency buckets, each bucket a doubly linked list

java

public final class LFUCache<K, V> implements Cache<K, V> {
    private final int capacity;
    private final Map<K, Node<K, V>> index = new HashMap<>();
    private final Map<Integer, LinkedHashSet<K>> freqBuckets = new HashMap<>(); // insertion order = recency within a frequency
    private int minFrequency = 0;
    private final CacheStats stats = new CacheStats();
 
    public LFUCache(int capacity) { this.capacity = capacity; }
 
    public synchronized V get(K key) {
        Node<K, V> node = index.get(key);
        if (node == null) { stats.recordMiss(); return null; }
        stats.recordHit();
        touch(node);
        return node.value;
    }
 
    public synchronized void put(K key, V value) {
        if (capacity <= 0) return;
        Node<K, V> existing = index.get(key);
        if (existing != null) {
            existing.value = value;
            touch(existing);
            return;
        }
        if (index.size() >= capacity) {
            evictMinFrequency();
        }
        Node<K, V> node = new Node<>(key, value);
        index.put(key, node);
        freqBuckets.computeIfAbsent(1, f -> new LinkedHashSet<>()).add(key);
        minFrequency = 1;
    }
 
    /** Move a key from its current frequency bucket to the next one — O(1) amortized. */
    private void touch(Node<K, V> node) {
        int freq = node.frequency;
        freqBuckets.get(freq).remove(node.key);
        if (freqBuckets.get(freq).isEmpty()) {
            freqBuckets.remove(freq);
            if (minFrequency == freq) minFrequency++; // this bucket was the global minimum
        }
        node.frequency++;
        freqBuckets.computeIfAbsent(node.frequency, f -> new LinkedHashSet<>()).add(node.key);
    }
 
    private void evictMinFrequency() {
        LinkedHashSet<K> bucket = freqBuckets.get(minFrequency);
        K victim = bucket.iterator().next(); // least-recently-inserted within the min-frequency bucket = tie-break by LRU
        bucket.remove(victim);
        if (bucket.isEmpty()) freqBuckets.remove(minFrequency);
        index.remove(victim);
        stats.recordEviction();
    }
 
    public synchronized void remove(K key) {
        Node<K, V> node = index.remove(key);
        if (node != null) freqBuckets.getOrDefault(node.frequency, new LinkedHashSet<>()).remove(key);
    }
 
    public synchronized int size() { return index.size(); }
    public CacheStats stats() { return stats; }
 
    static final class Node<K, V> {
        K key; V value; int frequency = 0;
        Node(K key, V value) { this.key = key; this.value = value; }
    }
}

✅

The LFU trick that makes this O(1) instead of the naive O(log n) heap approach: since a get/put can only ever increment a frequency by exactly 1, minFrequency only ever needs to increase by checking "did I just empty the bucket that held the global minimum?" — never a full rescan. This is the detail interviewers probe for specifically.

5. Design Patterns Applied

Pattern	Where used	Why
Strategy	`Cache<K,V>` interface with `LRUCache`/`LFUCache` implementations	Eviction policy is an interchangeable algorithm behind one interface; client code depends only on `Cache`.
Factory Method	`CacheFactory.createLRU(capacity)` / `createLFU(capacity)`	Hides construction details and lets the caller request a policy by name instead of `new`-ing a concrete class.
Observer	`EvictionListener` notified on `onEvict`	Decouples the cache from whatever needs to react to eviction (e.g., a write-behind store flushing the evicted value).
Sentinel node (structural idiom, not GoF, but interview-relevant)	`head`/`tail` dummy nodes in the linked list	Eliminates null checks for "is this the first/last real node" on every insert/remove.
Decorator (extension)	Wrapping a `Cache` with a `TtlCache` or `MetricsCache` decorator	Adds TTL enforcement or metrics export without modifying `LRUCache`/`LFUCache` internals.

6. Key Algorithms, Concurrency & Edge Cases

Why HashMap + doubly linked list gives O(1) LRU

A HashMap<K, Node> gives O(1) lookup by key but has no notion of order. A plain linked list gives O(1) removal/insertion at an end if you already hold a reference to the node, but O(n) lookup by key. Combining them — the map's value is a reference directly into the list — gets O(1) for both: the map finds the node instantly, the list reorders it instantly because no scan is needed to find it. This "index into a positional structure" combination recurs constantly in LLD (it's the same idea behind LFU's frequency buckets, and behind indexing structures generally).

Thread safety: lock granularity trade-off

The reference implementations above use synchronized on every method — coarse-grained but simple and correct, since even a get() mutates internal state (recency/frequency), so it cannot be a pure read.

java

// A ReadWriteLock does NOT help LRU/LFU the way it helps a typical read-heavy cache,
// because get() itself writes (reorders the linked list / bumps frequency).
// A striped-lock (e.g., partition the keyspace into N segments, each with its own lock,
// à la ConcurrentHashMap's historical segment locking) is the real scalability lever:
public final class StripedLRUCache<K, V> implements Cache<K, V> {
    private final LRUCache<K, V>[] segments;
    private final int segmentCount;
 
    @SuppressWarnings("unchecked")
    public StripedLRUCache(int totalCapacity, int segmentCount) {
        this.segmentCount = segmentCount;
        this.segments = new LRUCache[segmentCount];
        for (int i = 0; i < segmentCount; i++) {
            segments[i] = new LRUCache<>(totalCapacity / segmentCount);
        }
    }
 
    private LRUCache<K, V> segmentFor(K key) {
        return segments[Math.floorMod(key.hashCode(), segmentCount)];
    }
 
    public V get(K key) { return segmentFor(key).get(key); }
    public void put(K key, V value) { segmentFor(key).put(key, value); }
    public void remove(K key) { segmentFor(key).remove(key); }
    public int size() { return Arrays.stream(segments).mapToInt(LRUCache::size).sum(); }
    public CacheStats stats() { throw new UnsupportedOperationException("aggregate across segments"); }
}

Striping trades perfect global LRU ordering (eviction is now "least-recently-used within a segment," not globally) for much lower lock contention — the same trade Java's own ConcurrentHashMap historically made, and a trade worth naming explicitly as intentional, not accidental.

TTL support: lazy vs. active expiration

Lazy expiration (shown in LRUCache.get() via isExpired): cheap, no background thread, but a dead entry that's never get-accessed again occupies a capacity slot forever until evicted by the normal policy.
Active expiration: a background reaper thread periodically scans for expired entries and removes them, bounding memory more tightly at the cost of a periodic sweep and extra synchronization contention with foreground get/put calls. Production caches (Guava, Caffeine) do both: lazy check on access, plus a lightweight periodic sweep.

Edge cases

capacity == 0: put should be a no-op, not throw — guarded explicitly in LFUCache.put above.
Update of an existing key: must not double-count as a new insertion for eviction purposes, and for LRU must still refresh recency (handled by the existing != null branch in both implementations).
Eviction tie-breaking in LFU: multiple keys can share the minimum frequency; the design above breaks ties by least-recently-inserted-into-that-bucket (a LinkedHashSet per frequency), which is the standard LFU-with-LRU-tiebreak semantics.
Negative/null values: decide explicitly whether null is a valid cached value (meaning get must distinguish "miss" from "cached null") — an Optional<V> return type sidesteps the ambiguity at the cost of an extra wrapper allocation per call.

7. Trade-offs & Extensions

Decision	Trade-off
LRU vs LFU	LRU is simpler and works well for recency-biased access patterns; LFU protects "classic" hot items from being evicted by a burst of one-time reads (a scan), at higher bookkeeping cost.
Coarse `synchronized` vs. striped locking	Coarse: simple, globally-correct ordering, but a contention bottleneck under high concurrency. Striped: scales better, sacrifices exact global ordering.
Manual doubly-linked-list vs. `LinkedHashMap(accessOrder=true)`	`LinkedHashMap` is fewer lines and is genuinely O(1), but hides the mechanism — most interviewers want the manual version to confirm understanding; production code reasonably uses the built-in.
Lazy vs. active TTL expiration	Lazy is simpler and has zero background overhead; active bounds memory more tightly for entries that are written once and never re-read.

Natural extensions:

W-TinyLFU / ARC: hybrid eviction policies (used by Caffeine) that combine recency and frequency signals better than pure LRU or pure LFU — worth naming if the interviewer pushes on "how would you do better than LRU."
Write-through / write-behind: cache as the primary access path with a backing store synced either synchronously on put or asynchronously via the EvictionListener.
Distributed cache: sharding this same Cache<K,V> across nodes with consistent hashing turns this LLD design into the building block for a system-design-level distributed cache.
Size-based (not count-based) capacity: evict based on total byte size of cached values rather than entry count, useful when values vary wildly in size.

Interview Questions

Why does combining a HashMap with a doubly linked list give O(1) for both get and put in LRU, when neither structure alone achieves that?
Walk through what happens, step by step, when get() is called on an LFU cache — which structures are touched and in what order?
Why doesn't a ReadWriteLock help LRU/LFU the way it helps a typical cache, and what's a better concurrency strategy?
How would you support TTL per entry without breaking the O(1) guarantee for get/put?
What's the tie-breaking rule when multiple keys share the minimum frequency in LFU, and how is it implemented?
How would striping the keyspace across multiple internal LRU segments affect eviction correctness, and why might that be an acceptable trade-off?
If asked to design something better than plain LRU for a production cache, what would you propose and why?

Design an ATM

Design a Rate Limiter