More interview problems · Chapter 26

LRU cache

Design an LRU cache with O(1) get and put: a hash map plus a doubly linked list, eviction, thread safety, TTL, and the LinkedHashMap and OrderedDict shortcuts.

IntermediateInterview priority: High70 min
On this page
  1. The problem: a cache that is slower than it should be
  2. 1. Clarify the requirements
  3. 2. The idea: two structures, each doing what it is good at
  4. 3. The class design
  5. 4. The code
  6. 5. Concurrency: a read is a write
  7. 6. TTL: expiry on top of LRU
  8. 7. Options and trade-offs
  9. 8. Extensions the interviewer will ask for
  10. When not to build this
  11. In the interview
  12. Quiz

The problem: a cache that is slower than it should be

An LRU cache (least recently used) keeps a fixed number of items and, when it is full, throws away the item that was used longest ago. It is one of the most common machine-coding questions because it fits in 45 minutes and still has a trap: the interviewer asks for get and put in O(1) time, meaning constant time however many items the cache holds.

The first attempt usually keeps the order in a list:

class NaiveLru {
    Map<String, Integer> map = new HashMap<>();
    List<String> order = new ArrayList<>();      // front = least recent
    int capacity = 1000;

    Integer get(String k) {
        if (!map.containsKey(k)) return null;
        order.remove(k);                         // O(n): searches the whole list
        order.add(k);
        return map.get(k);
    }
    void put(String k, int v) {
        if (map.size() == capacity) map.remove(order.remove(0));  // O(n): shifts every element
        map.put(k, v);
        order.add(k);                            // bug: an existing key is now in the list twice
    }
}

It works on the interviewer's three-line test and fails the follow-ups:

  • O(n) per call. order.remove(k) scans the list. With 100,000 entries, every read walks up to 100,000 strings.
  • Updating an existing key adds a duplicate to order, so the list and the map disagree.
  • Not thread-safe. Two threads calling get both modify order at once. Note that in an LRU cache a read is also a write, because it changes the order.

1. Clarify the requirements

Your turn: scope it

The interviewer says "Design an LRU cache." Write 4–5 questions you would ask before writing code, and the API you would agree on.

Compare with our answer

Questions worth asking: What is the capacity measured in, number of entries or bytes? Do get and put both need O(1)? Is it used from several threads? Should entries also expire after a time (TTL)? What should get return on a miss? May I use the standard library's ordered map?

A strong answer mentions: capacity unit (count or bytes) · O(1) for both operations · put on an existing key updates it and makes it most recent · thread safety · TTL as a possible extension · whether built-in shortcuts are allowed.

The agreed list for this page:

RequirementDetail
get(key)Returns the value or "missing", and marks the key most recently used
put(key, value)Inserts or updates; the key becomes most recently used
CapacityA fixed number of entries, set in the constructor; must be positive
EvictionWhen inserting a new key into a full cache, remove the least recently used entry first
Complexityget and put in O(1) average time
ThreadsSafe to call from many threads
ExtensionOptional time-to-live (TTL): an entry expires a fixed time after it was written

Out of scope: persistence, a distributed cache across machines, size in bytes (offered as an extension below), and statistics beyond hit and miss counters.

2. The idea: two structures, each doing what it is good at

No single standard structure gives both O(1) lookup by key and O(1) "move this item to the front". So you combine two:

  • A hash map from key to a list node: finds any entry in O(1).
  • A doubly linked list of nodes in order of use: each node knows its neighbours (prev and next), so it can be cut out and re-inserted with a few pointer writes, without searching. The front is the most recently used; the back is the next victim.

Two sentinel nodes, head and tail, are dummy nodes that hold no data and are never removed. They mean every real node always has a neighbour on both sides, so the code needs no if (node == first) special cases.

The map points into the list; the list keeps the order of use

How get and put work

OperationStepsCost
get(k) hitmap lookup → unlink node → add after headO(1)
get(k) missmap lookup returns nothingO(1)
put(k, v), key existsupdate value → unlink → add after headO(1)
put(k, v), new key, not fullnew node → add after head → map insertO(1)
put(k, v), new key, fullvictim = tail.prev → unlink → delete its key from the map → insert as aboveO(1)

"O(1) average" is honest wording: hash-map operations are constant time on average, and can degrade with many collisions.

get moves a node to the front; put on a full cache evicts tail.prev

3. The class design

The classes and their relationships

Class / typeKindResponsibility
Cache<K,V>interfaceget, put, remove, size; callers depend on this, not on the eviction policy
LruCache<K,V>classOwns the map, the list and the lock; implements LRU eviction
Node<K,V>private nested classKey, value, expiry time, prev, next
Clockinterface (LongSupplier in Java, a function in Python)Returns the current time; injected so tests control it

Why these choices, one sentence each:

  • An interface for the cache lets you swap LRU for LFU (least frequently used) or a no-op cache in tests without touching callers.
  • Node is private: callers never see list pointers, so they cannot corrupt the list.
  • An injected clock makes TTL testable: the test moves a fake clock forward 500 ms instead of sleeping.
  • Optional<V> in Java (or None in Python) makes a miss explicit. Returning -1, as the LeetCode version does, breaks as soon as -1 is a legitimate value.

4. The code

The model below has capacity, O(1) get/put/remove, optional TTL with lazy expiry (an expired entry is removed when someone reads it), hit/miss counters, one lock, and a demo that also runs eight threads against one cache. It also shows the library shortcut.

import java.util.*;
import java.util.concurrent.*;
import java.util.function.LongSupplier;

interface Cache<K, V> {
    Optional<V> get(K key);
    void put(K key, V value);
    boolean remove(K key);
    int size();
}

/** O(1) LRU cache: a hash map finds the node, a doubly linked list keeps the recency order. */
final class LruCache<K, V> implements Cache<K, V> {
    private static final class Node<K, V> {
        K key; V value; long expiresAt;          // expiresAt = Long.MAX_VALUE means "never"
        Node<K, V> prev, next;
        Node(K key, V value, long expiresAt) { this.key = key; this.value = value; this.expiresAt = expiresAt; }
    }

    private final int capacity;
    private final long ttlMillis;                // 0 = no expiry
    private final LongSupplier clock;            // injected so tests can move time
    private final Map<K, Node<K, V>> map = new HashMap<>();
    private final Node<K, V> head = new Node<>(null, null, 0);   // sentinel: most recent follows it
    private final Node<K, V> tail = new Node<>(null, null, 0);   // sentinel: least recent precedes it
    private long hits, misses, evictions;

    LruCache(int capacity) { this(capacity, 0, () -> System.nanoTime() / 1_000_000); }   // monotonic ms, unlike currentTimeMillis

    LruCache(int capacity, long ttlMillis, LongSupplier clock) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
        this.capacity = capacity; this.ttlMillis = ttlMillis; this.clock = clock;
        head.next = tail; tail.prev = head;
    }

    // ---- list helpers: each is a few pointer writes, O(1) ----
    private void unlink(Node<K, V> n) { n.prev.next = n.next; n.next.prev = n.prev; }
    private void addFront(Node<K, V> n) { n.next = head.next; n.prev = head; head.next.prev = n; head.next = n; }
    private boolean expired(Node<K, V> n) { return clock.getAsLong() >= n.expiresAt; }

    @Override public synchronized Optional<V> get(K key) {
        Node<K, V> n = map.get(key);
        if (n == null) { misses++; return Optional.empty(); }
        if (expired(n)) { unlink(n); map.remove(key); misses++; return Optional.empty(); }  // lazy expiry
        unlink(n); addFront(n);                  // a read makes it the most recently used
        hits++;
        return Optional.of(n.value);
    }

    @Override public synchronized void put(K key, V value) {
        long exp = ttlMillis > 0 ? clock.getAsLong() + ttlMillis : Long.MAX_VALUE;
        Node<K, V> n = map.get(key);
        if (n != null) {                         // update in place, then move to front
            n.value = value; n.expiresAt = exp;
            unlink(n); addFront(n);
            return;
        }
        if (map.size() == capacity) {            // full: evict the least recently used
            Node<K, V> lru = tail.prev;
            unlink(lru); map.remove(lru.key); evictions++;
        }
        n = new Node<>(key, value, exp);
        addFront(n); map.put(key, n);
    }

    @Override public synchronized boolean remove(K key) {
        Node<K, V> n = map.remove(key);
        if (n == null) return false;
        unlink(n); return true;
    }

    @Override public synchronized int size() { return map.size(); }

    synchronized List<K> keysMostRecentFirst() {
        List<K> out = new ArrayList<>();
        for (Node<K, V> n = head.next; n != tail; n = n.next) out.add(n.key);
        return out;
    }

    synchronized String stats() { return "hits=" + hits + " misses=" + misses + " evictions=" + evictions; }
}

/** The shortcut: LinkedHashMap in access order does the same job in a few lines. */
final class LinkedLru<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    LinkedLru(int capacity) { super(16, 0.75f, true); this.capacity = capacity; }   // true = access order
    @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > capacity; }
}

public class LruDemo {
    public static void main(String[] args) throws Exception {
        LruCache<String, Integer> c = new LruCache<>(3);
        c.put("a", 1); c.put("b", 2); c.put("c", 3);
        System.out.println("order:  " + c.keysMostRecentFirst());
        c.get("a");                              // a becomes most recent
        c.put("d", 4);                           // full: evicts b, the least recent
        System.out.println("after get(a), put(d): " + c.keysMostRecentFirst());
        System.out.println("get(b): " + c.get("b").map(String::valueOf).orElse("miss"));
        c.put("c", 30);                          // update moves c to the front
        System.out.println("after put(c,30): " + c.keysMostRecentFirst());
        System.out.println(c.stats());

        // TTL with a fake clock: no sleeping in tests
        long[] now = {1_000};
        LruCache<String, String> t = new LruCache<>(2, 500, () -> now[0]);
        t.put("session", "alice");
        now[0] += 499; System.out.println("ttl at 499 ms: " + t.get("session").orElse("expired"));
        now[0] += 1;   System.out.println("ttl at 500 ms: " + t.get("session").orElse("expired"));

        Map<String, Integer> lhm = new LinkedLru<>(2);
        lhm.put("x", 1); lhm.put("y", 2); lhm.get("x"); lhm.put("z", 3);
        System.out.println("LinkedHashMap version keeps: " + lhm.keySet());

        // Concurrency: 8 threads hammer a cache of 100 keys; size never exceeds capacity
        LruCache<Integer, Integer> shared = new LruCache<>(100);
        ExecutorService pool = Executors.newFixedThreadPool(8);
        List<Future<?>> fs = new ArrayList<>();
        for (int th = 0; th < 8; th++) {
            final int seed = th;
            fs.add(pool.submit(() -> {
                Random r = new Random(seed);
                for (int i = 0; i < 50_000; i++) {
                    int k = r.nextInt(500);
                    if (shared.get(k).isEmpty()) shared.put(k, k);
                }
            }));
        }
        for (Future<?> f : fs) f.get();
        pool.shutdown();
        System.out.println("after 400,000 concurrent ops: size=" + shared.size()
            + ", list length=" + shared.keysMostRecentFirst().size());
    }
}

Running the Java version prints (Python prints the same, with lists shown as ['c', 'b', 'a']):

order:  [c, b, a]
after get(a), put(d): [d, a, c]
get(b): miss
after put(c,30): [c, d, a]
hits=1 misses=1 evictions=1
ttl at 499 ms: alice
ttl at 500 ms: expired
LinkedHashMap version keeps: [x, z]
after 400,000 concurrent ops: size=100, list length=100

Trace the first lines: after a, b, c the order is c, b, a. Reading a moves it to the front (a, c, b), so when d arrives the victim is b. Updating c moves it to the front without evicting anything, because the key already existed.

The shortcuts, and why interviewers may forbid them

Both languages ship an ordered hash map that does all of this:

  • Java LinkedHashMap with accessOrder = true moves an entry to the end on every get, and calls removeEldestEntry after each insert; returning size() > capacity makes it an LRU cache in five lines.
  • Python OrderedDict has move_to_end(key) and popitem(last=False), both O(1). (functools.lru_cache is a decorator for caching function results, not a general key-value cache.)

Mention them early: "In production I would use LinkedHashMap; shall I build the structure myself?" Most interviewers say yes, build it, because the question exists to see you combine a map and a linked list. If they accept the shortcut, you finish early and spend the time on concurrency and TTL. Note that neither shortcut is thread-safe: LinkedHashMap in access order is modified by get, so reads need the lock too (Collections.synchronizedMap provides one).

5. Concurrency: a read is a write

In most maps, many readers can run at once. In an LRU cache, get moves a node, so it writes the list. Two unsynchronised get calls on neighbouring nodes interleave their pointer writes, and the list can lose a node or form a cycle; the next traversal then loops forever.

Two threads rewrite the same pointers, and the fix

RaceWhat goes wrongFix
Two gets on neighboursPointers overwritten; lost node or loopOne lock around every method, including get
get while put evictsget moves a node that put just unlinked; it comes back as a ghostSame lock: eviction and the move cannot interleave
Size check then insertTwo puts both see size < capacity; the cache ends up over capacityThe check and the insert are inside one critical section
Read-write lockLooks faster, but get needs the write lock, so readers gain nothingUse a plain lock, or a design where reads do not move nodes

The demo's eight threads do 400,000 operations and the size and the list length both end at exactly 100. Remove synchronized (or the with self._lock) and the Java version can fail with a broken list or a size above capacity. Python's global interpreter lock (GIL) makes each bytecode step atomic, but a move_to_front is many steps, so the lock is still required.

Striped LRU: one lock per shard

Lock striping means replacing one lock that guards everything with N locks that each guard a part. For a cache, each part is simply a complete, independent LruCache with its own map, list and lock. A key's hash picks its stripe, so the same key always lands in the same one, and two threads only contend when their keys hash to the same stripe. With 16 stripes and keys spread evenly, the chance that two random calls collide drops from certain to 1 in 16.

The wrapper needs no lock of its own, because it holds no shared mutable state: the list of stripes never changes after construction.

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

/** N independent LRU caches, each with its own lock; a key always maps to the same stripe. */
final class StripedLruCache<K, V> implements Cache<K, V> {
    private final List<LruCache<K, V>> stripes = new ArrayList<>();

    StripedLruCache(int capacity, int stripeCount) {
        int perStripe = (capacity + stripeCount - 1) / stripeCount;   // round up
        for (int i = 0; i < stripeCount; i++) stripes.add(new LruCache<>(perStripe));
    }

    private LruCache<K, V> stripeFor(K key) {
        int h = key.hashCode();
        h ^= (h >>> 16);                              // mix high bits into low ones, as HashMap does
        return stripes.get(Math.floorMod(h, stripes.size()));
    }

    // No lock here: each call locks only its own stripe (LruCache's methods are synchronized).
    @Override public Optional<V> get(K key)          { return stripeFor(key).get(key); }
    @Override public void put(K key, V value)        { stripeFor(key).put(key, value); }
    @Override public boolean remove(K key)           { return stripeFor(key).remove(key); }
    @Override public int size() {                     // a moving total, not a snapshot
        int n = 0;
        for (LruCache<K, V> s : stripes) n += s.size();
        return n;
    }
}

public class StripedDemo {
    public static void main(String[] args) throws Exception {
        Cache<Integer, Integer> cache = new StripedLruCache<>(1_000, 16);
        ExecutorService pool = Executors.newFixedThreadPool(8);
        List<Future<?>> jobs = new ArrayList<>();
        for (int t = 0; t < 8; t++) {
            final int seed = t;
            jobs.add(pool.submit(() -> {
                Random r = new Random(seed);
                for (int i = 0; i < 200_000; i++) {
                    int k = r.nextInt(5_000);
                    if (cache.get(k).isEmpty()) cache.put(k, k * 10);
                }
            }));
        }
        for (Future<?> j : jobs) j.get();
        pool.shutdown();
        System.out.println("size after 1.6 M operations: " + cache.size() + " (at most 16 x 63 = 1008)");
        cache.put(42, 420);
        System.out.println("get(42) -> " + cache.get(42));
    }
}

Output (Java first; the Python demo does 400 K operations and prints the same size):

size after 1.6 M operations: 1008 (at most 16 x 63 = 1008)
get(42) -> Optional[420]

What you give up, and what to watch:

  • Eviction is LRU per stripe. A full stripe evicts its own oldest key even when another stripe holds a key that is older overall. With many keys per stripe the hit rate is close to exact LRU.
  • Capacity is rounded per stripe (1,000 / 16 rounds up to 63, so 1,008 in total), and a skewed hash can fill one stripe while others are half empty. Mix the hash bits, as the Java version does, and use a power-of-two stripe count of about 2 to 4 times the core count.
  • size() is not a snapshot: it adds stripes one by one while others change. Fine for metrics, not for decisions.
  • In CPython the GIL (global interpreter lock: only one thread runs Python bytecode at a time) limits the gain to shorter lock waits; real parallel speed-up needs a free-threaded build (Python 3.13+) or processes.

6. TTL: expiry on top of LRU

TTL and LRU answer different questions: LRU decides what to drop when full; TTL decides when data is too old to trust. The code stores expiresAt in each node and checks it on get, which is lazy expiry: an expired entry costs nothing until someone reads it.

The catch is that expired entries nobody reads still occupy slots until LRU eviction reaches them. That is usually fine, because they drift to the back of the list. If memory matters, add active expiry: a background task that periodically removes expired entries. Keeping entries ordered by expiry needs a second structure (a min-heap, or a list if every entry has the same TTL, since then write order equals expiry order). Redis does both, lazy checks on access and a periodic sampler.

7. Options and trade-offs

ApproachGood atWeak atUse when
Hash map + doubly linked list (built above)Exact LRU, O(1), you control everythingPointer overhead per entry (two references plus a node object)The interview; custom eviction rules
LinkedHashMap / OrderedDictFive lines, well testedNot thread-safe; harder to add TTL or byte limitsProduction code in one thread, or behind your own lock
Sharded LRUScales across coresLRU is exact only within a shardHot in-process caches on many-core servers
Approximate LRU (sampling)No list, low memory, little lockingMay evict a key that is not the oldestVery large caches (Redis)
LFU / W-TinyLFU (Caffeine)Better hit rate when some keys stay popularMore complex; frequency counters to ageProduction caches with skewed access

8. Extensions the interviewer will ask for

  • Capacity in bytes instead of entries: track totalBytes; on put, evict from the tail while totalBytes > maxBytes. One insert may evict several small entries. (Try box below.)
  • Eviction callback: accept a listener onEvict(key, value) in the constructor, called after the lock is released so a slow listener does not block the cache. This is the Observer idea; see the Observer pattern.
  • LFU instead of LRU: make eviction a policy behind the Cache interface. O(1) LFU uses a map from frequency to an ordered set of keys, plus a minFreq pointer (built below).
  • Loading cache: get(key, loader) computes the value on a miss. Two threads missing the same key should not both call the loader; keep a map of in-flight loads (a Future per key) so the second waits for the first.

LFU: evict the least frequently used

LFU (least frequently used) evicts the key with the fewest uses, which keeps popular keys that LRU would drop after a burst of one-off reads (a nightly report scanning thousands of keys once). The O(1) design keeps three things:

StructureHolds
entrieskey → value and its use count (frequency)
bucketsfrequency → the keys with that frequency, oldest first (a LinkedHashSet in Java, an OrderedDict used as an ordered set in Python)
minFreqthe lowest frequency that currently has keys

A use (get, or put on an existing key) moves the key from bucket f to bucket f + 1; if bucket f is now empty and f was minFreq, minFreq becomes f + 1. A new key goes into bucket 1 and sets minFreq = 1. To evict, take the oldest key in bucket minFreq, so ties between equally used keys fall back to LRU. Every step is a hash lookup or an ordered-set insert or delete: O(1).

import java.util.*;

/** O(1) LFU cache. Evicts the least frequently used key; ties go to the least recently used. */
final class LfuCache<K, V> implements Cache<K, V> {          // Cache is the interface from section 4
    private static final class Entry<V> {
        V value; int freq = 1;
        Entry(V value) { this.value = value; }
    }

    private final int capacity;
    private final Map<K, Entry<V>> entries = new HashMap<>();
    // frequency -> keys with that frequency, oldest first (LinkedHashSet keeps insertion order)
    private final Map<Integer, LinkedHashSet<K>> buckets = new HashMap<>();
    private int minFreq = 0;
    private long evictions;

    LfuCache(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
        this.capacity = capacity;
    }

    /** Move a key from its frequency bucket to the next one up. O(1). */
    private void touch(K key, Entry<V> e) {
        LinkedHashSet<K> old = buckets.get(e.freq);
        old.remove(key);
        if (old.isEmpty()) {
            buckets.remove(e.freq);
            if (minFreq == e.freq) minFreq++;           // the key was the last one at the minimum
        }
        e.freq++;
        buckets.computeIfAbsent(e.freq, f -> new LinkedHashSet<>()).add(key);
    }

    @Override public synchronized Optional<V> get(K key) {
        Entry<V> e = entries.get(key);
        if (e == null) return Optional.empty();
        touch(key, e);
        return Optional.of(e.value);
    }

    @Override public synchronized void put(K key, V value) {
        Entry<V> e = entries.get(key);
        if (e != null) {                                // update counts as a use, never evicts
            e.value = value;
            touch(key, e);
            return;
        }
        if (entries.size() == capacity) {
            LinkedHashSet<K> victims = buckets.get(minFreq);
            K victim = victims.iterator().next();       // least recently used among the least frequent
            victims.remove(victim);
            if (victims.isEmpty()) buckets.remove(minFreq);
            entries.remove(victim);
            evictions++;
            System.out.println("  evict " + victim + " (freq " + minFreq + ")");
        }
        entries.put(key, new Entry<>(value));
        buckets.computeIfAbsent(1, f -> new LinkedHashSet<>()).add(key);
        minFreq = 1;                                    // a new key always has the lowest frequency
    }

    @Override public synchronized boolean remove(K key) {
        Entry<V> e = entries.remove(key);
        if (e == null) return false;
        LinkedHashSet<K> b = buckets.get(e.freq);
        b.remove(key);
        if (b.isEmpty()) buckets.remove(e.freq);
        // minFreq may now point at an empty bucket. That is safe: the cache is below capacity,
        // so nothing is evicted before the next new key, and that put resets minFreq to 1.
        return true;
    }

    @Override public synchronized int size() { return entries.size(); }
    synchronized long evictions() { return evictions; }
}

public class LfuDemo {
    public static void main(String[] args) {
        Cache<String, Integer> c = new LfuCache<>(2);
        c.put("a", 1);
        c.put("b", 2);
        c.get("a");                                      // a: freq 2, b: freq 1
        System.out.println("put c");
        c.put("c", 3);                                   // full: evicts b, the least frequent
        System.out.println("get b -> " + c.get("b"));
        c.get("a"); c.get("c");                          // a: freq 3, c: freq 2
        System.out.println("put d");
        c.put("d", 4);                                   // evicts c (freq 2), not a (freq 3)
        System.out.println("get a -> " + c.get("a") + ", get c -> " + c.get("c") + ", get d -> " + c.get("d"));
        System.out.println("size " + c.size());
    }
}

Output (identical in both languages apart from Optional versus None):

put c
  evict b (freq 1)
get b -> Optional.empty
put d
  evict c (freq 2)
get a -> Optional[1], get c -> Optional.empty, get d -> Optional[4]
size 2

c was used twice and a three times, so c goes even though it was used more recently than a; plain LRU would have evicted a.

When not to build this

  • Function results in Python: @functools.lru_cache(maxsize=1024) already does it, thread-safely.
  • Production Java: use Caffeine or Guava's cache; they handle concurrency, TTL, weights and statistics.
  • Shared across servers: an in-process cache is per server. If every server must see the same data, use Redis or Memcached; see caching.
  • Tiny caches (a dozen entries): a scan over an array is fast enough and simpler.

In the interview

Your turn: spot the bug

This put passes a simple test but breaks the cache. Find three bugs and fix them.

public synchronized void put(K key, V value) {
    if (map.size() == capacity) {
        Node<K, V> lru = tail.prev;
        unlink(lru);
    }
    Node<K, V> n = new Node<>(key, value, Long.MAX_VALUE);
    addFront(n);
    map.put(key, n);
}
Compare with our answer

The bugs: (1) the evicted node's key is never removed from the map, so the map grows forever and get can return evicted values. (2) An existing key is treated as new: the old node stays in the list, so the list has two nodes for one key. (3) Updating an existing key in a full cache evicts an innocent entry, even though the size would not grow.

public synchronized void put(K key, V value) {
    Node<K, V> n = map.get(key);
    if (n != null) {                         // existing key: update and move, never evict
        n.value = value;
        unlink(n); addFront(n);
        return;
    }
    if (map.size() == capacity) {
        Node<K, V> lru = tail.prev;
        unlink(lru);
        map.remove(lru.key);                 // the node carries its key for exactly this
    }
    n = new Node<>(key, value, Long.MAX_VALUE);
    addFront(n);
    map.put(key, n);
}

A strong answer mentions: removing the victim's key from the map · handling an existing key before the capacity check · not evicting on an update · the node storing its key · the whole method under one lock.

Your turn: the requirement changes

The cache now stores images of different sizes. Capacity becomes 50 MB in total, not a number of entries. What changes in the code? Write the new put.

Compare with our answer

Each node gets a size field and the cache keeps totalBytes. On put, remove the old node's size if the key exists, add the new one, then evict from the tail while the total is over the limit; one large image may push out several small ones. Reject a single item larger than the whole cache, or it would evict everything and still not fit.

public synchronized void put(K key, V value, long bytes) {
    if (bytes > maxBytes) throw new IllegalArgumentException("item larger than the cache");
    Node<K, V> old = map.remove(key);
    if (old != null) { unlink(old); totalBytes -= old.bytes; }
    Node<K, V> n = new Node<>(key, value, bytes);
    addFront(n); map.put(key, n); totalBytes += bytes;
    while (totalBytes > maxBytes) {          // may evict several entries
        Node<K, V> lru = tail.prev;
        unlink(lru); map.remove(lru.key); totalBytes -= lru.bytes;
    }
}

A strong answer mentions: a size per node and a running total · subtracting the old size on update · a while loop, not a single eviction · rejecting an item bigger than the cache · the new node inserted first, so it is never its own victim unless it alone is too big.

LRU cache on one page
  • Structure: hash map key → node, plus a doubly linked list in order of use; front = most recent, tail.prev = victim.
  • Node stores key, value, prev, next (and expiresAt for TTL). The key is needed to delete the map entry on eviction.
  • Sentinels head and tail remove end-of-list special cases.
  • get: lookup, unlink, add to front. put: update-and-move if present; else evict if full, then insert. All O(1) average.
  • Threads: get writes the list, so one lock around every method; shard by key hash to scale.
  • TTL: lazy check on read with an injected clock; optional background sweep.
  • Shortcuts: LinkedHashMap(…, true) + removeEldestEntry; OrderedDict.move_to_end + popitem(last=False). Neither is thread-safe.
  • Production: Caffeine (W-TinyLFU), Redis sampled LRU (allkeys-lru).
  • Extensions: byte capacity (evict while over), eviction listener, LFU, loading cache with one load per key.
  • LFU in O(1): key → (value, freq), freq → ordered set of keys, minFreq; evict the oldest key in the minFreq bucket; age counts. Striping: N independent LRUs chosen by key hash, LRU exact only per stripe.
Check what stuck

1. Your LRU cache uses a ReentrantReadWriteLock: get takes the read lock and put the write lock. Under load, the list occasionally becomes corrupted. Why?

2. A cache with capacity 3 receives put(a), put(b), put(c), get(a), put(d), get(b). What does the last call return?

3. Why does each list node store its key as well as its value?

4. An interviewer allows LinkedHashMap. A candidate creates new LinkedHashMap<>(16, 0.75f, false) and overrides removeEldestEntry. What is wrong?

5. Your in-process LRU cache, guarded by one lock, is the hottest lock on a 48-core service. Which change helps most while keeping behaviour close to LRU?

6. Entries have a 10-minute TTL checked lazily on get. Memory usage stays high overnight even though most entries expired hours ago. What explains it?

7. A test for TTL currently calls Thread.sleep(600) and is slow and sometimes flaky on busy CI machines. What is the best fix?

8. An O(1) LFU cache with capacity 2 holds a (used 3 times) and c (used twice, more recently than a). A new key d is put. What happens?

Score 60% or more and the lesson is marked complete.

Passing the quiz also marks it complete. Progress is saved in this browser only.