AlgoScope

LRU Cache

Evicts the least recently used entry. A hash map plus a recency list gives O(1) get and put.

Data structures, data structure, intermediate
put 4. Evicted 2.4:401:103:30head
put 4. Evicted 2.4:401:103:30head

LRU Cache: A hit moves the node to the front

Decision, step 6 of 8

put 4 40: a new key, but the cache holds 3 already. The tail, key 2, is the least recently used, so it is dropped from both the list and the map, and 4:40 becomes the head.

How lru cache works

Cost

Get
O(1)
Put
O(1)
Space
O(capacity)

Leads to

Topics that need this one first.

Taught by the same lesson

LRU Cache covers these too, in the same run.