LRU Cache

1. Problem & Core Objective

Design a cache with a fixed capacity supporting:

get(key)         // return the value, or -1 if absent
put(key, value)  // insert or update; if over capacity, evict the LEAST recently used key

Both operations must run in O(1) average time.

LRUCache c = new LRUCache(2);
c.put(1,1);  c.put(2,2);
c.get(1);          → 1        (1 is now the most recently used)
c.put(3,3);                   (over capacity → evicts key 2, the least recently used)
c.get(2);          → -1

Constraints: 1 <= capacity <= 3000 · up to 2 × 10^5 calls · both get and put count as uses

What's actually being tested: recognising that no single data structure does this, and combining two so that each covers the other's weakness. It's the canonical "compose two structures" design question.

2. First-Principles Thought Process

Two requirements that pull in opposite directions

1. Find a key in O(1) → hash map. But a hash map has no order.
2. Know which key is least recently used, and update that ordering in O(1) → an ordered structure. But ordered structures can't search in O(1).

Neither alone suffices. That tension is the problem.

Why the obvious single structures fail

• Hash map alone — finding the LRU entry means scanning every key for the oldest timestamp: O(n) per eviction.
• Array or ArrayList alone — keeping most-recent-last means removing from the middle and shifting: O(n).
• Queue alone — you can pop the oldest, but on a get you must move an arbitrary element to the back, and finding it is O(n).
• PriorityQueue by timestamp — O(log n) per operation, and removing an arbitrary element is O(n). Close, but not O(1).

The combination

• A doubly linked list holds the keys in recency order: least-recently-used at the front, most-recently-used at the back.
• A hash map maps each key directly to its node in that list.

Now every operation is O(1):

Why the list must be doubly linked

To unlink a node you must rewire its predecessor. In a singly linked list, finding the predecessor means scanning from the head — O(n), which destroys the whole design. A prev pointer hands it to you immediately.

That's the single most important design decision here, and it's the question you'll be asked.

Why sentinel head and tail nodes

Without them, inserting into an empty list, removing the only node, and removing at either end each need their own branch. Two permanent dummy nodes mean every real node always has both a prev and a next, so unlink and insert are branch-free.

Same idea as the dummy head in questions 2, 4 and 6 — make the special case stop being special.

3. Solution Paths

Approach 1 — Hash map plus timestamps (brute force)

class LRUCache {
    private final Map<Integer, int[]> map = new HashMap<>();   // key -> {value, lastUsed}
    private final int capacity;
    private int clock = 0;

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

    public int get(int key) {
        int[] e = map.get(key);
        if (e == null) return -1;
        e[1] = clock++;
        return e[0];
    }

    public void put(int key, int value) {
        if (!map.containsKey(key) && map.size() == capacity) {
            int oldest = -1, oldestTime = Integer.MAX_VALUE;
            for (var en : map.entrySet())                       // scan everything
                if (en.getValue()[1] < oldestTime) { oldestTime = en.getValue()[1]; oldest = en.getKey(); }
            map.remove(oldest);
        }
        map.put(key, new int[]{value, clock++});
    }
}

• Time get O(1), put O(n) on eviction · Space O(n)

Counter-questions on this approach

⭐ "get is O(1). Why isn't that good enough?"

Because put isn't. Finding the oldest entry means scanning all n entries, and that happens on every eviction — which, once the cache is full, is most put calls. With capacity 3000 and 2 × 10^5 calls that's up to 6 × 10^8 comparisons.

The root issue is that the map stores recency as data rather than as structure. A timestamp has to be searched for; a position in a list can be read off directly.

"Could you keep a heap of timestamps alongside the map?"

That gets eviction to O(log n), but get must now update an element's priority, and finding it inside a binary heap is O(n) unless you also maintain an index map. At that point you've built something more complicated than the linked list, and it's still O(log n) rather than O(1).

"Does the clock ever overflow?"

At 2 × 10^5 calls, no. But it's worth noticing that correctness depends on a monotonically increasing counter that could in principle wrap — another sign that storing recency as a number is the weaker model. The list version has no such counter.

Approach 2 — LinkedHashMap in access-order mode

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private final int capacity;

    LRUCache(int capacity) {
        super(capacity, 0.75f, true);        // true = ACCESS order, not insertion order
        this.capacity = capacity;
    }

    public int get(int key) { return super.getOrDefault(key, -1); }
    public void put(int key, int value) { super.put(key, value); }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

• Time O(1) both · Space O(n)

Counter-questions on this approach

⭐ "This is ten lines and meets the bound. Why would anyone write more?"

Because LinkedHashMap is a hash map plus a doubly linked list — it's the exact structure the question is asking me to build, with the interesting part already implemented. Submitting it answers "do you know the library" rather than "do you understand the design".

In production it's the right choice, and I'd say so. In an interview I'd show it, explain that it's precisely the hand-rolled design, and then build it out.

"What does the true in the constructor actually change?"

It switches the internal list from insertion order to access order, so every get moves the entry to the end of the list. Without it, get doesn't count as a use and the eviction policy silently becomes FIFO rather than LRU — a bug that passes casual testing. See 02 §2.

"When is removeEldestEntry called?"

After each put inserts a new entry. Returning true makes the map drop its eldest entry — "eldest" meaning least-recently-accessed in access-order mode. Note it fires only on insertion, so a pure get never evicts, which is what you want.

Approach 3 — Hash map plus a hand-built doubly linked list (the intended answer)

class LRUCache {
    private static class Node {
        int key, value;
        Node prev, next;
        Node(int k, int v) { key = k; value = v; }
    }

    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0);     // sentinel: LRU side
    private final Node tail = new Node(0, 0);     // sentinel: MRU side
    private final int capacity;

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

    private void unlink(Node n) {                 // no null checks — sentinels guarantee both sides
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }

    private void pushBack(Node n) {               // insert just before tail = most recently used
        n.prev = tail.prev;
        n.next = tail;
        tail.prev.next = n;
        tail.prev = n;
    }

    public int get(int key) {
        Node n = map.get(key);
        if (n == null) return -1;
        unlink(n);
        pushBack(n);                              // touching it makes it most recent
        return n.value;
    }

    public void put(int key, int value) {
        Node n = map.get(key);
        if (n != null) {                          // update in place
            n.value = value;
            unlink(n);
            pushBack(n);
            return;
        }
        if (map.size() == capacity) {             // evict the node after head
            Node lru = head.next;
            unlink(lru);
            map.remove(lru.key);                  // key stored IN the node — see below
        }
        Node fresh = new Node(key, value);
        map.put(key, fresh);
        pushBack(fresh);
    }
}

• Time O(1) for both · Space O(n)

Counter-questions on this approach

⭐ "Why does the node store the key as well as the value?"

For eviction. When I remove the LRU node from the list, I also have to remove it from the map — and map.remove needs the key. Walking from a node, I have no other way to recover which key it was filed under.

Without it you'd need a second map from node back to key, which is absurd. One extra field turns eviction from impossible into O(1). This is the detail interviewers probe most.

⭐ "Why doubly linked rather than singly?"

Unlinking a node requires rewiring its predecessor: n.prev.next = n.next. In a singly linked list the only way to find the predecessor is to walk from the head, which is O(n) and destroys the entire design.

get unlinks an arbitrary node — one found by hash lookup, not by traversal — so I have no context around it. The prev pointer is what makes that O(1).

⭐ "Why the sentinel head and tail?"

They guarantee every real node has a non-null prev and next, so unlink and pushBack need no null checks and no branches for the empty, single-element, or at-the-end cases. Without them, unlink alone needs three branches, and each is a place to introduce a bug.

It's the same dummy-node idea as in questions 2, 4 and 6, used twice — once at each end.

"Why does put on an existing key still unlink and re-insert?"

Because put counts as a use. Updating the value without moving the node would leave it in its old recency position, and it could then be evicted despite having just been written. That's a genuine LRU bug and a common one.

"What if capacity were 0?"

Every put would need to evict immediately, and map.size() == capacity is 0 == 0, so it tries to evict from an empty list and unlinks a sentinel — corrupting the structure. The constraint says capacity >= 1, so it can't happen, but I'd guard it in real code rather than rely on the caller.

"Is O(1) here worst case or average?"

Average. The list operations are genuinely worst-case O(1), but HashMap degrades to O(log n) per operation under heavy collision (Java treeifies long buckets). With Integer keys and default hashing that's not a practical concern, but "O(1) average" is the honest claim.

Comparison

4. Why the Optimal Wins

The timestamp version fails because it stores recency as a value — and values must be searched for. The list stores recency as a position, and position is read directly: the node after head is the LRU, always, with no comparison performed.

That's the general lesson. When you need both "find by key" and "find by order", you need two structures with a pointer between them. The map's values are the list's nodes, so a hash lookup lands you exactly where the list surgery has to happen.

LinkedHashMap wins in production and loses in an interview, because it is this design with the interesting part hidden.

The framing worth keeping:

No single structure gives both O(1) lookup and O(1) ordered update. Use a hash map whose values are nodes of a doubly linked list — each covers the other's blind spot.

5. Java Prerequisites

Unlink with sentinels — branch-free because both sides always exist:

n.prev.next = n.next;
n.next.prev = n.prev;

Insert before the tail sentinel — order matters; wire the new node first:

n.prev = tail.prev;
n.next = tail;
tail.prev.next = n;
tail.prev = n;

Sentinel initialization — do this in the constructor or the first insert corrupts:

head.next = tail;
tail.prev = head;

LinkedHashMap access order

new LinkedHashMap<>(capacity, 0.75f, true);   // the third arg is the whole feature
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return size() > capacity; }

See 02 §2 for the full LinkedHashMap treatment.

6. Interview Communication Guide

Clarifying questions: Does get count as a use (yes — it's the crux of LRU vs FIFO)? Does updating an existing key count as a use (yes)? What should get return for a missing key (-1)? Can capacity be 0 (no, >= 1)? Must it be thread-safe (usually no — but worth asking)?

The pitch

"Two requirements pull against each other. Finding a key in O(1) wants a hash map, but a hash map has no ordering. Knowing the least-recently-used key wants an ordered structure, but those can't search in O(1). So no single structure works — I need two, wired together.

A doubly linked list holds keys in recency order: LRU at the front, MRU at the back. A hash map maps each key to its node in that list. So a lookup lands me directly on the node I need to move.

Then everything is O(1). get: map lookup, unlink the node, re-insert at the back. put on an existing key: same, plus update the value — and it must move, because a write counts as a use. put on a new key when full: drop the node right after head, which is the LRU.

Two design points I'd highlight. The list must be doubly linked, because unlinking an arbitrary node needs its predecessor, and finding that in a singly linked list is O(n) — which would defeat the whole design. And each node stores its key as well as its value, because on eviction I have the node but need the key to remove it from the map.

I use sentinel head and tail nodes so every real node always has both neighbours — unlink and insert become branch-free, with no special cases for empty, single-element, or at-the-ends.

O(1) average for both operations, O(n) space.

In production I'd just use LinkedHashMap with access-order true and override removeEldestEntry — but that is this structure, with the part you're asking about already written."

Edge cases to volunteer:

Name the "get then put" case. It's the one that distinguishes LRU from FIFO, and an implementation that forgets to move the node on get passes most other tests.

7. Follow-Up Questions — Modified Constraints

⭐ "Make it LFU — evict the least frequently used instead."

LeetCode 460, and substantially harder. You need a count per key, plus a map from count to a list of keys with that count, plus a running minimum frequency. On access, move the key from its frequency bucket to the next one up. Still O(1) if each bucket is itself a doubly linked list, but there are three structures instead of two and the bookkeeping is much fussier. Ties within a frequency are broken by recency, so each bucket is itself an LRU list.

⭐ "Make it thread-safe."

A single lock around both operations is correct and simple, but serialises everything — and since get mutates the list, even reads need the write lock, so a ReadWriteLock buys nothing. Better approaches: sharding into N independent caches by key hash, which is what Guava and Caffeine do, or an approximate policy that batches the recency updates so reads don't contend. Worth saying that exact LRU is inherently contention-heavy, which is why real caches approximate it.

"Add a TTL — entries expire after a fixed time."

Add an expiry timestamp per node and check it on get, treating an expired entry as a miss and unlinking it lazily. For proactive eviction, keep a second structure ordered by expiry — a min-heap or a second list, since insertions are already in expiry order if the TTL is constant.

"What if the cache were too large for memory?"

Tier it: a small in-memory LRU in front of a disk-backed store, which is exactly how a database buffer pool works. At that point you'd also reconsider the policy — real systems often use LRU-K or CLOCK, because strict LRU is both expensive to maintain and vulnerable to a scan wiping the whole cache.

"What's wrong with LRU as a policy?"

A single large scan touches every key once and evicts everything useful — the classic scan-resistance failure. LRU-K, 2Q, and ARC all exist to fix it by requiring more than one access before promotion. Good to raise unprompted, since it shows you're thinking about the cache, not just the data structure.

"Implement it without a hash map."

You can't hit O(1) lookup. A balanced BST keyed by key gives O(log n), and a trie gives O(key length). The hash map is doing genuinely irreplaceable work here.