Design an LRU Cache

1Clarify the requirements#

Pin down what "LRU" means to this interviewer before drawing a single box. The word "cache" hides a dozen decisions, and the wrong assumption early costs you the whole round.

Questions I ask out loud:

• Fixed capacity? Yes, there is a maximum number of entries, say capacity = 3. When we are full and a new key comes in, we evict the least recently used one. That is the contract.
• What counts as "use"? Both reads and writes. A get on a key makes it most recently used. So does a put. People forget the read part and then LRU quietly degrades into FIFO, which is a different cache with a different hit rate.
• Key and value types? Generic. I design it for K and V. Keys are hashable and comparable by equality, since they go into a hash map.
• What does get return on a miss? Null, or an Optional. I pick null to match the mental model most people have, and I say out loud that Optional<V> is the cleaner API if they prefer it.
• Updating an existing key? A put on a key that already exists updates the value and marks it most recently used. It does not count against capacity twice, so it must not trigger an eviction.
• Thread safety? This is the big one. I ask if it is single-threaded or shared across threads. The naive design is single-threaded. Concurrency changes everything about the code, so I design single-threaded first, get it correct, then layer safety on. Designing both at once is how you ship a broken list.

Functional scope

• get(key): return the value or null, mark as most recently used.
• put(key, value): insert or update, mark as most recently used, evict if over capacity.
• Optional: size(), clear(), and a hook for "what got evicted."

Non-functional scope

• Both get and put must be O(1) average time. This is the real requirement. If they let me do O(n), it is not an interview, it is a nap.
• Bounded memory: at most capacity entries plus bookkeeping. No slow leak of dead nodes.
• Predictable, deterministic eviction order.

That O(1) constraint is the whole game.

• A plain HashMap is not enough: you cannot find the oldest entry in O(1).
• A plain list is not enough: lookup is O(n).
• You need both structures cooperating, and the entire design falls out of that single tension.

2Identify the core entities#

Here is the insight I want to land on the board in the first few minutes: I need two structures that point at the same nodes.

• A hash map for O(1) lookup by key.
• A doubly linked list for O(1) reordering and eviction.

How the two cooperate.

• The map does not store values directly. It stores references to nodes that live in the list.
• When I touch a key, I find its node through the map in O(1), then unlink and relink that node in O(1).
• The map answers "where is this key." The list answers "what order are things in."
• They share the same node objects, so neither one ever goes O(n). Everything else is plumbing.

The entities:

• Node. Holds a key, a value, and prev/next pointers. The key lives in the node too, not just the map, because when I evict the tail node I need its key to delete it from the map. Forget this and your O(1) eviction silently becomes an O(n) map scan.
• DoublyLinkedList. Owns the order. Head side is most recently used, tail side is least recently used. I keep dummy head and tail sentinels so I never write a null check for empty-list edge cases. This single decision removes half the bugs you can make in this problem.
• LRUCache. The public facade. Holds the map and the list, enforces capacity, exposes get/put.
• EvictionListener (optional). An observer so callers can react when something gets evicted. Useful for write-back caches and metrics.

3Class design#

The design is deliberately boring, and boring is correct here.

• LRUCache composes a DoublyLinkedList and a Map.
• The map's values are Nodes owned by the list.
• LRUCache optionally notifies EvictionListeners.
• If you find yourself inventing something clever, you have probably taken a wrong turn.

Why sentinels in the list?

• A real doubly linked list spends most of its bug budget on "what if it is the first node" and "what if it is the last node."
• Two permanent dummy nodes mean every real node always has a non-null prev and next.
• Insert and remove become three-line operations with zero branching.
• The empty list is just head.next == tail.

What the composition arrows are telling you.

• The list owns its nodes (*--): kill the list, the nodes go with it.
• The cache references nodes through the map (o--) but does not own them. The list does.
• The cache holds the list as a part it fully owns.
• Getting ownership right in the diagram is the lifecycle signal, not the boxes.

4Key implementation#

Start with the node. Nothing clever, just a struct with pointers.

class Node<K, V> {
    K key;
    V value;
    Node<K, V> prev;
    Node<K, V> next;

    Node(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

Now the list. This is where the sentinels earn their keep. head.next is always the most recently used node, tail.prev is always the least recently used. Every operation is unconditional pointer surgery with no if (node == null) anywhere.

class DoublyLinkedList<K, V> {
    private final Node<K, V> head = new Node<>(null, null);
    private final Node<K, V> tail = new Node<>(null, null);

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

    void addFront(Node<K, V> node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    void remove(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    void moveToFront(Node<K, V> node) {
        remove(node);
        addFront(node);
    }

    Node<K, V> removeLast() {
        if (tail.prev == head) {
            return null; // empty
        }
        Node<K, V> last = tail.prev;
        remove(last);
        return last;
    }
}

The move worth pointing at:

• moveToFront is just remove then addFront. No special case for "already at front."
• It costs a few redundant pointer writes in that one case, and I take that trade every day for code I cannot get wrong on a whiteboard.
• The interviewer notices when you reuse remove instead of rewriting the four pointer assignments a second time.

Now the cache itself, which is almost anticlimactic once the list is solid.

public class LRUCache<K, V> {
    private final int capacity;
    private final Map<K, Node<K, V>> map = new HashMap<>();
    private final DoublyLinkedList<K, V> list = new DoublyLinkedList<>();
    private final List<EvictionListener<K, V>> listeners = new ArrayList<>();

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

    public V get(K key) {
        Node<K, V> node = map.get(key);
        if (node == null) {
            return null;
        }
        list.moveToFront(node);
        return node.value;
    }

    public void put(K key, V value) {
        Node<K, V> existing = map.get(key);
        if (existing != null) {
            existing.value = value;
            list.moveToFront(existing);
            return;
        }
        Node<K, V> node = new Node<>(key, value);
        map.put(key, node);
        list.addFront(node);
        evictIfNeeded();
    }

    private void evictIfNeeded() {
        if (map.size() <= capacity) {
            return;
        }
        Node<K, V> evicted = list.removeLast();
        if (evicted != null) {
            map.remove(evicted.key);
            for (EvictionListener<K, V> l : listeners) {
                l.onEvict(evicted.key, evicted.value);
            }
        }
    }

    public int size() {
        return map.size();
    }

    public void addListener(EvictionListener<K, V> l) {
        listeners.add(l);
    }
}

And the listener contract:

public interface EvictionListener<K, V> {
    void onEvict(K key, V value);
}

5Design decisions and patterns used#

I keep the pattern-name-dropping honest. I only call out a pattern if it genuinely shaped the code, because interviewers can smell a candidate reciting a GoF index.

• Facade. LRUCache is a clean front for a two-part machine. Callers see get/put and never touch the list or the node wiring. That separation is the point: I can swap the internals (a different list, a concurrent map) without changing the public surface.
• Observer. EvictionListener lets callers subscribe to evictions without the cache knowing or caring who is listening. This is exactly how you would build a write-back cache that flushes evicted dirty entries to disk, or emit a metric on every eviction. The cache stays decoupled from what happens next.
• Strategy (as an extension). Right now eviction is hardwired to "remove the tail." If the interviewer asks for pluggable policies (LRU vs LFU vs FIFO), I extract an EvictionPolicy interface and inject it. I would not build that up front, because you are not going to need it yet, but I name it as the natural seam so they know I see it.

The sentinel choice is the real call.

• It is not a named pattern, but it is the most important design decision in the whole thing.
• It converts a branchy, error-prone list into straight-line code.
• The principle, if I had to name it, is "make illegal states unrepresentable": with sentinels there is no such thing as a null neighbor, so there is no bug to write.

Guard the invariant.

• I keep the map and list as private fields, never exposed.
• The invariant is sacred: every key in the map has exactly one node in the list, and every node in the list has exactly one key in the map.
• The moment that invariant leaks out of the class, someone breaks it, and a corrupted linked list is a nightmare to debug.
• Naming the invariant explicitly is a senior move.

6Handling edge cases and concurrency#

The edge cases first, because they are where interviewers poke:

• Capacity of zero or negative. Reject in the constructor with IllegalArgumentException. A cache that can hold nothing is a bug, not a feature.
• put on an existing key. Must update the value and move to front, but must NOT evict and must NOT grow the map. My code handles this by returning early before the insert path, so map.size() never crosses capacity on an update.
• get on a missing key. Return null, touch nothing. Do not accidentally create an entry, a classic bug if you reach for computeIfAbsent.
• Null keys or values. I ask. If allowed, HashMap tolerates one null key, but I usually reject nulls to keep the contract clean. State your choice and move on, do not burn two minutes on it.
• Single-element cache. With capacity 1, every put of a new key evicts the previous one. The sentinel list handles this without a special case, which is the payoff for the dummy nodes. If your code needs an if here, your list is wrong.

Concurrency is the follow-up that separates the senior candidates.

• The design above is not thread safe.
• Two threads calling put at the same time can corrupt the linked list, because addFront does four pointer writes that must be atomic as a group.
• Interleave two of them and you get a cycle or a dropped node, and now you have a heisenbug in production.

The honest first answer: wrap get and put in a single lock. Simple, correct, and often good enough. Say this first, then earn the nuance.

private final ReentrantLock lock = new ReentrantLock();

public V get(K key) {
    lock.lock();
    try {
        // same body as before
    } finally {
        lock.unlock();
    }
}

If the interviewer pushes on throughput, I reach for sharding.

• Split the key space into N independent caches, each with its own lock, each with capacity total/N.
• Route by hash(key) % N. Contention drops by roughly N.
• The tradeoff: LRU becomes approximate across shards, since eviction is per-shard, not global, so a globally hot key in a cold shard can still get evicted.
• For most real caches that is a fine trade. This is essentially what high-performance caches like Caffeine and Guava do under the hood, and reasoning about it out loud is what "senior" sounds like.

The lock-free direction, named honestly.

• ConcurrentHashMap plus a lock-free ordering structure is the truly concurrent option.
• I am upfront that doing recency tracking lock-free is genuinely hard, usually involves accepting approximate ordering, and is almost never worth hand-rolling in a 45-minute interview.

7Extensions and follow-ups#

Where interviewers tend to steer next, and how I answer each in a sentence or two:

• TTL / expiry. Add an expiresAt timestamp to Node. On get, if it is expired, treat it as a miss and remove it. For proactive cleanup, a background sweeper or a second structure ordered by expiry. Lazy expiry on read is the cheap, usually-sufficient answer.
• LFU instead of LRU. Now I need frequency counts, and the clean O(1) LFU design uses a map of frequency buckets, each bucket being its own linked list, plus a minFreq pointer. This is where I pull out the EvictionPolicy strategy seam I mentioned earlier.
• Thread-safe with high read volume. Sharding, as above. Or accept approximate LRU and only reorder on a sampled fraction of reads, say 1 in 16, to cut lock contention hard while keeping recency roughly right.
• Persistence / write-back. This is the EvictionListener paying off. On eviction, the listener flushes the value to a backing store. On a miss, the cache could fall through to that store and populate itself, which turns this into a read-through cache.
• Bounded by memory, not count. Instead of counting entries, track a size estimate per value and evict until under a byte budget, say 100 MB. Changes evictIfNeeded from an if to a while loop over total weight.

Each of these is a small, localized change precisely because the core is clean. That is the message I want the interviewer to take away.

A good core makes extensions cheap, and cheap extensions are what a real codebase lives or dies on.

If you liked this, look at the LFU Cache problem next: same two-structure thinking, one level harder. And read up on the Observer and Strategy patterns, since both show up again in rate limiters and connection pools.