!This gives away every stage. For a clean attempt, practise it first, then come back.

How this walkthrough is built

An LRU cache is the classic low-level design problem with a data-structure heart. It’s asked at almost every level, from new graduates to senior engineers, and the bar rises with the level. A junior answer gets O(1) get and put working. A senior answer also makes it safe under threads, explains why the obvious fixes fail, and extends it without rewriting it.

We’ll build it in the same order you would in an interview. Each step uses only what the steps before it produced:

The one sentence to remember: an LRU cache is a hash map that finds things, joined to a list that remembers order. Everything else on this page is detail around that sentence, and the details are where interviews are won.

Step 1Understand the problem

Picture the real thing first

Think about the “recent files” menu in your code editor. It shows, say, the last ten files you opened. Open an eleventh, and the one you haven’t touched for the longest time drops off the bottom. Open a file that’s already in the list, and it jumps to the top without anything dropping off.

That’s exactly an LRU cache. LRU stands for least recently used: when there’s no room, throw away the thing that was used longest ago. The bet is that something you used a minute ago is more likely to be needed again than something you used yesterday.

Real systems make this bet everywhere. Your browser keeps recently viewed images. A database keeps recently read pages in memory. An app server keeps recently loaded user profiles so it doesn’t ask the database every time. In each case memory is limited, and the cache has to decide what to forget.

Ask before you design

Each question changed something in the design:

Functional requirements

1. FR1. get(key) returns the value if the key is present, and marks it as the most recently used.
2. FR2. put(key, value) inserts a new entry or updates an existing one, and marks it as the most recently used.
3. FR3. The cache holds at most a fixed number of entries, set when it’s created. When it’s full, putting a new key first evicts the least recently used entry.
4. FR4. remove(key) deletes an entry. size() says how many entries there are.
5. FR5. Callers can register to be told when an entry is evicted.
6. FR6. Keys and values can be any type.

Non-functional requirements

1. NFR1: Fast. get and put run in O(1) time, no matter how big the cache is.
2. NFR2: Safe under concurrency. Many threads can call it at once, and its internal structure never breaks.
3. NFR3: Bounded. It never holds more entries than its capacity, not even for a moment that another thread could see.
4. NFR4: Easy to extend. Expiry, statistics and other eviction rules can be added without editing the core class.

O(1) means “constant time”: the work doesn’t grow as the cache grows. A cache with a million entries answers as fast as one with ten. If you’ve only met this idea briefly, here’s the practical meaning: no loops over the entries, ever, inside get or put.

Assumptions we’ll write down

Step 2Break it into entities

In most LLD problems this step is about finding classes. In this one it’s mostly about finding the right data structures, because the classes follow from them. So we’ll do the usual noun hunt quickly, then spend real time on the structure choice.

Pull out the nouns

From the requirements: cache, key, value, entry, capacity, order of use, least recently used entry, eviction, listener, thread.

The interesting row is “order of use”. In the parking lot, every class was a real-world thing. Here, the most important class is an idea: the order in which entries were used. That’s normal for data-structure problems. The trick is noticing that the order has its own rules (move to front, remove the oldest) and so deserves its own class, instead of being scattered through the cache’s methods.

The data structure trap

Most candidates either jump straight to “hash map plus doubly linked list” (memorised, and the interviewer can tell) or try something simpler that quietly breaks O(1). The strong move is to reason through the options out loud. Each one fails in a way that points at the next.

Option 1: just a hash map. get and put are O(1). But when the cache is full, which key do you evict? A hash map has no idea which key was used longest ago. Dead end.

Option 2: a hash map plus a “last used” time on each entry. Now you know when each key was used. But to find the oldest, you have to look at every entry:

// evicting means scanning everything: O(n)
K oldest = null;
long oldestTime = Long.MAX_VALUE;
for (Map.Entry> e : map.entrySet()) { 1
    if (e.getValue().lastUsed < oldestTime) {
        oldestTime = e.getValue().lastUsed;
        oldest = e.getKey();
    }
}

get is O(1), but every eviction is O(n). For a full cache, that’s every put.

Option 3: a hash map plus a priority queue ordered by time. A priority queue (a heap) gives the oldest in O(1) and removes it in O(log n). Better. But every get changes an entry’s time, and moving an entry inside a heap is O(log n) at best (and Java’s PriorityQueue makes it O(n), because removing an arbitrary element means searching for it). Close, but not O(1).

Option 4: a list in order of use. Newest at the front, oldest at the back. Evicting is “remove from the back”: O(1). Marking as used is “move to the front”. But to move an entry, you first have to find it in the list, which is O(n).

Look at what options 1 and 4 are each missing. The map can find in O(1) but has no order. The list has order but can’t find. So combine them: the map stores, for each key, a direct pointer to that key’s node in the list. Finding is a map lookup. Moving is a few pointer changes on a node you’re already holding. Neither needs a loop.

Three details that make it work

The combined design has three small details. Each one looks optional until you try to write the code without it.

1. The list must be doubly linked. To unlink a node from the middle of a list, you need to change the pointer in the node before it. In a singly linked list, a node doesn’t know what’s before it, so you’d have to walk from the start to find out: O(n). With a prev pointer on every node, a node can unlink itself in O(1).

2. The node must store its own key. When we evict, we take the node at the back of the list. Then we have to remove that key from the map too, or the map points at a node that’s no longer in the list. But the list holds nodes, and if a node only held a value, we wouldn’t know which map key to remove. So each node keeps its key, even though the map already has it. A little extra memory buys O(1) eviction.

3. Sentinel nodes at both ends. A sentinel is a dummy node that never holds data. We put one permanently at the front (head) and one at the back (tail). Then every real node always has a real prev and a real next, even when it’s the only node. Without sentinels, every insert and unlink needs if (node == first), if (node == last) and if (list is empty) checks, and those checks are exactly where bugs hide.

Say all three out loud in the interview. They’re what separate an understood design from a memorised one.

Pull out the verbs

The verbs from the requirements: find, mark as used, insert, update, evict, remove, notify.

Give each job to the class that knows the most

Information Expert: give a job to the class that already has the information to do it.

Notice what the list does not know: keys as lookups, capacity, eviction rules. It’s a plain ordered list of nodes with O(1) moves. That keeps it simple and testable on its own. All the policy lives in LRUCache.

CRC cards

Find what will change

The last row is a deliberate decision, and it’s worth defending in the interview. We’ll come back to it.

Step 3Top-down or bottom-up?

Top-down starts with what callers need:

1. Callers need get(key) and put(key, value). So Cache and LRUCache exist.
2. To get in O(1), the cache needs to find a key instantly. So it holds a HashMap.
3. To evict the oldest in O(1), it needs entries in order of use. So it holds a DoublyLinkedList.
4. To move an entry in O(1), the list needs nodes that can unlink themselves. So Node has prev and next.

Bottom-up goes the other way: write Node, then a DoublyLinkedList you can test by itself, then the LRUCache that combines it with a map.

For this problem, bottom-up coding matters even more than usual. The list is where nearly all the bugs live: a missed pointer update leaves the list broken in a way that only shows up much later. If you write and check the list first, the cache on top of it is short and almost boring. So again: design top-down, code bottom-up.

Step 4Design each class

LRUCache: the class that keeps two structures in step

Job: answer get, put and remove in O(1), and keep the map and the list describing exactly the same set of entries.

The single most important rule inside this class: the map and the list must always contain the same nodes. Every method changes both or neither. If a key is in the map but not the list, it will never be evicted. If a node is in the list but not the map, it takes up space forever and can’t be found. Most broken LRU caches break this rule somewhere.

DoublyLinkedList: order of use, nothing else

Job: keep nodes in order from most to least recently used, with O(1) changes.

It’s written by hand, not taken from Java’s LinkedList, and the reason is worth knowing. Java’s LinkedList doesn’t give you its nodes. To move an element, you’d call remove(object), which searches from the start: O(n). We need to hold a node and unlink it directly.

Node: one entry

Job: hold one entry and its two neighbours.

The key is final because a node never changes which key it belongs to. The value isn’t, because put on an existing key updates it in place, which is cheaper than replacing the node.

Cache and EvictionListener: the contracts

Cache has four methods: get, put, remove, size. Callers depend on this, never on LRUCache directly, so a wrapper that adds expiry or statistics can be handed to them instead.

EvictionListener has one method, evicted(key, value). Because it has a single method, a caller can pass a lambda: (k, v) -> database.save(k, v).

Step 5How the classes relate

The shared node is the heart of the design: one node object, reachable from two structures. The map reaches it by key; the list reaches it by position. That’s why updating one node is visible to both instantly, and why both must always agree about which nodes exist.

Step 6The class diagram, built up

Version 1: the two structures

Start with the core idea: a cache holding a map and a list, both pointing at nodes.

Version 2: the contracts

Add the interface callers depend on, and the listener for evictions.

Version 3: the whole picture

Check it against the requirements

Step 7The patterns, and why each one is here

Why the eviction rule isn’t a Strategy (yet)

A tempting “senior-looking” design pulls the eviction rule out into an interface: EvictionPolicy with methods like keyAccessed(key) and evictKey(), and an LRUPolicy that implements it. Then LFU is just another policy.

It sounds clean, but look at what it costs. The policy needs its own way to find a key’s position in O(1), so it needs its own key-to-node map. Now every key is stored in two maps: the cache’s map of values and the policy’s map of positions. Twice the memory for the index, and two structures to keep in sync on every operation.

There’s also a deeper problem. LRU and LFU don’t just evict differently; they need different data structures to be O(1). LRU needs one list. O(1) LFU needs a list per usage count and a pointer to the smallest count (you’ll see it in step 11). An interface general enough for both ends up very vague.

So the honest answer is: *for one eviction rule, a dedicated class is simpler and faster. If the system genuinely needs swappable rules, write each rule as its own Cache implementation, sharing the Cache interface.* That’s what we do in the follow-ups. Saying this, with the reason, impresses more than adding the interface by reflex.

Why not a Singleton

“There’s one cache for the app, so make it a Singleton” comes up often. Same answer as the parking lot: tests need fresh caches with known sizes, apps often need several caches (users, sessions, product pages), and a global object hides who depends on it. Create caches where the app starts and pass them to the code that needs them.

Step 8Walk the flows

Watch it run

Before the sequence diagrams, see the whole thing work. A cache with room for three entries:

get: a hit

1. Lock, so no other thread changes the structures while we work.
2. One map lookup finds the node directly. No searching.
3. The list moves that node to the front: unlink it (two pointer changes on its neighbours) and add it after head (four pointer changes).
4. Unlock and return the value, wrapped in an Optional.

A miss is shorter: the map returns null, we unlock and return Optional.empty(). The list isn’t touched.

put: a new key into a full cache

1. Check whether the key exists. It doesn’t, so this is an insert.
2. The cache is full, so evict first: take the last node from the list, then remove its key from the map. This is detail 2 from step 2 paying off: the node knows its key.
3. Create the new node, add it at the front, and put it in the map.
4. Unlock, then tell the listener. Step 10 explains why the order matters.

put: an existing key

If the map already has the key, the flow is: update the node’s value, move it to the front, unlock. No eviction, no new node. Forgetting this branch, and evicting on every put, is one of the most common bugs in this problem.

A full trace

Here’s a real run with capacity 3, printing the list from most to least recent after each operation:

put A   [A]
put B   [B, A]
put C   [C, B, A]
get A = 1  [A, C, B]
put D   [D, A, C]  evicted [B=2]
get B = miss  [D, A, C]
put C=30 [C, D, A]  get C = 30
put E   [E, C, D]  evicted [B=2, A=1]

Read it line by line. After get A, A jumps to the front, so B becomes the oldest. put D evicts B, not A, because A was just used. put C=30 updates C in place and moves it to the front with no eviction. put E then evicts A, which had become the oldest.

What walking the flows taught us

The life of an entry

When things go wrong

Step 9Write the code, bottom-up

Every block below is part of one program that compiles and runs. The outputs on this page come from running it.

9.1 The contracts

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

interface EvictionListener { void evicted(K key, V value); }

Generics are the parts: placeholders for “whatever key type and value type the caller chooses”. A Cache only accepts String keys and only returns User values, checked by the compiler.

9.2 Node

final class Node {
    final K key; 1
    V value; 2
    Node prev, next;
    Node(K key, V value) { this.key = key; this.value = value; }
}

9.3 DoublyLinkedList

This is where the bugs live, so it gets the most care. Draw boxes and arrows on paper the first few times you write addFirst and unlink; there’s no shame in it, and interviewers like seeing it.

final class DoublyLinkedList {
    private final Node head = new Node<>(null, null); 1
    private final Node tail = new Node<>(null, null); 2
    private int size;

    DoublyLinkedList() { head.next = tail; tail.prev = head; }

    void addFirst(Node n) {
        n.prev = head;
        n.next = head.next; 3
        head.next.prev = n;
        head.next = n;
        size++;
    }

    void unlink(Node n) {
        n.prev.next = n.next; 4
        n.next.prev = n.prev;
        n.prev = null; 5
        n.next = null;
        size--;
    }

    void moveToFront(Node n) { unlink(n); addFirst(n); }

    Node removeLast() {
        if (size == 0) return null;
        Node last = tail.prev;
        unlink(last);
        return last;
    }

    int size() { return size; }
}

Look at unlink. Thanks to the sentinels, n.prev and n.next are never null for a node in the list, even if it’s the only one: its neighbours are head and tail. So there are no if statements at all. Without sentinels, this method needs four branches.

Note (3) is the line people most often get wrong. The order of the four assignments in addFirst matters: head.next must be read before it’s overwritten.

Why clear n.prev and n.next in note (5)? It isn’t strictly needed for correctness, but it means a removed node doesn’t keep its old neighbours alive in memory, and if some bug ever tries to unlink the same node twice, it fails loudly with a NullPointerException instead of silently corrupting the list.

9.4 LRUCache: the fields and get

final class LRUCache implements Cache {
    private final int capacity;
    private final Map> map;
    private final DoublyLinkedList order = new DoublyLinkedList<>();
    private final EvictionListener listener;
    private final ReentrantLock lock = new ReentrantLock();

    LRUCache(int capacity) { this(capacity, (k, v) -> { }); } 1

    LRUCache(int capacity, EvictionListener listener) {
        if (capacity <= 0)
            throw new IllegalArgumentException("capacity must be positive");
        this.capacity = capacity;
        this.map = new HashMap<>(capacity * 4 / 3 + 1); 2
        this.listener = Objects.requireNonNull(listener);
    }

    public Optional get(K key) {
        Objects.requireNonNull(key);
        lock.lock();
        try {
            Node n = map.get(key);
            if (n == null) return Optional.empty();
            order.moveToFront(n);
            return Optional.of(n.value);
        } finally { lock.unlock(); } 3
    }

Note (2): a HashMap grows (and copies everything) when it’s 75% full. We know the maximum size in advance, so we make it big enough from the start. No surprise slow put halfway through the day.

Note (3): try ... finally guarantees the lock is released even if something throws. Forgetting this is how a whole server freezes: one exception, and every thread waits forever for a lock nobody will release.

9.5 LRUCache: put

    public void put(K key, V value) {
        Objects.requireNonNull(key);
        Objects.requireNonNull(value);
        Node victim = null;
        lock.lock();
        try {
            Node n = map.get(key);
            if (n != null) { 1
                n.value = value;
                order.moveToFront(n);
                return;
            }
            if (map.size() == capacity) { 2
                victim = order.removeLast();
                map.remove(victim.key);
            }
            n = new Node<>(key, value);
            order.addFirst(n);
            map.put(key, n);
        } finally { lock.unlock(); }
        if (victim != null) listener.evicted(victim.key, victim.value); 3
    }

Three decisions, matching the three notes:

1. The existing-key check comes first. If it came after the capacity check, updating a key in a full cache would evict something for no reason.
2. Evict before inserting, so the cache never holds capacity + 1 entries, even for an instant (NFR3).
3. The listener runs after the lock is released. It’s someone else’s code: it might write to a database and take 50 milliseconds, or it might call back into the cache. Inside the lock, a slow listener would stall every thread, and a listener that calls cache.get() could even deadlock on some lock types. Outside, the cache is already consistent and other threads carry on.

9.6 LRUCache: remove and size

    public boolean remove(K key) {
        lock.lock();
        try {
            Node n = map.remove(key);
            if (n == null) return false;
            order.unlink(n);
            return true;
        } finally { lock.unlock(); }
    }

    public int size() {
        lock.lock();
        try { return map.size(); } finally { lock.unlock(); }
    }
}

Even size() takes the lock. Without it, a thread could read the size in the middle of another thread’s put, and Java gives no guarantee about what it sees.

9.7 Putting it together

List evicted = new ArrayList<>();
LRUCache c = new LRUCache<>(3, (k, v) -> evicted.add(k + "=" + v));
c.put("A", 1);
c.put("B", 2);
c.put("C", 3);
c.get("A");
c.put("D", 4); 1
c.get("B"); 2
c.put("C", 30); 3
c.put("E", 5); 4

The output is the trace from step 8, plus the constructor check:

put D   [D, A, C]  evicted [B=2]
get B = miss  [D, A, C]
put C=30 [C, D, A]  get C = 30
put E   [E, C, D]  evicted [B=2, A=1]
capacity 0: capacity must be positive

Step 10Make it safe when threads share it

Why a thread-safe map isn’t enough

The tempting fix is to swap HashMap for ConcurrentHashMap and call it done. The map is now safe. But the list isn’t, and the list is where the danger is. Here’s what can happen when two threads get neighbouring keys at once:

Each method is correct on its own. Interleaved, they corrupt the list. We tested exactly this design: a ConcurrentHashMap with an unprotected list, eight threads, 200,000 random gets and puts each.

unlocked run 0: crashed: NullPointerException
unlocked run 1: crashed: NullPointerException
unlocked run 2: crashed: NullPointerException

Three runs, three crashes. In production it’s often worse than a crash: a list with a loop in it makes the next removeLast or a debugging walk spin forever, with no error message at all.

Why a read-write lock doesn’t help

The next idea is a read-write lock: many readers at once, one writer at a time. It’s the right tool when reads don’t change anything. But in an LRU cache, every get changes the list, because it moves the node to the front. So every get would need the write lock, and you’re back to one-at-a-time, with a more complicated lock. This is the requirement from step 1, “get counts as use”, paying off. Mentioning it shows you understood why the problem is hard.

One lock: correct

The simple answer is one lock around every operation, which is what our code does. Is it correct? Same test, eight threads, then check that the list walked forwards matches the list walked backwards, its size matches the map’s size, and the cache never went over capacity:

locked run 0: size=100 healthy=true
locked run 1: size=100 healthy=true
locked run 2: size=100 healthy=true

Every operation is a handful of pointer changes, so the lock is held for well under a microsecond. For most applications, this is the right answer and you should stop here.

Making it faster: shards

final class ShardedCache implements Cache {
    private final List> shards = new ArrayList<>();

    ShardedCache(int shardCount, int capacityPerShard) {
        for (int i = 0; i < shardCount; i++) shards.add(new LRUCache<>(capacityPerShard));
    }

    private LRUCache shardFor(K key) {
        int mixed = key.hashCode() * 0x9E3779B9; 1
        return shards.get((mixed >>> 16) % shards.size()); 2
    }

    public Optional get(K key) { return shardFor(key).get(key); }
    public void put(K key, V value) { shardFor(key).put(key, value); }
    public boolean remove(K key) { return shardFor(key).remove(key); }
    public int size() { return shards.stream().mapToInt(LRUCache::size).sum(); }
}

Notes (1) and (2) hide a real bug we hit while building this page. Our first version picked the shard with hashCode % 16, the obvious choice. It was slower than one lock, even with a single thread. The reason: Java’s HashMap also uses the low bits of the hash to choose a bucket. If shard 3 only ever receives keys whose low bits are 0011, then inside shard 3’s map, all those keys land in one-sixteenth of the buckets and pile up. Multiplying by a large odd constant scrambles the bits, and taking the shard from the high bits leaves the low bits varied for the map.

Here are real timings: 4 million operations (80% gets) on a cache of 16,000 entries, on an 8-core laptop.

Two honest lessons in that table. First, with eight threads, sixteen shards beat one lock by about 30%. Second, eight threads with one lock took longer than one thread did. When each operation is this tiny, threads spend more time handing the lock and the data back and forth between CPU cores than doing work. Sharding helps, but it doesn’t make the problem go away.

That’s why high-performance caches go further. Java’s Caffeine library doesn’t reorder its list on every read; it records reads in a small buffer and applies them in batches. Redis doesn’t keep an exact LRU order at all; when it needs to evict, it samples a few keys and evicts the oldest of the sample. Both trade a perfectly exact order for far less coordination. You don’t need to build these in an interview, but knowing they exist, and why, is exactly the kind of depth senior interviewers look for. Mention them and move on.

One more trade-off to name: with shards, “least recently used” is only exact within a shard. The cache as a whole might evict a key from a busy shard while an older key sits in a quiet one. For a cache, that’s almost always fine.

Step 11Follow-ups, extended without editing

Entries that expire

Bad solutionA timer per entry

Schedule a task for each put that deletes the key 5 minutes later. A million entries means a million scheduled tasks, and a key that’s updated must cancel and reschedule its task. Lots of moving parts, and lots of memory.

Good solutionCheck the time on read

Store the expiry time with each value. On get, if it’s past, treat it as missing and remove it. No background work at all.

Great solutionDo it in a wrapper, so the core never changes

final class TtlCache implements Cache {
    private record Entry(V value, Instant expiresAt) { }
    private final LRUCache> inner; 1
    private final Duration ttl;
    private final Clock clock;

    TtlCache(int capacity, Duration ttl, Clock clock) {
        this.inner = new LRUCache<>(capacity);
        this.ttl = ttl;
        this.clock = clock;
    }

    public Optional get(K key) {
        Optional> e = inner.get(key);
        if (e.isEmpty()) return Optional.empty();
        if (!clock.instant().isBefore(e.get().expiresAt())) { 2
            inner.remove(key);
            return Optional.empty();
        }
        return Optional.of(e.get().value());
    }

    public void put(K key, V value) {
        inner.put(key, new Entry<>(value, clock.instant().plus(ttl)));
    }
    public boolean remove(K key) { return inner.remove(key); }
    public int size() { return inner.size(); }
}

ttl after 4 min: ayush
ttl after 6 min: expired, size now 0

The clock is passed in, so the test moved time forward instead of waiting six minutes. One trade-off to mention: an expired entry that’s never read again still takes a slot until LRU eviction reaches it. If that matters, add a background sweep that runs every minute and removes expired entries. For most caches, LRU clears them soon enough.

Hit rate statistics

Same trick, a wrapper:

final class RecordingCache implements Cache {
    private final Cache inner;
    private final LongAdder hits = new LongAdder(), misses = new LongAdder();   // (1)

    RecordingCache(Cache inner) { this.inner = inner; }

    public Optional get(K key) {
        Optional v = inner.get(key);
        (v.isPresent() ? hits : misses).increment();
        return v;
    }
    public void put(K key, V value) { inner.put(key, value); }
    public boolean remove(K key) { return inner.remove(key); }
    public int size() { return inner.size(); }

    double hitRate() {
        long h = hits.sum(), total = h + misses.sum();
        return total == 0 ? 0 : (double) h / total;
    }
}

LongAdder (note 1) is a counter built for many threads incrementing at once: each thread mostly updates its own private cell, and sum() adds them up. It avoids the very contention we measured in step 10.

Because it wraps any Cache, it works around LRUCache, TtlCache or ShardedCache alike: new RecordingCache<>(new TtlCache<>(...)). That’s the payoff of the Cache interface from step 2.

Least frequently used instead

That’s what LFU (least frequently used) is for: evict the key used the fewest times, and among ties, the oldest. The O(1) version is clever, so it’s worth seeing:

final class LFUCache implements Cache {
    private final int capacity;
    private final Map values = new HashMap<>();
    private final Map counts = new HashMap<>();
    private final Map> byCount = new HashMap<>();   // (1)
    private int minCount;                                                       // (2)

    LFUCache(int capacity) { this.capacity = capacity; }

    public synchronized Optional get(K key) {
        if (!values.containsKey(key)) return Optional.empty();
        touch(key);
        return Optional.of(values.get(key));
    }

    public synchronized void put(K key, V value) {
        if (values.containsKey(key)) { values.put(key, value); touch(key); return; }
        if (values.size() == capacity) {
            K victim = byCount.get(minCount).iterator().next(); 3
            byCount.get(minCount).remove(victim);
            values.remove(victim);
            counts.remove(victim);
        }
        values.put(key, value);
        counts.put(key, 1);
        byCount.computeIfAbsent(1, c -> new LinkedHashSet<>()).add(key);
        minCount = 1; 4
    }

    private void touch(K key) {
        int c = counts.get(key);
        counts.put(key, c + 1);
        byCount.get(c).remove(key);
        if (c == minCount && byCount.get(c).isEmpty()) minCount = c + 1;
        byCount.computeIfAbsent(c + 1, x -> new LinkedHashSet<>()).add(key);
    }

    public synchronized boolean remove(K key) {
        if (!values.containsKey(key)) return false;
        int c = counts.remove(key);
        byCount.get(c).remove(key);
        values.remove(key);
        return true;
    }
    public synchronized int size() { return values.size(); }
}

The idea: group keys by how many times they’ve been used (note 1), and remember the smallest group that isn’t empty (note 2). A LinkedHashSet keeps insertion order, so the first key in the smallest group is the least used and the oldest among equals (note 3). Every step is a map lookup or a set operation: O(1).

Same operations on both caches (capacity 2: put A, put B, get A twice, get B once, put C):

lfu after put C: A=true B=false C=true
lru after put C: A=false B=true C=true

LRU evicted A, the heavy user, because B was touched more recently. LFU kept A because it was used more often. Neither is “better”; they bet on different patterns. LFU’s weakness is the opposite: a key that was popular yesterday keeps its high count and can sit in the cache long after it stops being useful. Real systems often blend the two.

Notice this is a sibling class implementing the same Cache interface, not a policy plugged into LRUCache. That’s the decision from step 7, now justified: the data structures are completely different.

“Can’t you just use LinkedHashMap?”

Yes. LinkedHashMap can keep entries in access order, and lets you decide when to drop the eldest:

final class JdkLru extends LinkedHashMap {
    private final int capacity;
    JdkLru(int capacity) { super(16, 0.75f, true); this.capacity = capacity; } 1
    @Override protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > capacity; 2
    }
}

LinkedHashMap version: [C, A, D]

(It prints least recent first, the opposite of our trace, but it’s the same order: put A, B, C, get A, put D evicted B.)

Say this in the interview, early. It shows you know the library. Then the interviewer will almost always say “now build it yourself”, because the point of the question is the data structures. It’s also not thread-safe, and it briefly holds capacity + 1 entries during a put, since it removes the eldest after inserting. In real code, for a single-threaded cache, it’s a perfectly good choice.

A cache shared by many servers

That’s no longer a low-level design question. It becomes a separate cache service, like Redis or Memcached, reached over the network, with questions about which server holds which key, what happens when one dies, and how stale data is kept in check. The caching lesson covers that side. A good answer here names the boundary: “Inside one process, this class. Across servers, a cache service, and this class can still sit in front of it as a small local layer for the hottest keys.”

Mistakes people make on this one

• Reciting “hash map plus doubly linked list” without explaining why simpler structures fail.
• A singly linked list, then discovering unlink is O(n).
• Forgetting the key in the node, so eviction can’t clean the map.
• Updating an existing key by evicting first, so the cache loses an entry for nothing.
• Inserting before evicting, so the cache briefly holds one entry too many.
• *Using Java’s LinkedList* and calling remove(object), which searches.
• No sentinels, and a tangle of null checks with one missing.
• ”Use ConcurrentHashMap” as the whole thread-safety answer. The list still breaks.
• A read-write lock, without noticing that every get writes.
• Calling the eviction listener inside the lock.
• *Picking shards with hash % n* and colliding with the map’s own buckets.

How this answer gets scored

The whole design on one page

1. Structures: a HashMap to find, a DoublyLinkedList to order. The map points into the list.
2. Details: doubly linked (O(1) unlink), the node keeps its key (O(1) eviction), sentinels at both ends (no null checks).
3. get: look up, move to front, return. A miss touches nothing.
4. put: existing key → update and move to front. New key → evict the last node if full (list and map), then add at front. Tell listeners after unlocking.
5. Threads: every get writes, so a safe map or a read-write lock isn’t enough. One lock is correct; shards scale, chosen by well-mixed high bits.
6. Follow-ups: Cache interface → wrappers for expiry and statistics; LFU as a sibling class; LinkedHashMap when you’re allowed.