p101 — LFU Cache — Hints

1. The trap: if you reach for heapq or SortedDict, you’ve already conceded O(log n). Both get and put must be strictly O(1). Re-read the problem; then ask: what data structure gives O(1) remove(node) given a node pointer? Answer: doubly-linked list.

2. Two levels of indexing. You need to find a key fast (level 1: dict[key, node]). When evicting, you need to find the min-frequency key fast (level 2: dict[freq, list_of_nodes]). The level-2 list must be ordered by recency so the tail is the LRU within that frequency.

3. The min_freq pointer never scans. It can only change in two ways: (a) a brand-new put sets it to 1; (b) the bucket at min_freq becomes empty and the just-bumped node now lives at min_freq + 1 → so min_freq += 1. Convince yourself there is no other case.

4. put of an existing key is an access too. It updates the value AND counts as a get for tie-breaking. If you forget, your eviction picks the wrong key on the next full insert.

5. Edge case the autograder loves: capacity == 0. Every put is a no-op; every get returns -1. Don’t blow up on the first put.

If stuck: see solution.py.