Loading…

mediumLinked ListsLC #146Asked very often

LRU Cache

Q: How do you solve LRU Cache using the Built-in Ordered Map (LinkedHashMap / OrderedDict) approach?

When to use it: Mention it first to show you know the language and the production shortcut — then say 'but let me build it from scratch to show the mechanics'. The shortest correct answer reuses a library structure that *is* a hash map backed by a linked list. **Java — LinkedHashMap in access-order mode.** Constructing it with `new LinkedHashMap<>(capacity, 0.75f, true)` makes it reorder entries on every access (get/put) so the eldest entry is the least recently used. Overriding `removeEldestEntry` to return `size() > capacity` lets the map evict automatically on insert. `get` returns the value or -1. **Python — OrderedDict.** `move_to_end(key)` marks a key most-recently-used; `popitem(last=False)` removes the least-recently-used (front). On `get` we move the key to the end and return its value; on `put` we overwrite, move to end, and pop the front if we're over capacity. **Why mention it at all.** In real code this is the right answer — fewer lines, fewer bugs. But interviewers almost always follow with 'now implement it without that' because the *point* of the question is whether you understand the underlying map + doubly linked list. Naming the shortcut shows language fluency; the from-scratch build shows data-structure fluency. Time complexity: O(1). Space complexity: O(capacity).

LCPractice

Linked List · 7 of 24 · 12 min

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

LRUCache(int capacity) initializes the cache with positive size capacity.
int get(int key) returns the value of the key if it exists, otherwise returns -1.
void put(int key, int value) updates the value if the key exists; otherwise adds the key-value pair. If inserting causes the number of keys to exceed capacity, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

In plain English

We need a fixed-size key-value store where reading or writing a key marks it 'most recently used', and once we exceed capacity we drop whichever key was used longest ago. The O(1) requirement on both operations is the crux — it forces a combination of structures rather than a single one.

Examples

Example 1

Input: LRUCache(2); put(1,1); put(2,2); get(1); put(3,3); get(2); put(4,4); get(1); get(3); get(4)
Output: get(1)=1, get(2)=-1, get(1)=-1, get(3)=3, get(4)=4
Note: put(3,3) evicts key 2 (LRU); put(4,4) evicts key 1; so get(2) and the later get(1) miss.

Example 2

Input: LRUCache(1); put(1,1); put(2,2); get(1); get(2)
Output: get(1)=-1, get(2)=2
Note: Capacity 1: put(2,2) evicts key 1 immediately, so get(1) misses.

Example 3

Input: LRUCache(2); put(1,1); put(1,10); get(1)
Output: get(1)=10
Note: Updating an existing key overwrites its value and refreshes recency without adding a new entry.

Constraints

1 ≤ capacity ≤ 3000
0 ≤ key ≤ 10⁴
0 ≤ value ≤ 10⁵
At most 2 × 10⁵ calls to get and put
Both get and put must be O(1) average time

Clarifying questions4First question: Does a get count as a use (i.e. refresh recency)?Explore questions

Q1.Does a get count as a use (i.e. refresh recency)?
Yes — every successful get moves that key to most-recently-used. So does an update via put.
Q2.What does get return on a missing key?
-1, per the spec. I'll assume real values are non-negative so -1 is an unambiguous miss sentinel.
Q3.When does eviction happen, and which key goes?
Only on an insert that pushes the size above capacity, and we evict the least recently used key — the one at the tail of the recency list.
Q4.Can I use a built-in like LinkedHashMap or OrderedDict?
I'll mention it as the production shortcut, but build the map + doubly linked list from scratch since that's what the interviewer is usually testing.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Combine a hash map with a doubly linked list. The map gives O(1) key → node lookup; the doubly linked list keeps nodes in recency order with the most-recently-used near the head and the least-recently-used at the tail. get and put both touch the map (find the node) and the list (move it to the front); when capacity is exceeded, evict the tail. Every operation is O(1). The shortcut answer is Java's LinkedHashMap or Python's OrderedDict, which do this internally.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can compose two data structures so every operation is O(1) — recognising that a hash map alone can't track recency and a list alone can't find in O(1).

Where candidates slip

Using a singly linked list (can't unlink in O(1)), forgetting to move a node to the front on get, or evicting the wrong end.

How to stand out

State the LinkedHashMap/OrderedDict shortcut, then build it from scratch with dummy head/tail sentinels, and cleanly factor out helper methods (addToFront, remove, moveToFront).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Built-in Ordered Map (LinkedHashMap / OrderedDict)	`O(1)`	`O(capacity)`	Mention it first to show you know the language and the production shortcut — then say 'but let me build it from scratch to show the mechanics'.	Read
2	HashMap + Doubly Linked List (Optimal, From Scratch)Optimal	`O(1)`	`O(capacity)`	The real answer. Build it with dummy head/tail sentinels and small helper methods so the O(1) splicing is obvious.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewO(1) get/put cache with LRU evictionAllowed to use a library structure?Yes (production)No (interview)Explore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Built-in Ordered Map (LinkedHashMap / OrderedDict)

TimeO(1)SpaceO(capacity)

Mention it first to show you know the language and the production shortcut — then say 'but let me build it from scratch to show the mechanics'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Some standard libraries already maintain a hash map whose keys remember their access or insertion order. What would that give you for free?

2Hint 2Explore hint

Java's LinkedHashMap has an access-order mode and a removeEldestEntry hook; Python's OrderedDict has move_to_end and popitem(last=False).

3Hint 3Explore hint

On get: fetch and move the key to the most-recent end. On put: insert/refresh, then if size exceeds capacity pop the least-recent end.

A · Core idea

The shortest correct answer reuses a library structure that is a hash map backed by a linked list.

Java — LinkedHashMap in access-order mode. Constructing it with new LinkedHashMap<>(capacity, 0.75f, true) makes it reorder entries on every access (get/put) so the eldest entry is the least recently used. Overriding removeEldestEntry to return size() > capacity lets the map evict automatically on insert. get returns the value or -1.

Python — OrderedDict. move_to_end(key) marks a key most-recently-used; popitem(last=False) removes the least-recently-used (front). On get we move the key to the end and return its value; on put we overwrite, move to end, and pop the front if we're over capacity.

Why mention it at all. In real code this is the right answer — fewer lines, fewer bugs. But interviewers almost always follow with 'now implement it without that' because the point of the question is whether you understand the underlying map + doubly linked list. Naming the shortcut shows language fluency; the from-scratch build shows data-structure fluency.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

capacity=2; put(1,1); put(2,2); get(1); put(3,3)

put(1,1)

insert 1

State{1:1}

Final resultkey 2 evicted; cache = {1:1, 3:3}

C · Code with teaching comments

Reference implementation previewimport java.util.LinkedHashMap; import java.util.Map; public class LRUCache { private final int capacity;Explore the full code

solution.javaJava

Built-in Ordered Map (LinkedHashMap / OrderedDict) — reference

3 teaching notes

1
import java.util.LinkedHashMap;
2
import java.util.Map;
3
 
4
public class LRUCache {
5
    private final int capacity;
6
    private final LinkedHashMap<Integer, Integer> map;
7
 
8
    public LRUCache(int capacity) {
9
        this.capacity = capacity;
10
        // The third arg true enables access-order: get/put move entries to the
11
        // most-recent end.
12
        this.map = new LinkedHashMap<>(capacity, 0.75f, true) {
13
            @Override
14
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
15
                // removeEldestEntry hook: auto-evict the eldest (LRU) entry once we
16
                // exceed capacity.
17
                return size() > LRUCache.this.capacity;
18
            }
19
        };
20
    }
21
 
22
    public int get(int key) {
23
        // Access-order means this get also refreshes recency; returns -1 on a miss.
24
        return map.getOrDefault(key, -1);
25
    }
26
 
27
    public void put(int key, int value) {
28
        map.put(key, value);
29
    }
30
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.30 lines

D · Why it works and complexityO(1) timeO(capacity) spaceOpen the invariant and proofExplore the proof

Recognising that LinkedHashMap / OrderedDict already encapsulate exactly the map + doubly-linked-list pairing is a sign you understand the structure — it's the same machine, just pre-assembled. Lead with it, but be ready to open the hood.

ComplexityO(1) time, O(capacity) space — These structures are themselves a hash map plus a linked list, so each operation is O(1) average. They hold at most capacity entries → O(capacity) space.

E · Edge cases and pitfalls3Forgetting the access-order flag (true) on LinkedHashMap — then it tracks insertion order, not recency.Explore edge cases

Pitfalls

Forgetting the access-order flag (true) on LinkedHashMap — then it tracks insertion order, not recency.
In Python, not calling move_to_end on get, so recency isn't refreshed on reads.
Relying on this in an interview that explicitly asks you to implement it manually.

03.2

Approach 2 of 2 · Optimal

HashMap + Doubly Linked List (Optimal, From Scratch)

TimeO(1)SpaceO(capacity)

The real answer. Build it with dummy head/tail sentinels and small helper methods so the O(1) splicing is obvious.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A hash map gives O(1) lookup but no notion of order. A list gives order but O(n) lookup. What if the map's values were the list's nodes, so you get both?

2Hint 2Explore hint

Use a doubly linked list so any node can be unlinked in O(1) (you need its prev). Keep most-recently-used at the front, least-recently-used at the back.

3Hint 3Explore hint

Add dummy head and tail nodes so insertion and removal never special-case the ends. On get/put, remove the node then re-add it at the front; on overflow, remove the node before the tail and delete its map entry.

A · Core idea

We pair two structures so each covers the other's weakness: the map finds any key's node in O(1), and the doubly linked list reorders and evicts in O(1).

The data model. Each list node stores key, value, prev, next. The hash map maps key → node. We keep two sentinels: a dummy head and dummy tail. The node right after head is the most recently used; the node right before tail is the least recently used. Sentinels mean every real node always has non-null neighbours, so insert/remove need no null checks.

get(key). If the key isn't in the map, return -1. Otherwise grab the node, unlink it from its current position, re-insert it just after head (now it's most-recently-used), and return its value. Both the unlink and the re-insert are constant-time pointer updates.

put(key, value). If the key exists, update the node's value and move it to the front. If it's new, create a node, put it in the map, and insert it at the front. Then, if the map's size exceeds capacity, evict: take the node just before tail (the LRU), unlink it, and delete its entry from the map — forgetting the map deletion is the classic leak that makes the structure grow unbounded.

Why doubly linked, why sentinels. A singly linked list can't remove an arbitrary node in O(1) because you can't reach its predecessor — you'd scan, making it O(n). The prev pointer fixes that. Dummy head/tail remove the 'is this the first/last node?' branches, so addToFront and remove are three or four unconditional pointer writes each.

Helper methods pay off. Factoring remove(node) and addToFront(node) keeps get and put short and makes 'move to front' literally remove(node); addToFront(node). Clean helpers are also what an interviewer reads to confirm your pointer surgery is correct.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

capacity=2; put(1,1); put(2,2); get(1); put(3,3); get(2)

Array state

before

1 is MRU after a get(1)

[0]

MRU ↓

[1]

LRU ↓

[2]

[3]

Current pointerResolved stateNot processed

Final resultget(1)=1, get(2)=-1; key 2 evicted

C · Code with teaching comments

solution.javaJava

HashMap + Doubly Linked List (Optimal, From Scratch) — optimal

6 teaching notes

1
import java.util.HashMap;
2
import java.util.Map;
3
 
4
public class LRUCache {
5
    private static class Node {
6
        int key, value;
7
        Node prev, next;
8
        Node(int key, int value) { this.key = key; this.value = value; }
9
    }
10
 
11
    private final int capacity;
12
    // Maps key → the list NODE (not the value) so we can splice it out in O(1).
13
    private final Map<Integer, Node> map = new HashMap<>();
14
    private final Node head = new Node(0, 0); // dummy head (MRU side)
15
    private final Node tail = new Node(0, 0); // dummy tail (LRU side)
16
 
17
    public LRUCache(int capacity) {
18
        this.capacity = capacity;
19
        head.next = tail;
20
        tail.prev = head;
21
    }
22
 
23
    private void remove(Node node) {
24
        node.prev.next = node.next;
25
        node.next.prev = node.prev;
26
    }
27
 
28
    private void addToFront(Node node) {
29
        node.next = head.next;
30
        node.prev = head;
31
        head.next.prev = node;
32
        head.next = node;
33
    }
34
 
35
    public int get(int key) {
36
        Node node = map.get(key);
37
        if (node == null) return -1;
38
        remove(node);
39
        addToFront(node);
40
        return node.value;
41
    }
42
 
43
    public void put(int key, int value) {
44
        Node node = map.get(key);
45
        if (node != null) {
46
            node.value = value;
47
            remove(node);
48
            addToFront(node);
49
            return;
50
        }
51
        Node fresh = new Node(key, value);
52
        map.put(key, fresh);
53
        addToFront(fresh);
54
        if (map.size() > capacity) {
55
            Node lru = tail.prev;
56
            remove(lru);
57
            map.remove(lru.key);
58
        }
59
    }
60
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.60 lines

D · Why it works and complexityO(1) timeO(capacity) spaceOpen the invariant and proofExplore the proof

This is the canonical 'compose two structures around one invariant' design. The map's value being the list node (not the raw value) is the linchpin — it's what lets you jump from a key straight to its position in the recency order and splice it in O(1). Internalise this and LFU Cache and All O(1) Data Structure are variations on the theme.

ComplexityO(1) time, O(capacity) space — Map lookup is O(1); splicing a node out and re-inserting at the front is O(1) thanks to the doubly linked list and sentinels. The map and list each hold at most capacity nodes → O(capacity) space.

E · Edge cases and pitfalls7capacity = 1; put(1,1); put(2,2) — put(2,2) adds node2 then size 2 > 1 → evicts node1; get(1) returns -1.Explore edge cases

Edge cases handled

capacity = 1; put(1,1); put(2,2)put(2,2) adds node2 then size 2 > 1 → evicts node1; get(1) returns -1.
put on existing keyValue updated and node moved to front; map size unchanged, so no eviction.
get on missing keymap.get returns null → return -1; list untouched.

Pitfalls

Using a singly linked list — removing an arbitrary node becomes O(n) without a prev pointer.
Evicting but forgetting map.remove(lru.key) — the map grows unbounded (memory leak).
Not moving the node to the front on get, so recency stops reflecting reads.
Skipping dummy sentinels and crashing on inserts/removes at the list ends.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.HashMap; import java.util.Map; public class LRUCache { private static class Node {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    private static class Node {
        int key, value;
        Node prev, next;
        Node(int key, int value) { this.key = key; this.value = value; }
    }

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

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

private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

private void addToFront(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        remove(node);
        addToFront(node);
        return node.value;
    }

public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            remove(node);
            addToFront(node);
            return;
        }
        Node fresh = new Node(key, value);
        map.put(key, fresh);
        addToFront(fresh);
        if (map.size() > capacity) {
            Node lru = tail.prev;
            remove(lru);
            map.remove(lru.key);
        }
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Evicting from the list but not the map

If you unlink the LRU node but leave its key in the map, the map keeps growing and stale keys still 'hit', breaking correctness and leaking memory.

Explore the code comparison

Don't write this

if len(self.map) > self.capacity:
    lru = self.tail.prev
    self._remove(lru)
    # forgot: del self.map[lru.key]

Write this instead

if len(self.map) > self.capacity:
    lru = self.tail.prev
    self._remove(lru)
    del self.map[lru.key]

Not refreshing recency on get

A get is a use. If you return the value without moving the node to the front, the LRU order becomes wrong and you evict still-hot keys.

Explore the code comparison

Don't write this

public int get(int key) {
    Node node = map.get(key);
    if (node == null) return -1;
    return node.value;   // recency not updated!
}

Write this instead

public int get(int key) {
    Node node = map.get(key);
    if (node == null) return -1;
    remove(node);
    addToFront(node);
    return node.value;
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Hash map (key → node) + doubly linked list ordered by recency

Code pattern to memorize

get(key):  if miss return -1; move node to front; return val
put(key,val): if exists update + move to front; else add node at front;
             if size > capacity: remove tail node and its map entry

Rules to remember

1Use a doubly linked list — you must unlink a node in O(1), which needs its prev pointer.
2Keep dummy head and tail sentinels so insert/remove never hit a null neighbour edge case.
3Most-recently-used lives next to head; least-recently-used sits just before tail — evict from the tail.
4Both get and put (even on an update) count as a use → move the node to the front.
5The map stores key → node reference, not key → value, so you can splice the node out of the list in O(1).

Use this pattern when

Design a fixed-capacity cache with O(1) get/put and least-recently-used eviction
Any 'O(1) access + ordered by recency/insertion' requirement
Implementing an LFU/LRU layer, a bounded memo table, or a page-replacement policy
When you need both fast lookup AND fast reordering of the same elements

Choose another pattern when

Eviction is by frequency, not recency → LFU Cache (counts + buckets), a different structure
No capacity bound / no eviction → a plain hash map suffices
You only append and never reorder → a singly linked list or queue is enough

Interview takeaway

The hash-map-plus-doubly-linked-list combo is the archetypal 'two data structures, one invariant' design: the map buys O(1) find, the list buys O(1) reorder/evict. Master the dummy-sentinel splicing and LFU Cache and All O(1) Data Structure follow the same blueprint.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternThe hash-map-plus-doubly-linked-list design: a map for O(1) lookup married to a doubly linked list for O(1) reorder/evict, kept consistent by storing nodes as the map's values. The blueprint behind LFU Cache and All O(1) Data Structure.

Practice queueDirect variations and pattern siblings

Direct follow-ups

LFU Cache
Coming soon
Evict by least frequency instead of recency — keep a frequency map of doubly linked lists, one per count.
All O`one Data Structure
Coming soon
Same map + doubly linked list of buckets to keep min/max key counts in O(1).
First Unique Number
Coming soon
Hash map for counts plus an ordered structure to pop the first unique in O(1).

Same pattern

←

Copy List with Random Pointer

Continue · Next problem

Add Two Numbers

mediumLinked ListsLC #146Asked very often

LRU Cache

LCPractice

Linked List · 7 of 24 · 12 min

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

LRUCache(int capacity) initializes the cache with positive size capacity.
int get(int key) returns the value of the key if it exists, otherwise returns -1.
void put(int key, int value) updates the value if the key exists; otherwise adds the key-value pair. If inserting causes the number of keys to exceed capacity, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

In plain English

Examples

Example 1

Input: LRUCache(2); put(1,1); put(2,2); get(1); put(3,3); get(2); put(4,4); get(1); get(3); get(4)
Output: get(1)=1, get(2)=-1, get(1)=-1, get(3)=3, get(4)=4
Note: put(3,3) evicts key 2 (LRU); put(4,4) evicts key 1; so get(2) and the later get(1) miss.

Example 2

Input: LRUCache(1); put(1,1); put(2,2); get(1); get(2)
Output: get(1)=-1, get(2)=2
Note: Capacity 1: put(2,2) evicts key 1 immediately, so get(1) misses.

Example 3

Input: LRUCache(2); put(1,1); put(1,10); get(1)
Output: get(1)=10
Note: Updating an existing key overwrites its value and refreshes recency without adding a new entry.

Constraints

1 ≤ capacity ≤ 3000
0 ≤ key ≤ 10⁴
0 ≤ value ≤ 10⁵
At most 2 × 10⁵ calls to get and put
Both get and put must be O(1) average time

Clarifying questions4First question: Does a get count as a use (i.e. refresh recency)?Explore questions

Q1.Does a get count as a use (i.e. refresh recency)?
Yes — every successful get moves that key to most-recently-used. So does an update via put.
Q2.What does get return on a missing key?
-1, per the spec. I'll assume real values are non-negative so -1 is an unambiguous miss sentinel.
Q3.When does eviction happen, and which key goes?
Only on an insert that pushes the size above capacity, and we evict the least recently used key — the one at the tail of the recency list.
Q4.Can I use a built-in like LinkedHashMap or OrderedDict?
I'll mention it as the production shortcut, but build the map + doubly linked list from scratch since that's what the interviewer is usually testing.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can compose two data structures so every operation is O(1) — recognising that a hash map alone can't track recency and a list alone can't find in O(1).

Where candidates slip

Using a singly linked list (can't unlink in O(1)), forgetting to move a node to the front on get, or evicting the wrong end.

How to stand out

State the LinkedHashMap/OrderedDict shortcut, then build it from scratch with dummy head/tail sentinels, and cleanly factor out helper methods (addToFront, remove, moveToFront).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Built-in Ordered Map (LinkedHashMap / OrderedDict)	`O(1)`	`O(capacity)`	Mention it first to show you know the language and the production shortcut — then say 'but let me build it from scratch to show the mechanics'.	Read
2	HashMap + Doubly Linked List (Optimal, From Scratch)Optimal	`O(1)`	`O(capacity)`	The real answer. Build it with dummy head/tail sentinels and small helper methods so the O(1) splicing is obvious.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Built-in Ordered Map (LinkedHashMap / OrderedDict)

TimeO(1)SpaceO(capacity)

Mention it first to show you know the language and the production shortcut — then say 'but let me build it from scratch to show the mechanics'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Some standard libraries already maintain a hash map whose keys remember their access or insertion order. What would that give you for free?

2Hint 2Explore hint

Java's LinkedHashMap has an access-order mode and a removeEldestEntry hook; Python's OrderedDict has move_to_end and popitem(last=False).

3Hint 3Explore hint

On get: fetch and move the key to the most-recent end. On put: insert/refresh, then if size exceeds capacity pop the least-recent end.

A · Core idea

The shortest correct answer reuses a library structure that is a hash map backed by a linked list.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

capacity=2; put(1,1); put(2,2); get(1); put(3,3)

put(1,1)

insert 1

State{1:1}

Final resultkey 2 evicted; cache = {1:1, 3:3}

C · Code with teaching comments

Reference implementation previewimport java.util.LinkedHashMap; import java.util.Map; public class LRUCache { private final int capacity;Explore the full code

solution.javaJava

Built-in Ordered Map (LinkedHashMap / OrderedDict) — reference

3 teaching notes

1
import java.util.LinkedHashMap;
2
import java.util.Map;
3
 
4
public class LRUCache {
5
    private final int capacity;
6
    private final LinkedHashMap<Integer, Integer> map;
7
 
8
    public LRUCache(int capacity) {
9
        this.capacity = capacity;
10
        // The third arg true enables access-order: get/put move entries to the
11
        // most-recent end.
12
        this.map = new LinkedHashMap<>(capacity, 0.75f, true) {
13
            @Override
14
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
15
                // removeEldestEntry hook: auto-evict the eldest (LRU) entry once we
16
                // exceed capacity.
17
                return size() > LRUCache.this.capacity;
18
            }
19
        };
20
    }
21
 
22
    public int get(int key) {
23
        // Access-order means this get also refreshes recency; returns -1 on a miss.
24
        return map.getOrDefault(key, -1);
25
    }
26
 
27
    public void put(int key, int value) {
28
        map.put(key, value);
29
    }
30
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.30 lines

D · Why it works and complexityO(1) timeO(capacity) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Forgetting the access-order flag (true) on LinkedHashMap — then it tracks insertion order, not recency.Explore edge cases

Pitfalls

Forgetting the access-order flag (true) on LinkedHashMap — then it tracks insertion order, not recency.
In Python, not calling move_to_end on get, so recency isn't refreshed on reads.
Relying on this in an interview that explicitly asks you to implement it manually.

03.2

Approach 2 of 2 · Optimal

HashMap + Doubly Linked List (Optimal, From Scratch)

TimeO(1)SpaceO(capacity)

The real answer. Build it with dummy head/tail sentinels and small helper methods so the O(1) splicing is obvious.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A hash map gives O(1) lookup but no notion of order. A list gives order but O(n) lookup. What if the map's values were the list's nodes, so you get both?

2Hint 2Explore hint

Use a doubly linked list so any node can be unlinked in O(1) (you need its prev). Keep most-recently-used at the front, least-recently-used at the back.

3Hint 3Explore hint

A · Core idea

We pair two structures so each covers the other's weakness: the map finds any key's node in O(1), and the doubly linked list reorders and evicts in O(1).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

capacity=2; put(1,1); put(2,2); get(1); put(3,3); get(2)

Array state

before

1 is MRU after a get(1)

[0]

MRU ↓

[1]

LRU ↓

[2]

[3]

Current pointerResolved stateNot processed

Final resultget(1)=1, get(2)=-1; key 2 evicted

C · Code with teaching comments

solution.javaJava

HashMap + Doubly Linked List (Optimal, From Scratch) — optimal

6 teaching notes

1
import java.util.HashMap;
2
import java.util.Map;
3
 
4
public class LRUCache {
5
    private static class Node {
6
        int key, value;
7
        Node prev, next;
8
        Node(int key, int value) { this.key = key; this.value = value; }
9
    }
10
 
11
    private final int capacity;
12
    // Maps key → the list NODE (not the value) so we can splice it out in O(1).
13
    private final Map<Integer, Node> map = new HashMap<>();
14
    private final Node head = new Node(0, 0); // dummy head (MRU side)
15
    private final Node tail = new Node(0, 0); // dummy tail (LRU side)
16
 
17
    public LRUCache(int capacity) {
18
        this.capacity = capacity;
19
        head.next = tail;
20
        tail.prev = head;
21
    }
22
 
23
    private void remove(Node node) {
24
        node.prev.next = node.next;
25
        node.next.prev = node.prev;
26
    }
27
 
28
    private void addToFront(Node node) {
29
        node.next = head.next;
30
        node.prev = head;
31
        head.next.prev = node;
32
        head.next = node;
33
    }
34
 
35
    public int get(int key) {
36
        Node node = map.get(key);
37
        if (node == null) return -1;
38
        remove(node);
39
        addToFront(node);
40
        return node.value;
41
    }
42
 
43
    public void put(int key, int value) {
44
        Node node = map.get(key);
45
        if (node != null) {
46
            node.value = value;
47
            remove(node);
48
            addToFront(node);
49
            return;
50
        }
51
        Node fresh = new Node(key, value);
52
        map.put(key, fresh);
53
        addToFront(fresh);
54
        if (map.size() > capacity) {
55
            Node lru = tail.prev;
56
            remove(lru);
57
            map.remove(lru.key);
58
        }
59
    }
60
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.60 lines

D · Why it works and complexityO(1) timeO(capacity) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7capacity = 1; put(1,1); put(2,2) — put(2,2) adds node2 then size 2 > 1 → evicts node1; get(1) returns -1.Explore edge cases

Edge cases handled

capacity = 1; put(1,1); put(2,2)put(2,2) adds node2 then size 2 > 1 → evicts node1; get(1) returns -1.
put on existing keyValue updated and node moved to front; map size unchanged, so no eviction.
get on missing keymap.get returns null → return -1; list untouched.

Pitfalls

Using a singly linked list — removing an arbitrary node becomes O(n) without a prev pointer.
Evicting but forgetting map.remove(lru.key) — the map grows unbounded (memory leak).
Not moving the node to the front on get, so recency stops reflecting reads.
Skipping dummy sentinels and crashing on inserts/removes at the list ends.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.HashMap; import java.util.Map; public class LRUCache { private static class Node {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    private static class Node {
        int key, value;
        Node prev, next;
        Node(int key, int value) { this.key = key; this.value = value; }
    }

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

private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

private void addToFront(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        remove(node);
        addToFront(node);
        return node.value;
    }

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Evicting from the list but not the map

If you unlink the LRU node but leave its key in the map, the map keeps growing and stale keys still 'hit', breaking correctness and leaking memory.

Explore the code comparison

Don't write this

if len(self.map) > self.capacity:
    lru = self.tail.prev
    self._remove(lru)
    # forgot: del self.map[lru.key]

Write this instead

if len(self.map) > self.capacity:
    lru = self.tail.prev
    self._remove(lru)
    del self.map[lru.key]

Not refreshing recency on get

A get is a use. If you return the value without moving the node to the front, the LRU order becomes wrong and you evict still-hot keys.

Explore the code comparison

Don't write this

public int get(int key) {
    Node node = map.get(key);
    if (node == null) return -1;
    return node.value;   // recency not updated!
}

Write this instead

public int get(int key) {
    Node node = map.get(key);
    if (node == null) return -1;
    remove(node);
    addToFront(node);
    return node.value;
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Hash map (key → node) + doubly linked list ordered by recency

Code pattern to memorize

get(key):  if miss return -1; move node to front; return val
put(key,val): if exists update + move to front; else add node at front;
             if size > capacity: remove tail node and its map entry

Rules to remember

1Use a doubly linked list — you must unlink a node in O(1), which needs its prev pointer.
2Keep dummy head and tail sentinels so insert/remove never hit a null neighbour edge case.
3Most-recently-used lives next to head; least-recently-used sits just before tail — evict from the tail.
4Both get and put (even on an update) count as a use → move the node to the front.
5The map stores key → node reference, not key → value, so you can splice the node out of the list in O(1).

Use this pattern when

Design a fixed-capacity cache with O(1) get/put and least-recently-used eviction
Any 'O(1) access + ordered by recency/insertion' requirement
Implementing an LFU/LRU layer, a bounded memo table, or a page-replacement policy
When you need both fast lookup AND fast reordering of the same elements

Choose another pattern when

Eviction is by frequency, not recency → LFU Cache (counts + buckets), a different structure
No capacity bound / no eviction → a plain hash map suffices
You only append and never reorder → a singly linked list or queue is enough

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

LFU Cache
Coming soon
Evict by least frequency instead of recency — keep a frequency map of doubly linked lists, one per count.
All O`one Data Structure
Coming soon
Same map + doubly linked list of buckets to keep min/max key counts in O(1).
First Unique Number
Coming soon
Hash map for counts plus an ordered structure to pop the first unique in O(1).

Same pattern

←

Copy List with Random Pointer

Continue · Next problem

Add Two Numbers