1919. Least Frequently Used, Oldest Loses the Tie
A cache holds at most c entries. Every entry carries a USE COUNT. Three
operations arrive, one per line:
put k v store v under k
get k print the value under k, or miss
count k print k's current use count, or miss
When a new key arrives and the cache is full, the entry with the SMALLEST use count is thrown away. If several share that smallest count, the one used longest ago goes.
c = 2
put 1 10 1 has count 1
put 2 20 2 has count 1
get 1 -> 10 1 now has count 2
put 3 30 1 and 2 both candidates? no: 2 has the smaller count
count 1 -> 2
count 2 -> miss
## The rules, stated so the answer is decidable
- An entry's count starts at 1 when it is inserted.
- A successful
getadds one to the count. Aputof a key already present - overwrites the value and also adds one.
countis a read of the bookkeeping, not a use: it never changes anything.- A
getorcountthat misses changes nothing.
The tie-break is not decoration. Without it the trace put 1 / put 2 / put 3 at
c = 2 has two legal answers, and with it there is exactly one: both entries
have count 1, key 1 was used longer ago, so key 1 goes.
## What most people try first
A map from key to value and count, and a sweep for the minimum count when a
slot is needed. It is correct and it is O(c) per eviction, so with c and q
both at 2 * 10^5 an evicting stream costs about 4 * 10^10 comparisons.
Reaching for a heap keyed by count is the next instinct and it does not fit
either: a get raises one key's count, and a binary heap cannot find that key
to repair its position without an index beside it, which is most of the work of
the real answer anyway.
## One list per count
val[k], cnt[k] the value and use count of each cached key
bucket[f] the keys whose count is f, in use order,
least recently used first
minf the smallest f with a non-empty bucket
A use moves a key from bucket[f] to bucket[f + 1], which is two linked-list
splices, and raises minf by one if it has just emptied bucket[minf]. An
eviction takes the FRONT of bucket[minf], which is the least recently used key
of the least used count, exactly what the rule asks for. An insertion sets the
count to 1 and minf to 1.
## Why minf never has to be searched for
minf can only change in two ways. An insertion sets a count of 1, and 1 is the
smallest count any entry can have, so minf = 1 is immediate. A use moves a key
up by exactly one, so if it empties bucket[minf] the next non-empty bucket can
only be minf + 1: no other bucket index was created or destroyed. So the
minimum is maintained by a single increment and never scanned for, which is what
makes the whole structure constant time.
## Sizes
Keys and values reach 10^9, inside a signed 32 bit integer whose limit is
2147483647. A use count cannot pass q, which is 2 * 10^5, so counts need
nothing wider either. Every operation is O(1) and the run is O(q) with
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 put k v, get k or count k.
Output
Print one line for every get and every count: the stored value for a get, the current use count for a count, or miss if the key is not in the cache. A put prints nothing.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.