Cruxly › Low-level design › LLD Exercises

LRU Cache

two structures in lockstep, every operation O(1)

Prompt: design an LRU cache. get(key) and put(key, value), both O(1), fixed capacity, evicting the least recently used entry when full.

Then: make it thread-safe. Then: add per-entry TTL.

Applying the five moves: the nouns are almost a trick question — there is exactly one domain noun, Entry (key, value, and whatever recency bookkeeping it needs), and the temptation to invent a "Cache" class with extra ceremony around it is worth resisting. The invariant is "the structure the hash map and the list agree on is always the same structure" — every method that touches one touches the other, in the same call, or the two silently diverge. There's no interface seam here worth adding (an EvictionPolicy interface is over-engineering for a fixed LRU rule — name that explicitly rather than adding it reflexively). The concurrency sentence matters most on the follow-up: "thread-safe" turns one lock around the whole structure into the honest first answer, with a sharded/striped-lock alternative named as the thing you'd reach for only once contention is measured, not guessed at.

Why one structure is never enough

Two requirements pull in opposite directions:

• Find a key in O(1) → hash map. But a hash map has no recency order.
• Move an entry to "most recent" in O(1), and drop the least recent in O(1) → doubly-linked list. But a list has no lookup.

An array of entries sorted by recency makes get O(n). A heap by timestamp makes updates O(log n), not O(1). A singly-linked list can't unlink a node in O(1) because you can't reach its predecessor. Each near-miss is worth a sentence out loud — it shows the choice was derived, not recalled.

The design: HashMap<K, Node> plus a doubly-linked list of the same Node objects. The map finds the node; the node's prev/next let you unlink and re-link it in constant time. The two structures hold the same objects, which is exactly why they can drift if you update one and forget the other.

The classes — full implementation

public class LRUCache<K, V> {

    /** Doubly-linked so a node can unlink itself in O(1) without a scan. */
    private static final class Node<K, V> {
        final K key;            // back-reference: needed to evict from the map
        V value;
        Node<K, V> prev, next;

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

    private final Map<K, Node<K, V>> index = new HashMap<>();
    private final int capacity;

    /** Sentinels. Never hold real data; they remove every edge case. */
    private final Node<K, V> head = new Node<>(null, null);
    private final Node<K, V> tail = new Node<>(null, null);

    public LRUCache(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be > 0");
        this.capacity = capacity;
        head.next = tail;       // empty list is head <-> tail
        tail.prev = head;
    }

    // ---------------------------------------------------------- list helpers

    private void unlink(Node<K, V> n) {
        n.prev.next = n.next;   // no null checks: sentinels guarantee both exist
        n.next.prev = n.prev;
        n.prev = n.next = null; // help GC, and make a double-unlink crash loudly
    }

    private void insertAfterHead(Node<K, V> n) {
        n.next = head.next;
        n.prev = head;
        head.next.prev = n;
        head.next = n;
    }

    private void moveToFront(Node<K, V> n) {
        unlink(n);
        insertAfterHead(n);
    }
}

The sentinel trick is the highest-value detail here. Without head and tail dummies, unlink needs if (n.prev == null) and if (n.next == null) branches, and the empty-list case needs its own. With them, every real node always has a non-null prev and next, so the helpers above are branch-free. Candidates who have only read about this structure produce the branchy version.

Node stores its own key. Non-obvious but essential — see put below: on eviction you hold the tail node and must remove it from the map, which needs the key. Without the back-reference, eviction degrades to scanning the map for the matching value, and the cache is no longer O(1).

get and put, and the lockstep rule

    public V get(K key) {
        Node<K, V> n = index.get(key);
        if (n == null) return null;
        moveToFront(n);            // a read IS a mutation — see concurrency below
        return n.value;
    }

    public void put(K key, V value) {
        Node<K, V> existing = index.get(key);
        if (existing != null) {
            existing.value = value;
            moveToFront(existing);
            return;                // NOT a new entry: do not evict
        }

        if (index.size() == capacity) {
            Node<K, V> victim = tail.prev;     // least recently used
            unlink(victim);                    // 1. out of the list
            index.remove(victim.key);          // 2. out of the map (needs back-ref)
        }

        Node<K, V> n = new Node<>(key, value);
        index.put(key, n);                     // 1. into the map
        insertAfterHead(n);                    // 2. into the list
    }

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

The lockstep rule: every mutation touches both structures, or neither.

The two structures hold the same node objects, so they can drift. Each of these is a real bug someone has written in an interview:

That last one is why put returns early on the update path — it is the easiest to miss because the cache still works, just with quietly reduced capacity.

Stating this as a rule — both structures or neither — beats enumerating bugs, because it generalises directly to the TTL follow-up below.

Thread safety, and why the obvious answer is weak

get mutates. That surprises people: a read reorders the list, so there is no read-only path and a read-write lock buys nothing — every operation takes the write lock anyway. Say that explicitly; proposing a ReadWriteLock here is a common wrong answer that sounds sophisticated.

Baseline: one lock over both structures.

public synchronized V get(K key) { ... }     // same monitor
public synchronized void put(K key, V v) { ... }

Correct, because the invariant spans both structures and any finer lock lets them drift. Simple, and entirely defensible for a single cache instance.

When contention matters: shard.

public class ShardedLRU<K, V> {
    private final LRUCache<K, V>[] shards;

    @SuppressWarnings("unchecked")
    public ShardedLRU(int totalCapacity, int shardCount) {
        shards = new LRUCache[shardCount];
        int per = Math.max(1, totalCapacity / shardCount);
        for (int i = 0; i < shardCount; i++) shards[i] = new LRUCache<>(per);
    }

    private LRUCache<K, V> shardFor(K key) {
        int h = key.hashCode();
        h ^= (h >>> 16);                           // spread poor hashes
        return shards[Math.floorMod(h, shards.length)];
    }

    public V get(K key)            { return shardFor(key).get(key); }   // sync inside
    public void put(K key, V val)  { shardFor(key).put(key, val); }
}

Different keys usually land on different shards and never contend — the same idea as Java's old ConcurrentHashMap lock striping.

Name the cost: capacity is now per-shard, so eviction is per-shard. A hot shard evicts while a cold one has room, so this is no longer globally exact LRU. For a cache that is virtually always the right trade — but it is a trade, not a free win, and saying so is the difference between knowing the technique and understanding it.

What about just using ConcurrentHashMap for the index? It makes the map thread-safe but not the pair. The linked list still needs the lock, and a lock-free map behind a locked list gains nothing. One sentence, but it shows you know where the invariant actually lives.

TTL — where the lockstep rule pays off

Add expiresAt to Node. Now get must treat an expired entry as a miss.

    private static final class Node<K, V> {
        final K key;
        V value;
        long expiresAtNanos;        // Long.MAX_VALUE == never expires
        Node<K, V> prev, next;
    }

    public V get(K key) {
        Node<K, V> n = index.get(key);
        if (n == null) return null;

        if (clock.getAsLong() >= n.expiresAtNanos) {
            unlink(n);                 // both structures, or neither —
            index.remove(n.key);       // the same rule as eviction
            return null;               // expired reads as a miss, not a hit
        }

        moveToFront(n);
        return n.value;
    }

    public void put(K key, V value, long ttlNanos) {
        long expiry = ttlNanos == 0 ? Long.MAX_VALUE
                                    : clock.getAsLong() + ttlNanos;
        // ... same as before, plus: n.expiresAtNanos = expiry;
    }

Lazy expiry on read. Cheap, no background machinery, and it reuses the both-or-neither discipline directly — which is exactly why stating that rule earlier pays off rather than having to re-derive it here.

The problem with lazy-only: an expired entry that is never read again occupies capacity forever, and can even be evicted later than a live entry, which inverts the whole point. Options: a periodic sampling sweep (Redis's approach — check a random subset, repeat if the expired fraction is high), or a second structure ordered by expiry.

Do not add a min-heap by expiry without saying what it costs. It restores O(log n) to put, which breaks the stated O(1) requirement. If the interviewer wants strict TTL eviction, that is the trade and it should be said out loud rather than quietly accepted.

LRU + TTL is two eviction policies at once, and they can disagree about which entry to drop. Ask which wins. It is a real ambiguity in the requirements, and noticing it is worth more than picking one silently.

How to say it in the interview

"A hash map gives O(1) lookup but no ordering; a linked list gives O(1) reordering but no lookup. Neither alone works — the design is the two of them kept in lockstep, and the bug is always in the lockstep."

Checklist

• Ruled out array/heap/singly-linked options with a stated reason each
• Used sentinel head/tail nodes to remove every edge-case branch
• Stored the key on the node so eviction can remove it from the map in O(1)
• Stated the both-or-neither rule rather than enumerating individual bugs
• Recognised that get() mutates, so a read-write lock buys nothing
• Offered sharding for contention and named the exact-LRU accuracy it costs
• Handled TTL lazily on read, reusing the lockstep discipline
• Named the cost of strict TTL eviction (O(log n) put) rather than accepting it silently
• Noticed that LRU and TTL are two policies that can disagree, and asked which wins

Related lessons

• Rate Limiter
• Elevator Bank
• Expense Splitting
• Chess / Game Board
• Logging Framework
• Vending Machine