1918. A Cache Where Reading Does Not Count

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, or miss

The eviction rule is the whole problem: when a new key arrives and the cache is full, the entry whose last WRITE is oldest is thrown away. Reading an entry does not protect it. A put of a key already present overwrites its value and counts as a write, so it does refresh that entry.

c = 2 put 1 10 put 2 20 get 1 -> 10 reading 1 does NOT protect it put 3 30 1 is thrown away: its write is the oldest get 1 -> miss get 2 -> 20

## Why this is not problem 199

Problem 199 is the same cache with the opposite rule: there a read counts as a use, so reading key 1 would have protected it and key 2 would have gone instead. On the trace above that cache prints 10, then 10 again, then miss: the last two lines are swapped. Neither rule is more correct than the other. What matters is that a cache specification which does not say which one it means cannot be implemented, and this is the half of the fork that real write-heavy caches use, because a read is cheap to serve and tells you nothing about whether the value is about to change.

## What most people try first

Reach for the familiar LRU and move the entry on a read, because that is the version everybody has implemented. It passes any test whose reads happen to fall on entries that were going to survive anyway, which is most hand-written test data, and then differs on the first stream where a read lands on the oldest entry.

The other first attempt is a scan: keep a map and sweep it for the oldest write when a slot is needed. That is O(c) per eviction, so with c and q both at 2 * 10^5 an evicting stream costs about 4 * 10^10 comparisons.

## The structure

``` order a doubly linked list of keys, most recently WRITTEN at the front where a map from key -> that key's node

put k v: if k in where -> overwrite the value, move its node to the front else -> if full, drop the node at the back and forget its key insert a new node at the front get k: one map lookup, and nothing moves ```

## Why it is correct

The invariant is that the list holds the cached keys in decreasing order of last write. Only put touches the list, and it always moves or inserts at the front, so every other node keeps its relative position and the node at the back is the one no write has touched for longest. A get cannot break the invariant because it does not touch the list at all, which is exactly what the rule says.

Reading becomes strictly cheaper than in an LRU: one hash lookup with no pointer surgery, which is why this policy is used where reads vastly outnumber writes.

## Sizes

Keys and values reach 10^9, which fits in a signed 32 bit integer whose limit is 2147483647; nothing here adds two of them. Every operation is O(1), so 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