What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Advanced Data Structures

Builds on Dummy Node and Hash Map, which you haven’t finished yet.

P2MediumMental model~12 min speedrun

LRU Cache (HashMap + Doubly Linked List)

The problem

LRU Cache (LC 146)(opens leetcode.com)

A cache with a fixed capacity needs to hold key-value pairs and, whenever it's full and a new key arrives, evict whichever key was touched longest ago.

Build an LRUCache class:

LRUCache(int capacity) sets up the cache with a positive capacity.
int get(int key) returns the value stored for key, or -1 if key isn't present.
void put(int key, int value) inserts key with value, or overwrites the value if key is already present. If this push takes the cache past capacity, evict the least recently used key first.

Both get and put must run in O(1) average time.

Example 1

Input:["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

Output:[null, null, null, 1, null, -1, null, -1, 3, 4]

put(1, 1), put(2, 2), get(1) -> 1, put(3, 3) evicts key 2, get(2) -> -1 (not found), put(4, 4) evicts key 1, get(1) -> -1, get(3) -> 3, get(4) -> 4.

LRU Cache

key-value storage ➔ hash map (O(1) lookup) + DLL (O(1) recency)

Spot it when: A design problem asks for O(1) lookups plus eviction by least recent use (or by frequency).

LRU Cache

Python

1	from typing import Optional
2
3	class DLinkedNode:
4	def __init__(self, key: int = 0, val: int = 0) -> None:
5	self.key = key # Stored so eviction can delete the map entry
6	self.val = val
7	self.prev: Optional["DLinkedNode"] = None
8	self.next: Optional["DLinkedNode"] = None
9
10	class LRUCache:
11	"""LRU Cache: hash map for O(1) lookup + doubly-linked list for O(1) recency order.
12	Time: O(1) get and put \| Space: O(capacity)
13	"""
14	def __init__(self, capacity: int) -> None:
15	self.cap = capacity
16	self.cache: dict[int, DLinkedNode] = {}
17	self.head = DLinkedNode() # Sentinel: most recent side
18	self.tail = DLinkedNode() # Sentinel: least recent side
19	self.head.next = self.tail
20	self.tail.prev = self.head
21
22	def _remove(self, node: DLinkedNode) -> None:
23	node.prev.next = node.next # Unlink: sentinels mean no null checks
24	node.next.prev = node.prev
25
26	def _add_to_head(self, node: DLinkedNode) -> None:
27	node.prev = self.head
28	node.next = self.head.next
29	self.head.next.prev = node
30	self.head.next = node
31
32	def get(self, key: int) -> int:
33	# 1. Return A Miss, Or Promote The Found Node To Most Recently Used:
34	# A successful read counts as a use just like a write, so the node must move to the front
35	# before its value is returned; otherwise the node next to tail could stop being the least-recently-used one.
36	if key not in self.cache:
37	return -1
38	node = self.cache[key]
39	self._remove(node) # A read counts as a use:
40	self._add_to_head(node) # move to the most recent position
41	return node.val
42
43	def put(self, key: int, value: int) -> None:
44	# 1. Update In Place And Promote, Or Insert A New Node (Evicting If Full):
45	# An existing key keeps its map entry and only moves to the front; a brand-new key may first
46	# evict the node next to tail, which is always the least recently used because every use moves its node to the front.
47	if key in self.cache:
48	node = self.cache[key]
49	node.val = value # Update in place, then mark as most recent
50	self._remove(node)
51	self._add_to_head(node)
52	else:
53	if len(self.cache) >= self.cap:
54	lru = self.tail.prev # Least recently used sits next to the tail
55	self._remove(lru)
56	del self.cache[lru.key]
57	new_node = DLinkedNode(key, value)
58	self.cache[key] = new_node
59	self._add_to_head(new_node)

Invariant: The list from head to tail holds exactly the nodes in self.cache, ordered from most to least recently used.

The hash map finds any node instantly, and the doubly linked list keeps nodes in order of use: most recent next to head, least recent next to tail. This is correct because every get and every put moves its node to the front, so no node can sit behind one that was used less recently, and the node just before tail is always the least recently used; each node stores its key so evicting it can also del self.cache[lru.key]. The trap is put on a key that is already there: update node.val and move the node to the front, or it keeps its old place and is evicted too early; with capacity 2, put(1, 1), put(2, 2), put(1, 9), put(3, 3) must evict 2, not 1.

See it run

LRU Cache, capacity 2, ops = put(1, 1), put(2, 2), put(1, 9), put(3, 3), get(2), get(1)

call none yet

The row is the list from head to tail. Each box shows key:val. The box next to head is the most recently used key.

used the node that this call reads, writes or moves to the front
lru the least recently used node, next to tail

The cache is empty, so head is linked straight to tail.

self.cache keys

empty

1 / 12

Gotchas1 of 4

The trap
Gotcha 1: Updating node.val without moving the node to the front
Mistake
```
node.val = value
```
Fix
```
node.val = value
self._remove(node)
self._add_to_head(node)
```
What happens: put on a cached key is a use, like get. Without the move, the node keeps its old place near tail. With capacity 2, put(1, 1), put(2, 2), put(1, 9) and put(3, 3) then evict key 1. Key 2 was used less recently, so key 2 must be evicted.
Example: capacity = 2: put(1, 1), put(2, 2), put(1, 9), put(3, 3), then get(1) and get(2)
Mistake: returns (-1, 2)Fix: returns (9, -1)
Gotcha 2: Evicting the node without del self.cache[lru.key]
Mistake
```
self._remove(lru)
```
Fix
```
self._remove(lru)
del self.cache[lru.key]
```
What happens: Eviction must remove the key from the map as well as the node from the list. Each node stores its key for exactly this line. Without it, the map keeps the evicted key. A later get finds it and returns a value that was evicted.
Example: capacity = 1: put(1, 1), put(2, 2), then get(1)
Mistake: returns 1Fix: returns -1
Gotcha 3: Calling _add_to_head before _remove in get
Mistake
```
self._add_to_head(node)
self._remove(node)
return node.val
```
Fix
```
self._remove(node)
self._add_to_head(node)
return node.val
```
What happens: _add_to_head(node) links the node after head, but its old neighbours still point to it. _remove(node) then uses the new node.prev and node.next, so it unlinks the node only from the front. The list is now broken. In this example, put(3, 5) evicts key 2, which get(2) has just read, and keeps key 1.
Example: capacity = 2: put(2, 2), put(1, 9), get(2), put(3, 5), then get(1)
Mistake: returns 9Fix: returns -1
Gotcha 4: Evicting when put updates a key that is already cached
Mistake
```
def put(self, key: int, value: int) -> None:
    if len(self.cache) >= self.cap:  # runs for every put
        lru = self.tail.prev
```
Fix
```
else:
    if len(self.cache) >= self.cap:
        lru = self.tail.prev
```
What happens: Updating a cached key adds no entry, so the cache does not grow. Eviction belongs only in the branch for a new key. With capacity 2, put(1, 1), put(2, 2) and put(2, 5) must keep both keys. Evicting on the update removes key 1.
Example: capacity = 2: put(1, 1), put(2, 2), put(2, 5), then get(1)
Mistake: returns -1Fix: returns 1

Not this one if…

Only the last size values are kept and they leave in arrival order, as in Moving Average from Data Stream (LC 346): a queue drops the oldest value, nothing is looked up by key, and reading a value never makes it stay longer. See Fixed Window

Deep Dive

Why the list stays in order of use

The cache needs two things at once: find a key in O(1), and know which key was used longest ago. The hash map self.cache does the first. The doubly linked list does the second. It keeps the nodes in order from the most recent (next to head) to the least recent (next to tail).

Only two moves change the list. _add_to_head puts a node next to head, and _remove unlinks a node. Every get that finds a key and every put ends with the node next to head. So a node can never sit behind a node that was used less recently.

Trace a cache with cap = 2. After put(1, 1) and put(2, 2), the list is 2:2, 1:1. put(1, 9) updates the value and moves key 1 to the front, so the list is 1:9, 2:2. put(3, 3) finds the cache full, takes lru = tail.prev, which is key 2, and evicts it. The list is 3:3, 1:9.

Then get(2) returns -1, because key 2 is gone. get(1) returns 9 and moves key 1 to the front, so the list is 1:9, 3:3.

This is why the card's invariant says that the list holds exactly the nodes in self.cache, in order of use. Each method changes the map and the list together.

Why a doubly linked list, and why sentinels

To move a node, _remove needs the node before it and the node after it. A singly linked list has no link to the node before, so finding it takes O(N) steps. A doubly linked list stores prev and next in each node. The map gives the node directly, and _remove unlinks it in O(1).

head and tail are sentinel nodes. A sentinel is a fixed node that holds no data. Because they always exist, every real node has a prev and a next. _remove and _add_to_head therefore need no checks for an empty list, for the first node or for the last node.

The least recently used node is always self.tail.prev. That is the node put evicts when the cache is full.

Why each node stores its key

Eviction removes the node from the list and the entry from the map. The list gives lru = self.tail.prev. The map entry is self.cache[lru.key], so the node must know its own key.

Without key in the node, del self.cache[lru.key] is impossible. The map keeps an entry that points at a node no longer in the list. A later get of that key would call _remove on a node that is not linked, and the list breaks.

The order of the steps in the else branch of put matters. Evict first, only if len(self.cache) >= self.cap. Then create the new node. If the new node were added first, tail.prev could be the new node itself. With cap = 1, put would evict the key it just added.

Updating a key that already exists

put on an existing key is a use, the same as get. The branch for key in self.cache must do three things: set node.val, call _remove(node) and call _add_to_head(node). It must not create a second node, and it must not evict.

The card's trap is to set node.val and stop. With cap = 2, the calls put(1, 1), put(2, 2), put(1, 9), put(3, 3) then evict key 1, because key 1 stayed at the back. The correct code evicts key 2, which was used least recently. The correct cache keeps keys 1 and 3.

Each call does a fixed number of dictionary and pointer operations. So get and put are O(1), and the space is O(cap).

60-Second Pitch

"I need O(1) lookup and O(1) eviction of the key used longest ago. So I combine a hash map and a doubly linked list. The map gives the node for a key. The list keeps the nodes in order of use, with head and tail as sentinels, so unlinking a node needs no special cases. Every get and every put moves its node next to head. So the node before tail is always the least recently used, and put evicts it when the cache is full. Each node stores its key, so I can delete the map entry too. Every operation is O(1), and the space is O(capacity)."

Common Questions

What is the time and space complexity?: get and put are both O(1) time. The map lookup is O(1) on average, and _remove and _add_to_head change a fixed number of links. The space is O(capacity), for at most cap nodes and cap map entries.
Why not use an array or a plain list for the order?: Moving an item to the front of a Python list takes O(N), because the other items shift. A doubly linked list moves a node by changing four links. The map gives the node in O(1), so no search is needed.
Can you use OrderedDict instead?: Yes, in Python. OrderedDict.move_to_end moves a key in O(1), and popitem(last=False) removes the oldest key in O(1). Many interviewers accept it, but some ask for the list version. The list version shows that you know why the moves are O(1).
What changes for a least frequently used cache?: Order of use is no longer enough, because the key with the lowest use count must go. LFU Cache (LC 460) keeps a count for each key and one list of keys for each count. Ties inside one count are broken by recency, which is the LRU rule again.
How would this change with several threads?: A get also writes to the list, so two threads can corrupt the links. The simplest fix is one lock around each method. For heavy traffic, split the cache into several parts, each with its own lock and its own list, and choose the part by the hash of the key.

SWE Reasoning

Spot it

A design problem asks for get and put in O(1).
When the cache is full, the entry used longest ago must be removed.
Both reading and writing count as a use.
One structure alone fails: a hash map has no order, and a list has no O(1) lookup.
The statement says "least recently used", or a variant with counts (LFU Cache (LC 460)).

The invariant, step by step

LRUCache(cap) creates an empty self.cache, and links head to tail. The list holds no nodes.
put of a new key checks len(self.cache) >= self.cap. If the cache is full, it takes lru = self.tail.prev, calls _remove(lru) and runs del self.cache[lru.key].
It then creates a node, stores it in self.cache[key] and calls _add_to_head. The list and the map each gained one node.
get of a key in self.cache calls _remove(node) and then _add_to_head(node). The node moves from its place to the front, and the map is unchanged.
put of an existing key sets node.val and moves the node the same way.
Every use leaves the used node next to head, so the node next to tail is the one used longest ago. The list and the map hold the same keys after every call.

Traps

Updating node.val without moving the node. The node keeps its old place and is evicted too early.
Evicting from the list but not the map. If del self.cache[lru.key] is missing, a later get finds a node that is no longer in the list.
A node without key. The eviction code cannot find the map entry to delete.
Moving only on put. get is a use too. Without the move in get, a key that is read often can still be evicted.
Checking > instead of >=. With len(self.cache) > self.cap, the cache grows to cap + 1 before it evicts.
Forgetting that get of a missing key returns -1. The function must return before it touches the list.

Practice

Canonical LeetCode:LRU Cache (LC 146)LFU Cache (LC 460)All O`one Data Structure (LC 432)First Unique Number (LC 1429)Design Authentication Manager (LC 1797)

Theory Context•Advanced Data Structures

Builds on Dummy Node and Hash Map, which you haven’t finished yet.

P2MediumMental model~12 min speedrun

LRU Cache (HashMap + Doubly Linked List)

The problem

LRU Cache (LC 146)(opens leetcode.com)

A cache with a fixed capacity needs to hold key-value pairs and, whenever it's full and a new key arrives, evict whichever key was touched longest ago.

Build an LRUCache class:

LRUCache(int capacity) sets up the cache with a positive capacity.
int get(int key) returns the value stored for key, or -1 if key isn't present.
void put(int key, int value) inserts key with value, or overwrites the value if key is already present. If this push takes the cache past capacity, evict the least recently used key first.

Both get and put must run in O(1) average time.

Example 1

Input:["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

Output:[null, null, null, 1, null, -1, null, -1, 3, 4]

put(1, 1), put(2, 2), get(1) -> 1, put(3, 3) evicts key 2, get(2) -> -1 (not found), put(4, 4) evicts key 1, get(1) -> -1, get(3) -> 3, get(4) -> 4.

LRU Cache

key-value storage ➔ hash map (O(1) lookup) + DLL (O(1) recency)

Spot it when: A design problem asks for O(1) lookups plus eviction by least recent use (or by frequency).

LRU Cache

Python

1	from typing import Optional
2
3	class DLinkedNode:
4	def __init__(self, key: int = 0, val: int = 0) -> None:
5	self.key = key # Stored so eviction can delete the map entry
6	self.val = val
7	self.prev: Optional["DLinkedNode"] = None
8	self.next: Optional["DLinkedNode"] = None
9
10	class LRUCache:
11	"""LRU Cache: hash map for O(1) lookup + doubly-linked list for O(1) recency order.
12	Time: O(1) get and put \| Space: O(capacity)
13	"""
14	def __init__(self, capacity: int) -> None:
15	self.cap = capacity
16	self.cache: dict[int, DLinkedNode] = {}
17	self.head = DLinkedNode() # Sentinel: most recent side
18	self.tail = DLinkedNode() # Sentinel: least recent side
19	self.head.next = self.tail
20	self.tail.prev = self.head
21
22	def _remove(self, node: DLinkedNode) -> None:
23	node.prev.next = node.next # Unlink: sentinels mean no null checks
24	node.next.prev = node.prev
25
26	def _add_to_head(self, node: DLinkedNode) -> None:
27	node.prev = self.head
28	node.next = self.head.next
29	self.head.next.prev = node
30	self.head.next = node
31
32	def get(self, key: int) -> int:
33	# 1. Return A Miss, Or Promote The Found Node To Most Recently Used:
34	# A successful read counts as a use just like a write, so the node must move to the front
35	# before its value is returned; otherwise the node next to tail could stop being the least-recently-used one.
36	if key not in self.cache:
37	return -1
38	node = self.cache[key]
39	self._remove(node) # A read counts as a use:
40	self._add_to_head(node) # move to the most recent position
41	return node.val
42
43	def put(self, key: int, value: int) -> None:
44	# 1. Update In Place And Promote, Or Insert A New Node (Evicting If Full):
45	# An existing key keeps its map entry and only moves to the front; a brand-new key may first
46	# evict the node next to tail, which is always the least recently used because every use moves its node to the front.
47	if key in self.cache:
48	node = self.cache[key]
49	node.val = value # Update in place, then mark as most recent
50	self._remove(node)
51	self._add_to_head(node)
52	else:
53	if len(self.cache) >= self.cap:
54	lru = self.tail.prev # Least recently used sits next to the tail
55	self._remove(lru)
56	del self.cache[lru.key]
57	new_node = DLinkedNode(key, value)
58	self.cache[key] = new_node
59	self._add_to_head(new_node)

Invariant: The list from head to tail holds exactly the nodes in self.cache, ordered from most to least recently used.

See it run

LRU Cache, capacity 2, ops = put(1, 1), put(2, 2), put(1, 9), put(3, 3), get(2), get(1)

call none yet

The row is the list from head to tail. Each box shows key:val. The box next to head is the most recently used key.

used the node that this call reads, writes or moves to the front
lru the least recently used node, next to tail

The cache is empty, so head is linked straight to tail.

self.cache keys

empty

1 / 12

Gotchas1 of 4

The trap
Gotcha 1: Updating node.val without moving the node to the front
Mistake
```
node.val = value
```
Fix
```
node.val = value
self._remove(node)
self._add_to_head(node)
```
What happens: put on a cached key is a use, like get. Without the move, the node keeps its old place near tail. With capacity 2, put(1, 1), put(2, 2), put(1, 9) and put(3, 3) then evict key 1. Key 2 was used less recently, so key 2 must be evicted.
Example: capacity = 2: put(1, 1), put(2, 2), put(1, 9), put(3, 3), then get(1) and get(2)
Mistake: returns (-1, 2)Fix: returns (9, -1)
Gotcha 2: Evicting the node without del self.cache[lru.key]
Mistake
```
self._remove(lru)
```
Fix
```
self._remove(lru)
del self.cache[lru.key]
```
What happens: Eviction must remove the key from the map as well as the node from the list. Each node stores its key for exactly this line. Without it, the map keeps the evicted key. A later get finds it and returns a value that was evicted.
Example: capacity = 1: put(1, 1), put(2, 2), then get(1)
Mistake: returns 1Fix: returns -1
Gotcha 3: Calling _add_to_head before _remove in get
Mistake
```
self._add_to_head(node)
self._remove(node)
return node.val
```
Fix
```
self._remove(node)
self._add_to_head(node)
return node.val
```
What happens: _add_to_head(node) links the node after head, but its old neighbours still point to it. _remove(node) then uses the new node.prev and node.next, so it unlinks the node only from the front. The list is now broken. In this example, put(3, 5) evicts key 2, which get(2) has just read, and keeps key 1.
Example: capacity = 2: put(2, 2), put(1, 9), get(2), put(3, 5), then get(1)
Mistake: returns 9Fix: returns -1
Gotcha 4: Evicting when put updates a key that is already cached
Mistake
```
def put(self, key: int, value: int) -> None:
    if len(self.cache) >= self.cap:  # runs for every put
        lru = self.tail.prev
```
Fix
```
else:
    if len(self.cache) >= self.cap:
        lru = self.tail.prev
```
What happens: Updating a cached key adds no entry, so the cache does not grow. Eviction belongs only in the branch for a new key. With capacity 2, put(1, 1), put(2, 2) and put(2, 5) must keep both keys. Evicting on the update removes key 1.
Example: capacity = 2: put(1, 1), put(2, 2), put(2, 5), then get(1)
Mistake: returns -1Fix: returns 1

Not this one if…

Only the last size values are kept and they leave in arrival order, as in Moving Average from Data Stream (LC 346): a queue drops the oldest value, nothing is looked up by key, and reading a value never makes it stay longer. See Fixed Window

Deep Dive

Why the list stays in order of use

Then get(2) returns -1, because key 2 is gone. get(1) returns 9 and moves key 1 to the front, so the list is 1:9, 3:3.

This is why the card's invariant says that the list holds exactly the nodes in self.cache, in order of use. Each method changes the map and the list together.

Why a doubly linked list, and why sentinels

The least recently used node is always self.tail.prev. That is the node put evicts when the cache is full.

Why each node stores its key

Eviction removes the node from the list and the entry from the map. The list gives lru = self.tail.prev. The map entry is self.cache[lru.key], so the node must know its own key.

Updating a key that already exists

Each call does a fixed number of dictionary and pointer operations. So get and put are O(1), and the space is O(cap).

60-Second Pitch

Common Questions

What is the time and space complexity?: get and put are both O(1) time. The map lookup is O(1) on average, and _remove and _add_to_head change a fixed number of links. The space is O(capacity), for at most cap nodes and cap map entries.
Why not use an array or a plain list for the order?: Moving an item to the front of a Python list takes O(N), because the other items shift. A doubly linked list moves a node by changing four links. The map gives the node in O(1), so no search is needed.
Can you use OrderedDict instead?: Yes, in Python. OrderedDict.move_to_end moves a key in O(1), and popitem(last=False) removes the oldest key in O(1). Many interviewers accept it, but some ask for the list version. The list version shows that you know why the moves are O(1).
What changes for a least frequently used cache?: Order of use is no longer enough, because the key with the lowest use count must go. LFU Cache (LC 460) keeps a count for each key and one list of keys for each count. Ties inside one count are broken by recency, which is the LRU rule again.
How would this change with several threads?: A get also writes to the list, so two threads can corrupt the links. The simplest fix is one lock around each method. For heavy traffic, split the cache into several parts, each with its own lock and its own list, and choose the part by the hash of the key.

SWE Reasoning

Spot it

A design problem asks for get and put in O(1).
When the cache is full, the entry used longest ago must be removed.
Both reading and writing count as a use.
One structure alone fails: a hash map has no order, and a list has no O(1) lookup.
The statement says "least recently used", or a variant with counts (LFU Cache (LC 460)).

The invariant, step by step

LRUCache(cap) creates an empty self.cache, and links head to tail. The list holds no nodes.
put of a new key checks len(self.cache) >= self.cap. If the cache is full, it takes lru = self.tail.prev, calls _remove(lru) and runs del self.cache[lru.key].
It then creates a node, stores it in self.cache[key] and calls _add_to_head. The list and the map each gained one node.
get of a key in self.cache calls _remove(node) and then _add_to_head(node). The node moves from its place to the front, and the map is unchanged.
put of an existing key sets node.val and moves the node the same way.
Every use leaves the used node next to head, so the node next to tail is the one used longest ago. The list and the map hold the same keys after every call.

Traps

Updating node.val without moving the node. The node keeps its old place and is evicted too early.
Evicting from the list but not the map. If del self.cache[lru.key] is missing, a later get finds a node that is no longer in the list.
A node without key. The eviction code cannot find the map entry to delete.
Moving only on put. get is a use too. Without the move in get, a key that is read often can still be evicted.
Checking > instead of >=. With len(self.cache) > self.cap, the cache grows to cap + 1 before it evicts.
Forgetting that get of a missing key returns -1. The function must return before it touches the list.

Practice

Canonical LeetCode:LRU Cache (LC 146)LFU Cache (LC 460)All O`one Data Structure (LC 432)First Unique Number (LC 1429)Design Authentication Manager (LC 1797)

Theory Context•Advanced Data Structures

Builds on Dummy Node and Hash Map, which you haven’t finished yet.

P2MediumMental model~12 min speedrun

LRU Cache (HashMap + Doubly Linked List)

The problem

LRU Cache (LC 146)(opens leetcode.com)

A cache with a fixed capacity needs to hold key-value pairs and, whenever it's full and a new key arrives, evict whichever key was touched longest ago.

Build an LRUCache class:

LRUCache(int capacity) sets up the cache with a positive capacity.
int get(int key) returns the value stored for key, or -1 if key isn't present.
void put(int key, int value) inserts key with value, or overwrites the value if key is already present. If this push takes the cache past capacity, evict the least recently used key first.

Both get and put must run in O(1) average time.

Example 1

Input:["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

Output:[null, null, null, 1, null, -1, null, -1, 3, 4]

put(1, 1), put(2, 2), get(1) -> 1, put(3, 3) evicts key 2, get(2) -> -1 (not found), put(4, 4) evicts key 1, get(1) -> -1, get(3) -> 3, get(4) -> 4.

LRU Cache

key-value storage ➔ hash map (O(1) lookup) + DLL (O(1) recency)

Spot it when: A design problem asks for O(1) lookups plus eviction by least recent use (or by frequency).

LRU Cache

Python

1	from typing import Optional
2
3	class DLinkedNode:
4	def __init__(self, key: int = 0, val: int = 0) -> None:
5	self.key = key # Stored so eviction can delete the map entry
6	self.val = val
7	self.prev: Optional["DLinkedNode"] = None
8	self.next: Optional["DLinkedNode"] = None
9
10	class LRUCache:
11	"""LRU Cache: hash map for O(1) lookup + doubly-linked list for O(1) recency order.
12	Time: O(1) get and put \| Space: O(capacity)
13	"""
14	def __init__(self, capacity: int) -> None:
15	self.cap = capacity
16	self.cache: dict[int, DLinkedNode] = {}
17	self.head = DLinkedNode() # Sentinel: most recent side
18	self.tail = DLinkedNode() # Sentinel: least recent side
19	self.head.next = self.tail
20	self.tail.prev = self.head
21
22	def _remove(self, node: DLinkedNode) -> None:
23	node.prev.next = node.next # Unlink: sentinels mean no null checks
24	node.next.prev = node.prev
25
26	def _add_to_head(self, node: DLinkedNode) -> None:
27	node.prev = self.head
28	node.next = self.head.next
29	self.head.next.prev = node
30	self.head.next = node
31
32	def get(self, key: int) -> int:
33	# 1. Return A Miss, Or Promote The Found Node To Most Recently Used:
34	# A successful read counts as a use just like a write, so the node must move to the front
35	# before its value is returned; otherwise the node next to tail could stop being the least-recently-used one.
36	if key not in self.cache:
37	return -1
38	node = self.cache[key]
39	self._remove(node) # A read counts as a use:
40	self._add_to_head(node) # move to the most recent position
41	return node.val
42
43	def put(self, key: int, value: int) -> None:
44	# 1. Update In Place And Promote, Or Insert A New Node (Evicting If Full):
45	# An existing key keeps its map entry and only moves to the front; a brand-new key may first
46	# evict the node next to tail, which is always the least recently used because every use moves its node to the front.
47	if key in self.cache:
48	node = self.cache[key]
49	node.val = value # Update in place, then mark as most recent
50	self._remove(node)
51	self._add_to_head(node)
52	else:
53	if len(self.cache) >= self.cap:
54	lru = self.tail.prev # Least recently used sits next to the tail
55	self._remove(lru)
56	del self.cache[lru.key]
57	new_node = DLinkedNode(key, value)
58	self.cache[key] = new_node
59	self._add_to_head(new_node)

Invariant: The list from head to tail holds exactly the nodes in self.cache, ordered from most to least recently used.

See it run

LRU Cache, capacity 2, ops = put(1, 1), put(2, 2), put(1, 9), put(3, 3), get(2), get(1)

call none yet

The row is the list from head to tail. Each box shows key:val. The box next to head is the most recently used key.

used the node that this call reads, writes or moves to the front
lru the least recently used node, next to tail

The cache is empty, so head is linked straight to tail.

self.cache keys

empty

1 / 12

Gotchas1 of 4

The trap
Gotcha 1: Updating node.val without moving the node to the front
Mistake
```
node.val = value
```
Fix
```
node.val = value
self._remove(node)
self._add_to_head(node)
```
What happens: put on a cached key is a use, like get. Without the move, the node keeps its old place near tail. With capacity 2, put(1, 1), put(2, 2), put(1, 9) and put(3, 3) then evict key 1. Key 2 was used less recently, so key 2 must be evicted.
Example: capacity = 2: put(1, 1), put(2, 2), put(1, 9), put(3, 3), then get(1) and get(2)
Mistake: returns (-1, 2)Fix: returns (9, -1)
Gotcha 2: Evicting the node without del self.cache[lru.key]
Mistake
```
self._remove(lru)
```
Fix
```
self._remove(lru)
del self.cache[lru.key]
```
What happens: Eviction must remove the key from the map as well as the node from the list. Each node stores its key for exactly this line. Without it, the map keeps the evicted key. A later get finds it and returns a value that was evicted.
Example: capacity = 1: put(1, 1), put(2, 2), then get(1)
Mistake: returns 1Fix: returns -1
Gotcha 3: Calling _add_to_head before _remove in get
Mistake
```
self._add_to_head(node)
self._remove(node)
return node.val
```
Fix
```
self._remove(node)
self._add_to_head(node)
return node.val
```
What happens: _add_to_head(node) links the node after head, but its old neighbours still point to it. _remove(node) then uses the new node.prev and node.next, so it unlinks the node only from the front. The list is now broken. In this example, put(3, 5) evicts key 2, which get(2) has just read, and keeps key 1.
Example: capacity = 2: put(2, 2), put(1, 9), get(2), put(3, 5), then get(1)
Mistake: returns 9Fix: returns -1
Gotcha 4: Evicting when put updates a key that is already cached
Mistake
```
def put(self, key: int, value: int) -> None:
    if len(self.cache) >= self.cap:  # runs for every put
        lru = self.tail.prev
```
Fix
```
else:
    if len(self.cache) >= self.cap:
        lru = self.tail.prev
```
What happens: Updating a cached key adds no entry, so the cache does not grow. Eviction belongs only in the branch for a new key. With capacity 2, put(1, 1), put(2, 2) and put(2, 5) must keep both keys. Evicting on the update removes key 1.
Example: capacity = 2: put(1, 1), put(2, 2), put(2, 5), then get(1)
Mistake: returns -1Fix: returns 1

Not this one if…

Only the last size values are kept and they leave in arrival order, as in Moving Average from Data Stream (LC 346): a queue drops the oldest value, nothing is looked up by key, and reading a value never makes it stay longer. See Fixed Window

Deep Dive

Why the list stays in order of use

Then get(2) returns -1, because key 2 is gone. get(1) returns 9 and moves key 1 to the front, so the list is 1:9, 3:3.

This is why the card's invariant says that the list holds exactly the nodes in self.cache, in order of use. Each method changes the map and the list together.

Why a doubly linked list, and why sentinels

The least recently used node is always self.tail.prev. That is the node put evicts when the cache is full.

Why each node stores its key

Eviction removes the node from the list and the entry from the map. The list gives lru = self.tail.prev. The map entry is self.cache[lru.key], so the node must know its own key.

Updating a key that already exists

Each call does a fixed number of dictionary and pointer operations. So get and put are O(1), and the space is O(cap).

60-Second Pitch

Common Questions

What is the time and space complexity?: get and put are both O(1) time. The map lookup is O(1) on average, and _remove and _add_to_head change a fixed number of links. The space is O(capacity), for at most cap nodes and cap map entries.
Why not use an array or a plain list for the order?: Moving an item to the front of a Python list takes O(N), because the other items shift. A doubly linked list moves a node by changing four links. The map gives the node in O(1), so no search is needed.
Can you use OrderedDict instead?: Yes, in Python. OrderedDict.move_to_end moves a key in O(1), and popitem(last=False) removes the oldest key in O(1). Many interviewers accept it, but some ask for the list version. The list version shows that you know why the moves are O(1).
What changes for a least frequently used cache?: Order of use is no longer enough, because the key with the lowest use count must go. LFU Cache (LC 460) keeps a count for each key and one list of keys for each count. Ties inside one count are broken by recency, which is the LRU rule again.
How would this change with several threads?: A get also writes to the list, so two threads can corrupt the links. The simplest fix is one lock around each method. For heavy traffic, split the cache into several parts, each with its own lock and its own list, and choose the part by the hash of the key.

SWE Reasoning

Spot it

A design problem asks for get and put in O(1).
When the cache is full, the entry used longest ago must be removed.
Both reading and writing count as a use.
One structure alone fails: a hash map has no order, and a list has no O(1) lookup.
The statement says "least recently used", or a variant with counts (LFU Cache (LC 460)).

The invariant, step by step

LRUCache(cap) creates an empty self.cache, and links head to tail. The list holds no nodes.
put of a new key checks len(self.cache) >= self.cap. If the cache is full, it takes lru = self.tail.prev, calls _remove(lru) and runs del self.cache[lru.key].
It then creates a node, stores it in self.cache[key] and calls _add_to_head. The list and the map each gained one node.
get of a key in self.cache calls _remove(node) and then _add_to_head(node). The node moves from its place to the front, and the map is unchanged.
put of an existing key sets node.val and moves the node the same way.
Every use leaves the used node next to head, so the node next to tail is the one used longest ago. The list and the map hold the same keys after every call.

Traps

Updating node.val without moving the node. The node keeps its old place and is evicted too early.
Evicting from the list but not the map. If del self.cache[lru.key] is missing, a later get finds a node that is no longer in the list.
A node without key. The eviction code cannot find the map entry to delete.
Moving only on put. get is a use too. Without the move in get, a key that is read often can still be evicted.
Checking > instead of >=. With len(self.cache) > self.cap, the cache grows to cap + 1 before it evicts.
Forgetting that get of a missing key returns -1. The function must return before it touches the list.

Practice

Canonical LeetCode:LRU Cache (LC 146)LFU Cache (LC 460)All O`one Data Structure (LC 432)First Unique Number (LC 1429)Design Authentication Manager (LC 1797)

Theory Context•Advanced Data Structures

Builds on Dummy Node and Hash Map, which you haven’t finished yet.

P2MediumMental model~12 min speedrun

LRU Cache (HashMap + Doubly Linked List)

The problem

LRU Cache (LC 146)(opens leetcode.com)

A cache with a fixed capacity needs to hold key-value pairs and, whenever it's full and a new key arrives, evict whichever key was touched longest ago.

Build an LRUCache class:

LRUCache(int capacity) sets up the cache with a positive capacity.
int get(int key) returns the value stored for key, or -1 if key isn't present.
void put(int key, int value) inserts key with value, or overwrites the value if key is already present. If this push takes the cache past capacity, evict the least recently used key first.

Both get and put must run in O(1) average time.

Example 1

Input:["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

Output:[null, null, null, 1, null, -1, null, -1, 3, 4]

put(1, 1), put(2, 2), get(1) -> 1, put(3, 3) evicts key 2, get(2) -> -1 (not found), put(4, 4) evicts key 1, get(1) -> -1, get(3) -> 3, get(4) -> 4.

LRU Cache

key-value storage ➔ hash map (O(1) lookup) + DLL (O(1) recency)

Spot it when: A design problem asks for O(1) lookups plus eviction by least recent use (or by frequency).

LRU Cache

Python

1	from typing import Optional
2
3	class DLinkedNode:
4	def __init__(self, key: int = 0, val: int = 0) -> None:
5	self.key = key # Stored so eviction can delete the map entry
6	self.val = val
7	self.prev: Optional["DLinkedNode"] = None
8	self.next: Optional["DLinkedNode"] = None
9
10	class LRUCache:
11	"""LRU Cache: hash map for O(1) lookup + doubly-linked list for O(1) recency order.
12	Time: O(1) get and put \| Space: O(capacity)
13	"""
14	def __init__(self, capacity: int) -> None:
15	self.cap = capacity
16	self.cache: dict[int, DLinkedNode] = {}
17	self.head = DLinkedNode() # Sentinel: most recent side
18	self.tail = DLinkedNode() # Sentinel: least recent side
19	self.head.next = self.tail
20	self.tail.prev = self.head
21
22	def _remove(self, node: DLinkedNode) -> None:
23	node.prev.next = node.next # Unlink: sentinels mean no null checks
24	node.next.prev = node.prev
25
26	def _add_to_head(self, node: DLinkedNode) -> None:
27	node.prev = self.head
28	node.next = self.head.next
29	self.head.next.prev = node
30	self.head.next = node
31
32	def get(self, key: int) -> int:
33	# 1. Return A Miss, Or Promote The Found Node To Most Recently Used:
34	# A successful read counts as a use just like a write, so the node must move to the front
35	# before its value is returned; otherwise the node next to tail could stop being the least-recently-used one.
36	if key not in self.cache:
37	return -1
38	node = self.cache[key]
39	self._remove(node) # A read counts as a use:
40	self._add_to_head(node) # move to the most recent position
41	return node.val
42
43	def put(self, key: int, value: int) -> None:
44	# 1. Update In Place And Promote, Or Insert A New Node (Evicting If Full):
45	# An existing key keeps its map entry and only moves to the front; a brand-new key may first
46	# evict the node next to tail, which is always the least recently used because every use moves its node to the front.
47	if key in self.cache:
48	node = self.cache[key]
49	node.val = value # Update in place, then mark as most recent
50	self._remove(node)
51	self._add_to_head(node)
52	else:
53	if len(self.cache) >= self.cap:
54	lru = self.tail.prev # Least recently used sits next to the tail
55	self._remove(lru)
56	del self.cache[lru.key]
57	new_node = DLinkedNode(key, value)
58	self.cache[key] = new_node
59	self._add_to_head(new_node)

Invariant: The list from head to tail holds exactly the nodes in self.cache, ordered from most to least recently used.

See it run

LRU Cache, capacity 2, ops = put(1, 1), put(2, 2), put(1, 9), put(3, 3), get(2), get(1)

call none yet

The row is the list from head to tail. Each box shows key:val. The box next to head is the most recently used key.

used the node that this call reads, writes or moves to the front
lru the least recently used node, next to tail

The cache is empty, so head is linked straight to tail.

self.cache keys

empty

1 / 12

Gotchas1 of 4

The trap
Gotcha 1: Updating node.val without moving the node to the front
Mistake
```
node.val = value
```
Fix
```
node.val = value
self._remove(node)
self._add_to_head(node)
```
What happens: put on a cached key is a use, like get. Without the move, the node keeps its old place near tail. With capacity 2, put(1, 1), put(2, 2), put(1, 9) and put(3, 3) then evict key 1. Key 2 was used less recently, so key 2 must be evicted.
Example: capacity = 2: put(1, 1), put(2, 2), put(1, 9), put(3, 3), then get(1) and get(2)
Mistake: returns (-1, 2)Fix: returns (9, -1)
Gotcha 2: Evicting the node without del self.cache[lru.key]
Mistake
```
self._remove(lru)
```
Fix
```
self._remove(lru)
del self.cache[lru.key]
```
What happens: Eviction must remove the key from the map as well as the node from the list. Each node stores its key for exactly this line. Without it, the map keeps the evicted key. A later get finds it and returns a value that was evicted.
Example: capacity = 1: put(1, 1), put(2, 2), then get(1)
Mistake: returns 1Fix: returns -1
Gotcha 3: Calling _add_to_head before _remove in get
Mistake
```
self._add_to_head(node)
self._remove(node)
return node.val
```
Fix
```
self._remove(node)
self._add_to_head(node)
return node.val
```
What happens: _add_to_head(node) links the node after head, but its old neighbours still point to it. _remove(node) then uses the new node.prev and node.next, so it unlinks the node only from the front. The list is now broken. In this example, put(3, 5) evicts key 2, which get(2) has just read, and keeps key 1.
Example: capacity = 2: put(2, 2), put(1, 9), get(2), put(3, 5), then get(1)
Mistake: returns 9Fix: returns -1
Gotcha 4: Evicting when put updates a key that is already cached
Mistake
```
def put(self, key: int, value: int) -> None:
    if len(self.cache) >= self.cap:  # runs for every put
        lru = self.tail.prev
```
Fix
```
else:
    if len(self.cache) >= self.cap:
        lru = self.tail.prev
```
What happens: Updating a cached key adds no entry, so the cache does not grow. Eviction belongs only in the branch for a new key. With capacity 2, put(1, 1), put(2, 2) and put(2, 5) must keep both keys. Evicting on the update removes key 1.
Example: capacity = 2: put(1, 1), put(2, 2), put(2, 5), then get(1)
Mistake: returns -1Fix: returns 1

Not this one if…

Only the last size values are kept and they leave in arrival order, as in Moving Average from Data Stream (LC 346): a queue drops the oldest value, nothing is looked up by key, and reading a value never makes it stay longer. See Fixed Window

Deep Dive

Why the list stays in order of use

Then get(2) returns -1, because key 2 is gone. get(1) returns 9 and moves key 1 to the front, so the list is 1:9, 3:3.

This is why the card's invariant says that the list holds exactly the nodes in self.cache, in order of use. Each method changes the map and the list together.

Why a doubly linked list, and why sentinels

The least recently used node is always self.tail.prev. That is the node put evicts when the cache is full.

Why each node stores its key

Eviction removes the node from the list and the entry from the map. The list gives lru = self.tail.prev. The map entry is self.cache[lru.key], so the node must know its own key.

Updating a key that already exists

Each call does a fixed number of dictionary and pointer operations. So get and put are O(1), and the space is O(cap).

60-Second Pitch

Common Questions

What is the time and space complexity?: get and put are both O(1) time. The map lookup is O(1) on average, and _remove and _add_to_head change a fixed number of links. The space is O(capacity), for at most cap nodes and cap map entries.
Why not use an array or a plain list for the order?: Moving an item to the front of a Python list takes O(N), because the other items shift. A doubly linked list moves a node by changing four links. The map gives the node in O(1), so no search is needed.
Can you use OrderedDict instead?: Yes, in Python. OrderedDict.move_to_end moves a key in O(1), and popitem(last=False) removes the oldest key in O(1). Many interviewers accept it, but some ask for the list version. The list version shows that you know why the moves are O(1).
What changes for a least frequently used cache?: Order of use is no longer enough, because the key with the lowest use count must go. LFU Cache (LC 460) keeps a count for each key and one list of keys for each count. Ties inside one count are broken by recency, which is the LRU rule again.
How would this change with several threads?: A get also writes to the list, so two threads can corrupt the links. The simplest fix is one lock around each method. For heavy traffic, split the cache into several parts, each with its own lock and its own list, and choose the part by the hash of the key.

SWE Reasoning

Spot it

A design problem asks for get and put in O(1).
When the cache is full, the entry used longest ago must be removed.
Both reading and writing count as a use.
One structure alone fails: a hash map has no order, and a list has no O(1) lookup.
The statement says "least recently used", or a variant with counts (LFU Cache (LC 460)).

The invariant, step by step

LRUCache(cap) creates an empty self.cache, and links head to tail. The list holds no nodes.
put of a new key checks len(self.cache) >= self.cap. If the cache is full, it takes lru = self.tail.prev, calls _remove(lru) and runs del self.cache[lru.key].
It then creates a node, stores it in self.cache[key] and calls _add_to_head. The list and the map each gained one node.
get of a key in self.cache calls _remove(node) and then _add_to_head(node). The node moves from its place to the front, and the map is unchanged.
put of an existing key sets node.val and moves the node the same way.
Every use leaves the used node next to head, so the node next to tail is the one used longest ago. The list and the map hold the same keys after every call.

Traps

Updating node.val without moving the node. The node keeps its old place and is evicted too early.
Evicting from the list but not the map. If del self.cache[lru.key] is missing, a later get finds a node that is no longer in the list.
A node without key. The eviction code cannot find the map entry to delete.
Moving only on put. get is a use too. Without the move in get, a key that is read often can still be evicted.
Checking > instead of >=. With len(self.cache) > self.cap, the cache grows to cap + 1 before it evicts.
Forgetting that get of a missing key returns -1. The function must return before it touches the list.

Practice

Canonical LeetCode:LRU Cache (LC 146)LFU Cache (LC 460)All O`one Data Structure (LC 432)First Unique Number (LC 1429)Design Authentication Manager (LC 1797)