1917. The Cache That Names What It Threw Away
A cache holds at most c entries. Two operations arrive, one per line:
put k v store the value v under the key k
get k print the value stored under k
Every put prints the key it had to throw away to make room, or keep if it
threw nothing away. Every get prints the stored value, or miss.
c = 2
put 1 10 -> keep
put 2 20 -> keep
get 1 -> 10 1 is now the most recently used
put 3 30 -> 2 2 was the least recently used, so 2 goes
get 2 -> miss
## The rules, stated so the answer is decidable
Problem 199 asks for a cache and observes eviction only indirectly, through a later miss. Here the victim is the answer, so the order has to be pinned down exactly:
- A successful
getCOUNTS AS A USE, so it moves that key to the most recently - used position.
- A
putof a key that is already present overwrites its value, counts as a - use, and evicts nothing. It prints
keepeven when the cache is full. - A
putof a NEW key evicts only when the cache is already atcentries, - and the victim is the least recently used entry.
- A
getthat misses changes nothing at all.
Without the first rule the problem is unanswerable: on the trace above, a cache
where reading does not count would have evicted 1 instead of 2 and printed 1.
## What most people try first
A map from key to value, plus a scan to find the oldest entry whenever a slot
is needed. The map half is right. The scan is O(c) per eviction, and with
c and q both at 2 * 10^5 a stream that evicts on almost every put costs
about 4 * 10^10 comparisons.
A list in use order also looks tempting on its own, and then a get has to
find the key by walking the list, which is O(c) per read instead.
## Both at once
Keep both and let each cover the other's weakness, the same habit problem 1914 uses:
order a doubly linked list of keys, most recently used at the front
where a map from key -> that key's node in the list
A get finds the node through the map in constant time and unlinks and
re-inserts it at the front, which is constant because a doubly linked node
knows both of its neighbours. The least recently used key is whatever sits at
the back, read in one step rather than searched for.
## Why the back really is the victim
The invariant is that the list holds exactly the cached keys in decreasing order of last use. Every operation that uses a key moves it to the front and nothing else moves, so the relative order of the others is untouched and the element at the back is the one no operation has touched for longest. That is the definition of least recently used, so the victim needs no search.
## Sizes
Keys and values reach 10^9, comfortably inside a signed 32 bit integer, whose
limit is 2147483647. Nothing here adds two of them, so no total needs 64
bits. Every operation is O(1), giving O(q) for the run and O(c) memory.
Constraints - `1 ≤ c ≤ 200000` - `1 ≤ q ≤ 200000` - `1 ≤ k ≤ 1000000000` - `0 ≤ v ≤ 1000000000` - the cache starts empty
Input
The first line contains two integers c and q, the capacity and the number of operations.
Each of the next q lines is either put k v or get k.
Output
Print one line for every operation. For a put, print the key that was evicted to make room, or keep if nothing was evicted. For a get, print the stored value, or miss if the key is not in the cache.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.