LLD Series: LRU / LFU Cache (Low-Level Design)

Overview

1. Problem statement and how it is asked
2. Requirements clarification
3. Entities and class diagram
4. Design patterns and why
5. Code
6. Key flows
7. Extensibility
8. Concurrency and edge cases
9. Follow-ups and model answers
10. Common mistakes and rubric

Part of the Interview Prep series. Dotted-underline words are glossary terms: hover for the meaning or open the Glossary. Track your progress on the Interview Prep tracker. Series index: Start here.

1. Problem statement and how it is asked

"Design and implement an LRU cache with O(1) get and put. Then: make it thread-safe, support TTL, make it generic, and support LFU as well (pluggable eviction)."

Phrasings: "LeetCode 146/460 but as a class design", "Design an in-memory cache like Guava/Caffeine", "cache BIN/merchant/config lookups". Asked heavily at Visa, Mastercard, NPCI, Amex, PayU (reference-data caches: BIN tables, VPA to account lookups, merchant configs, token vaults metadata). Commonly a warm-up (15 min) that is then extended to 60 min with Strategy + concurrency + TTL.

2. Requirements clarification

Functional

get(key), put(key, value), remove(key), size(); fixed capacity; on full insert, evict one entry.
Eviction policy pluggable: LRU, LFU (extensible to FIFO, MRU, random).
Optional TTL (default and per-entry).
Generic <K, V>; get returns Optional<V> (distinguishes absent from null value).

Non-functional

O(1) get/put/evict for both policies.
Thread-safe variant; hit/miss/eviction stats.

Assumptions / out of scope

In-memory single JVM; no write-through/loader (computeIfAbsent, cache stampede discussed in follow-ups), no size-by-bytes weight, no async refresh.
Null keys/values disallowed for simplicity.

3. Entities and class diagram

        +------------------------+            +--------------------------+
        | <<interface>> Cache<K,V>|<-----------| PolicyCache<K,V>         |
        | get/put/put(ttl)/remove |  implements| - capacity, defaultTtl   |
        | size                    |            | - Map<K,Entry<V>> map    |
        +------------------------+            | - ReentrantLock lock     |
                                              | - LongSupplier clock     |
                                              +------------+-------------+
                                                           | has-a (Strategy)
                                              +------------v-------------+
                                              | <<interface>>            |
                                              | EvictionPolicy<K>        |
                                              | onInsert/onAccess/       |
                                              | onRemove/evict           |
                                              +------^-------------^-----+
                                                     |             |
                                      +--------------+--+   +------+------------+
                                      |LRUEvictionPolicy|   |LFUEvictionPolicy  |
                                      | HashMap<K,Node> |   | Map<K,freq>       |
                                      | + doubly linked |   | Map<freq,         |
                                      |   list          |   |  LinkedHashSet<K>>|
                                      +-----------------+   | + minFreq         |
                                                            +-------------------+
 LRUCache<K,V>: standalone classic version (HashMap + DLL storing values), not thread-safe.

 LRU list:  head <-> [MRU] <-> ... <-> [LRU] <-> tail     evict = tail.prev
 LFU:  freq 1: {c}   freq 2: {b}   freq 4: {a}   minFreq=1  evict = first of bucket[minFreq]

4. Design patterns and why

Pattern	Where	Why / rejected alternative
Strategy	`EvictionPolicy`	Policy changes independently of storage/locking/TTL. Rejected: subclassing a `LRUCache`/`LFUCache` hierarchy (duplicates TTL, locking, stats).
Separation of concerns	policy tracks keys only; cache owns values + TTL	Policy classes stay tiny and unit-testable without values/locks.
Template-ish composition	`PolicyCache` orchestrates	Lock, TTL, stats written once.
Dependency injection (clock)	`LongSupplier`	Deterministic TTL tests.
Decorator (follow-up)	`StatsCache`, `LoadingCache` wrappers	Add behaviors without touching core.

Why not LinkedHashMap(accessOrder=true) with removeEldestEntry? Valid in production and worth mentioning (3 lines), but interviewers ask for the hand-rolled DLL to see you understand the structure, and it cannot do LFU.

5. Code

Compiled with javac, run on JDK; default package.

Cache.java

import java.util.Optional;
public interface Cache<K, V> {
    Optional<V> get(K key);
    void put(K key, V value);                       // default TTL
    void put(K key, V value, long ttlMillis);       // per-entry TTL
    boolean remove(K key);
    int size();
}

EvictionPolicy.java

/** Strategy: tracks key usage only (not values). Called under the cache's lock. */
public interface EvictionPolicy<K> {
    void onInsert(K key);
    void onAccess(K key);
    void onRemove(K key);
    K evict();            // choose + remove victim from policy state; null if empty
}

LRUEvictionPolicy.java

import java.util.HashMap;
import java.util.Map;

/** HashMap + hand-rolled doubly linked list with head/tail sentinels. All ops O(1). Head = MRU, tail.prev = LRU. */
public class LRUEvictionPolicy<K> implements EvictionPolicy<K> {
    private static final class Node<K> { K key; Node<K> prev, next; Node(K k) { key = k; } }
    private final Map<K, Node<K>> map = new HashMap<>();
    private final Node<K> head = new Node<>(null), tail = new Node<>(null);

    public LRUEvictionPolicy() { head.next = tail; tail.prev = head; }

    @Override public void onInsert(K key) { Node<K> n = new Node<>(key); map.put(key, n); addFirst(n); }
    @Override public void onAccess(K key) { Node<K> n = map.get(key); if (n != null) { unlink(n); addFirst(n); } }
    @Override public void onRemove(K key) { Node<K> n = map.remove(key); if (n != null) unlink(n); }
    @Override public K evict() {
        Node<K> lru = tail.prev;
        if (lru == head) return null;
        unlink(lru); map.remove(lru.key);
        return lru.key;
    }
    private void addFirst(Node<K> n) { n.next = head.next; n.prev = head; head.next.prev = n; head.next = n; }
    private void unlink(Node<K> n) { n.prev.next = n.next; n.next.prev = n.prev; }
}

LFUEvictionPolicy.java

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Map;

/**
 * O(1) LFU: key->freq, freq->LinkedHashSet(keys in insertion/access order), plus minFreq.
 * Ties on frequency are broken by LRU within that frequency (oldest first in the LinkedHashSet).
 */
public class LFUEvictionPolicy<K> implements EvictionPolicy<K> {
    private final Map<K, Integer> freq = new HashMap<>();
    private final Map<Integer, LinkedHashSet<K>> buckets = new HashMap<>();
    private int minFreq = 0;

    @Override public void onInsert(K key) {
        freq.put(key, 1);
        buckets.computeIfAbsent(1, f -> new LinkedHashSet<>()).add(key);
        minFreq = 1;                       // a new key always resets min to 1
    }
    @Override public void onAccess(K key) {
        Integer f = freq.get(key);
        if (f == null) return;
        removeFromBucket(key, f);
        if (f == minFreq && !buckets.containsKey(f)) minFreq++;
        freq.put(key, f + 1);
        buckets.computeIfAbsent(f + 1, x -> new LinkedHashSet<>()).add(key);
    }
    @Override public void onRemove(K key) {
        Integer f = freq.remove(key);
        if (f != null) removeFromBucket(key, f);   // minFreq may be stale; fixed lazily in evict()
    }
    @Override public K evict() {
        if (freq.isEmpty()) return null;
        while (!buckets.containsKey(minFreq)) minFreq++;   // only loops after explicit removes
        Iterator<K> it = buckets.get(minFreq).iterator();
        K victim = it.next();
        onRemove(victim);
        return victim;
    }
    private void removeFromBucket(K key, int f) {
        LinkedHashSet<K> s = buckets.get(f);
        s.remove(key);
        if (s.isEmpty()) buckets.remove(f);
    }
}

PolicyCache.java

import java.util.HashMap;
import java.util.Map;
import java.util.Optional;
import java.util.concurrent.locks.ReentrantLock;
import java.util.function.LongSupplier;

/**
 * Thread-safe generic cache. ONE ReentrantLock guards map + policy: even get() mutates policy
 * state (recency/frequency), so a ReadWriteLock gives no benefit. Values are never computed under lock.
 */
public class PolicyCache<K, V> implements Cache<K, V> {
    private static final class Entry<V> {
        final V value; final long expiresAt;   // Long.MAX_VALUE = never
        Entry(V v, long e) { value = v; expiresAt = e; }
    }
    private final int capacity;
    private final long defaultTtlMs;           // <=0 => no expiry
    private final EvictionPolicy<K> policy;
    private final LongSupplier clock;
    private final Map<K, Entry<V>> map = new HashMap<>();
    private final ReentrantLock lock = new ReentrantLock();
    private long hits, misses, evictions;

    public PolicyCache(int capacity, EvictionPolicy<K> policy, long defaultTtlMs, LongSupplier clock) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity");
        this.capacity = capacity; this.policy = policy; this.defaultTtlMs = defaultTtlMs; this.clock = clock;
    }
    public PolicyCache(int capacity, EvictionPolicy<K> policy) { this(capacity, policy, 0, System::currentTimeMillis); }

    @Override public Optional<V> get(K key) {
        lock.lock();
        try {
            Entry<V> e = map.get(key);
            if (e == null) { misses++; return Optional.empty(); }
            if (e.expiresAt <= clock.getAsLong()) {      // lazy expiry
                map.remove(key); policy.onRemove(key); misses++;
                return Optional.empty();
            }
            policy.onAccess(key); hits++;
            return Optional.of(e.value);
        } finally { lock.unlock(); }
    }
    @Override public void put(K key, V value) { put(key, value, defaultTtlMs); }
    @Override public void put(K key, V value, long ttlMs) {
        lock.lock();
        try {
            long exp = ttlMs > 0 ? clock.getAsLong() + ttlMs : Long.MAX_VALUE;
            if (map.containsKey(key)) {                  // update counts as an access
                map.put(key, new Entry<>(value, exp)); policy.onAccess(key); return;
            }
            if (map.size() >= capacity) {
                purgeExpiredLocked();                    // prefer dropping dead entries over live ones
                if (map.size() >= capacity) { K victim = policy.evict(); map.remove(victim); evictions++; }
            }
            map.put(key, new Entry<>(value, exp)); policy.onInsert(key);
        } finally { lock.unlock(); }
    }
    /** O(n) sweep; also callable from a scheduled janitor. */
    public int purgeExpired() { lock.lock(); try { return purgeExpiredLocked(); } finally { lock.unlock(); } }
    private int purgeExpiredLocked() {
        long now = clock.getAsLong(); int n = 0;
        for (java.util.Iterator<Map.Entry<K, Entry<V>>> it = map.entrySet().iterator(); it.hasNext();) {
            Map.Entry<K, Entry<V>> en = it.next();
            if (en.getValue().expiresAt <= now) { it.remove(); policy.onRemove(en.getKey()); n++; }
        }
        return n;
    }
    @Override public boolean remove(K key) {
        lock.lock();
        try { if (map.remove(key) == null) return false; policy.onRemove(key); return true; }
        finally { lock.unlock(); }
    }
    @Override public int size() { lock.lock(); try { return map.size(); } finally { lock.unlock(); } }
    public String stats() { lock.lock(); try { return "hits=" + hits + " misses=" + misses + " evictions=" + evictions; } finally { lock.unlock(); } }
}

LRUCache.java

import java.util.HashMap;
import java.util.Map;

/** The classic 15-minute interview version: values live in the nodes, no Strategy. NOT thread-safe. */
public class LRUCache<K, V> {
    private class Node { K k; V v; Node prev, next; Node(K k, V v) { this.k = k; this.v = v; } }
    private final int cap;
    private final Map<K, Node> map = new HashMap<>();
    private final Node head = new Node(null, null), tail = new Node(null, null);

    public LRUCache(int cap) { this.cap = cap; head.next = tail; tail.prev = head; }

    public V get(K k) {
        Node n = map.get(k);
        if (n == null) return null;
        unlink(n); addFirst(n);
        return n.v;
    }
    public void put(K k, V v) {
        Node n = map.get(k);
        if (n != null) { n.v = v; unlink(n); addFirst(n); return; }
        if (map.size() == cap) { Node lru = tail.prev; unlink(lru); map.remove(lru.k); }
        n = new Node(k, v); map.put(k, n); addFirst(n);
    }
    private void addFirst(Node n) { n.next = head.next; n.prev = head; head.next.prev = n; head.next = n; }
    private void unlink(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
}

Main.java

import java.util.concurrent.*;
import java.util.concurrent.atomic.*;

public class Main {
    static final AtomicLong now = new AtomicLong(0);

    public static void main(String[] args) throws Exception {
        System.out.println("== Classic LRUCache(2)");
        LRUCache<Integer, String> c = new LRUCache<>(2);
        c.put(1, "one"); c.put(2, "two"); c.get(1); c.put(3, "three");
        System.out.println("get(2) after put(3) (2 was LRU) = " + c.get(2) + ", get(1) = " + c.get(1));

        System.out.println("== PolicyCache + LRU (cap 3)");
        PolicyCache<String, Integer> lru = new PolicyCache<>(3, new LRUEvictionPolicy<>());
        lru.put("a", 1); lru.put("b", 2); lru.put("c", 3);
        lru.get("a");                       // order now: a, c, b  (b is LRU)
        lru.put("d", 4);
        System.out.println("b evicted? " + !lru.get("b").isPresent() + "; a present? " + lru.get("a").isPresent() + "; " + lru.stats());

        System.out.println("== PolicyCache + LFU (cap 3)");
        PolicyCache<String, Integer> lfu = new PolicyCache<>(3, new LFUEvictionPolicy<>());
        lfu.put("a", 1); lfu.put("b", 2); lfu.put("c", 3);
        lfu.get("a"); lfu.get("a"); lfu.get("b");      // freq a=3 b=2 c=1
        lfu.put("d", 4);                               // evicts c
        System.out.println("c evicted? " + !lfu.get("c").isPresent() + "; a,b,d present? "
            + lfu.get("a").isPresent() + "," + lfu.get("b").isPresent() + "," + lfu.get("d").isPresent());
        lfu.put("e", 5);                               // d freq2(after get) vs e freq1 -> evict e? e is new; victim = min freq among existing
        System.out.println("after put(e): d present? " + lfu.get("d").isPresent() + ", size=" + lfu.size());

        System.out.println("== TTL (default 100ms, fake clock)");
        PolicyCache<String, String> ttl = new PolicyCache<>(2, new LRUEvictionPolicy<>(), 100, now::get);
        ttl.put("k", "v"); ttl.put("long", "v2", 1000);
        now.set(50);  System.out.println("t=50  k=" + ttl.get("k").orElse("<expired>"));
        now.set(150); System.out.println("t=150 k=" + ttl.get("k").orElse("<expired>") + ", long=" + ttl.get("long").orElse("<expired>") + ", size=" + ttl.size());

        System.out.println("== Concurrency: 16 threads x 50k ops, cap 100");
        PolicyCache<Integer, Integer> cc = new PolicyCache<>(100, new LFUEvictionPolicy<>());
        ExecutorService ex = Executors.newFixedThreadPool(16);
        CountDownLatch done = new CountDownLatch(16);
        for (int t = 0; t < 16; t++) ex.submit(() -> {
            ThreadLocalRandom r = ThreadLocalRandom.current();
            for (int i = 0; i < 50_000; i++) { int k = r.nextInt(500); if (cc.get(k).isPresent() == false) cc.put(k, k); }
            done.countDown();
        });
        done.await(); ex.shutdown();
        System.out.println("size<=100? " + (cc.size() <= 100) + " size=" + cc.size() + " " + cc.stats().replaceAll("\\d+", "N"));
    }
}

Real output (javac -d out *.java && java -cp out Main)

== Classic LRUCache(2)
get(2) after put(3) (2 was LRU) = null, get(1) = one
== PolicyCache + LRU (cap 3)
b evicted? true; a present? true; hits=2 misses=1 evictions=1
== PolicyCache + LFU (cap 3)
c evicted? true; a,b,d present? true,true,true
after put(e): d present? false, size=3
== TTL (default 100ms, fake clock)
t=50  k=v
t=150 k=<expired>, long=v2, size=1
== Concurrency: 16 threads x 50k ops, cap 100
size<=100? true size=100 hits=N misses=N evictions=N

Note on the LFU section: after put(d), the demo's own get(d) calls raise d to frequency 2 while a=4, b=3, so put(e) correctly evicts d (minimum frequency). The demo masks the hit/miss/eviction counts as N because they vary run to run; size is always capped at 100.

Lock granularity. One ReentrantLock for the whole cache. Reason: even get mutates shared structures (the linked list / frequency buckets), so a ReadWriteLock read lock would be incorrect, and the critical sections are O(1) and tiny. Rejected: ConcurrentHashMap + synchronized list separately (two structures can disagree: key evicted from list but still in map). For higher throughput: stripe into N segments by hash(key) % N each with its own lock/policy (capacity/N each; approximate global LRU), or use Caffeine (buffered access recording, TinyLFU).

6. Key flows

get(k)                                    put(k,v) when full, new key
 lock                                      lock
  e = map[k]                                map has k? no
  e==null -> miss                           size>=cap -> purgeExpired()  (dead entries first)
  e.expired -> map.remove, policy.onRemove  still full -> victim = policy.evict()
               miss                                          map.remove(victim)
  else policy.onAccess(k) -> hit            map.put(k, Entry(v, exp)); policy.onInsert(k)
 unlock                                    unlock

LRU.onAccess: unlink(node); addFirst(node)             O(1)
LFU.onAccess: remove from bucket[f]; if bucket empty and f==minFreq then minFreq++;
              add to bucket[f+1]                       O(1)
LFU.onInsert: bucket[1].add(k); minFreq=1

7. Extensibility

FIFO/MRU/Random/ARC/TinyLFU: implement EvictionPolicy<K>, pass into PolicyCache. No existing class changes.
Eviction listener (write-back, metrics): add Consumer<Map.Entry<K,V>> callback invoked on eviction/expiry (Observer).
Loading cache: get(k, Function<K,V> loader) decorator with per-key in-flight CompletableFuture map to prevent stampede.
Weighted capacity: replace size()>=capacity with a running weight; evict in a loop.
Background expiry: scheduled janitor calling purgeExpired(), or a DelayQueue/min-heap by expiresAt for O(log n) targeted expiry.

8. Concurrency and edge cases

Compound ops (check then evict then insert) are inside one lock, so map and policy never diverge.
Update of an existing key must not evict and must count as an access (tested path in put).
Capacity 1, capacity <= 0 (rejected), same key repeatedly.
LFU: new key must reset minFreq = 1; minFreq can go stale after explicit remove, so evict advances it lazily. Tie-break within a frequency by LRU (LinkedHashSet order).
LFU weakness: old, once-hot keys never age out (cache pollution). Fixes: frequency decay/aging, or TinyLFU/W-TinyLFU.
TTL: lazy expiry on read plus sweep when full; expired entries should not be returned and should be preferred victims over live ones. Use monotonic clock in production.
Never run the loader or listeners while holding the lock (deadlock/latency risk).
Mutable values: cache stores references; return immutable or copies for sensitive data.

9. Follow-ups and model answers

Q: Why doubly linked list, not singly? Removing an arbitrary node on access needs its predecessor in O(1); the map gives the node, prev gives the neighbor. Sentinels remove null checks.

Q: Why store key in the node? On eviction we get the tail node and must remove its key from the map.

Q: Make LFU O(1) - how? Frequency buckets (freq -> ordered set) plus minFreq; the min only needs adjusting when the min bucket empties (then it becomes f+1 on access) or on insert (reset to 1). A heap would be O(log n).

Q: Make it faster under contention? Lock striping/segmenting, or Caffeine's approach: reads write to a lock-free ring buffer and a single thread replays them into the policy; writes batched. Or thread-local caches with relaxed accuracy.

Q: Cache stampede / thundering herd? Single-flight per key: ConcurrentHashMap<K, CompletableFuture<V>>; first caller loads, others join. Add jittered TTLs and negative caching.

Q: Distributed? Cannot share a JVM map. Use Redis/Memcached with maxmemory-policy allkeys-lru|lfu (approximated sampling LRU), consistent hashing across nodes, replication for hot keys, local L1 (Caffeine) + remote L2 (Redis) with invalidation via pub/sub. Discuss consistency: TTL-bounded staleness vs explicit invalidation; write-through vs write-behind vs cache-aside (cache-aside is the usual default).

Q: Persist it? Warm-start snapshot (serialize key/value + remaining TTL) on shutdown; or append-only log as in Redis AOF. Usually not needed: caches are rebuildable; just protect the DB during cold start (rate-limit loads, pre-warm).

Q: LRU vs LFU in payments? BIN/merchant config: stable hot set, LFU or TinyLFU shines; session/recent-transaction lookups: LRU (recency).

Complexity: get/put/remove/evict O(1) average for both policies; space O(capacity). purgeExpired O(n) (only triggered when full; use a heap/timer wheel for O(log n)).

10. Common mistakes and rubric

Red flags

Using ArrayList/LinkedList.remove(Object) (O(n)) or a PriorityQueue for LRU.
Forgetting to update the map when evicting, or the list when removing from the map.
Not handling update-existing-key (duplicate nodes, wrong eviction).
synchronized on get only, or ReadWriteLock read lock around get that mutates order.
LFU with O(n) scan for min; forgetting to reset minFreq on insert.
Returning null for miss with nullable values; hardcoding Integer instead of generics.
Expired entries consuming capacity / being returned.

Mini rubric (10 pts): correct O(1) LRU with sentinels (3), Strategy separation for policies (2), O(1) LFU with minFreq (2), thread-safety reasoning (1), TTL + clock injection (1), distributed/stampede discussion (1).

Previous Blog← LLD Series: Rate Limiter (Low-Level Design)

Next BlogLLD Series: Elevator System (LLD) →