Least Recently Used Cache | Practice

Write a class LRUCache, a key-value store that holds at most capacity keys:

LRUCache(capacity) makes an empty cache.
get(key) returns the value stored for key, or -1 if the cache doesn't hold it.
put(key, value) stores value for key, replacing any old value. If that would add a new key to a full cache, first remove the least recently used key: the one whose last get or put was longest ago.

A get that finds its key and every put count as using that key. Both methods must take constant time on average.

Each test is a list of calls, starting with the constructor; the expected answer lists what each call returns (null for the constructor and for put).

Example 1

Calls: LRUCache(2), put(1, 100), put(2, 200), get(1), put(3, 300), get(2), get(3), get(1)
Returns: [null, null, null, 100, null, -1, 300, 100]

Reading key 1 makes key 2 the least recently used, so putting key 3 evicts key 2.

Example 2

Calls: LRUCache(1), put(5, 7), put(5, 8), get(5), put(6, 9), get(5)
Returns: [null, null, null, 8, null, -1]

Putting a key that is already there replaces its value and evicts nothing.

Constraints

1 ≤ capacity ≤ 3000
Keys are between 0 and 10⁴; values are between 0 and 10⁵.
A test makes at most 2 × 10⁵ calls.

Show the pattern

Hashing, Linked list

You need constant-time lookup by key, which is a hash map, and constant-time "mark as just used" and "drop the oldest", which is a doubly linked list kept in order of use. Each map entry points at its node in the list.

See hashing in a visualiser

Show the approach

Combine a hash map with a doubly linked list kept in order of use, least recent at the front and most recent at the back. The map takes each key to its node, which stores the key and the value. Two dummy nodes, head and tail, sit at the ends, so unlinking or appending a node never meets a missing neighbour.

get(key): if the key isn't in the map, return −1. Otherwise unlink its node, append it at the back, and return its value.
put(key, value): if the key is in the map, update its node's value and move the node to the back. Otherwise, if the cache is full, unlink the node just after head (the least recently used) and delete its key from the map; then append a new node and record it in the map.

Every call is a few pointer changes and map operations, so each takes constant time.

Time: O(1) per call, on average · Space: O(capacity)

Brush up firstHash Table visualiser Linked List visualiser