Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
LRU Cache
Bookmark
Brute Force
Map + Linked List
Ordered Map
Input
Standard
All Hits
All Evictions
Custom
capacity
=
2
,
operations
=
[put(1,1), put(2,2), get(1), put(3,3), get(2), put(4,4), get(1), get(3), get(4)]
LRUCache(2)
put(1, 1)
put(2, 2)
get(1)
=
?
put(3, 3)
get(2)
=
?
put(4, 4)
get(1)
=
?
get(3)
=
?
get(4)
=
?
size 0 / 2
MRU
no index: every lookup walks the list
LRUCache(2)
put(1, 1)
put(2, 2)
get(1)
=
?
put(3, 3)
get(2)
=
?
put(4, 4)
get(1)
=
?
get(3)
=
?
get(4)
=
?
size 0 / 2
MRU
no index: every lookup walks the list
LRUCache(2)
put(1, 1)
put(2, 2)
get(1)
=
?
put(3, 3)
get(2)
=
?
put(4, 4)
get(1)
=
?
get(3)
=
?
get(4)
=
?
size 1 / 2 · 1 probes
key 1
1
MRU
LRU
cache[0].key
1
≠
2
comparison 1
LRUCache(2)
put(1, 1)
put(2, 2)
get(1)
=
?
put(3, 3)
get(2)
=
?
put(4, 4)
get(1)
=
?
get(3)
=
?
get(4)
=
?
size 2 / 2 · 3 probes
key 1
1
key 2
2
MRU
LRU
cache[1].key
1
==
1
comparison 2
LRUCache(2)
put(1, 1)
put(2, 2)
get(1)
=
1
put(3, 3)
get(2)
=
?
put(4, 4)
get(1)
=
?
get(3)
=
?
get(4)
=
?
size 2 / 2 · 5 probes
key 1
1
key 2
2
MRU
LRU
cache[1].key
2
≠
3
comparison 2
LRUCache(2)
put(1, 1)
put(2, 2)
get(1)
=
1
put(3, 3)
get(2)
=
?
put(4, 4)
get(1)
=
?
get(3)
=
?
get(4)
=
?
size 2 / 2 · 6 probes
key 1
1
key 3
3
MRU
LRU
cache[0].key
3
≠
2
comparison 1
LRUCache(2)
put(1, 1)
put(2, 2)
get(1)
=
1
put(3, 3)
get(2)
=
-1
put(4, 4)
get(1)
=
?
get(3)
=
?
get(4)
=
?
size 2 / 2 · 8 probes
key 1
1
key 3
3
MRU
LRU
cache[0].key
3
≠
4
comparison 1
LRUCache(2)
put(1, 1)
put(2, 2)
get(1)
=
1
put(3, 3)
get(2)
=
-1
put(4, 4)
get(1)
=
?
get(3)
=
?
get(4)
=
?
size 2 / 2 · 9 probes
key 3
3
key 4
4
MRU
LRU
call
get(1)
LRUCache(2)
put(1, 1)
put(2, 2)
get(1)
=
1
put(3, 3)
get(2)
=
-1
put(4, 4)
get(1)
=
-1
get(3)
=
?
get(4)
=
?
size 2 / 2 · 11 probes
key 3
3
key 4
4
MRU
LRU
call
get(3)
LRUCache(2)
put(1, 1)
put(2, 2)
get(1)
=
1
put(3, 3)
get(2)
=
-1
put(4, 4)
get(1)
=
-1
get(3)
=
3
get(4)
=
?
size 2 / 2 · 13 probes
key 3
3
key 4
4
MRU
LRU
call
get(4)
LRUCache(2)
put(1, 1)
put(2, 2)
get(1)
=
1
put(3, 3)
get(2)
=
-1
put(4, 4)
get(1)
=
-1
get(3)
=
3
get(4)
=
4
size 2 / 2 · 15 probes
key 3
3
key 4
4
MRU
LRU
All operations processed
· 15 key comparisons
algo
master
.
io
Step:
LRU Cache initialized with capacity 2: one list, most recently used first, and no index to look keys up with.
0 / 45
Input
Standard
All Hits
All Evictions
Custom
capacity
=
2
,
operations
=
[put(1,1), put(2,2), get(1), put(3,3), get(2), put(4,4), get(1), get(3), get(4)]
0 / 45
algo
master
.
io
Step:
LRU Cache initialized with capacity 2: one list, most recently used first, and no index to look keys up with.
