LFU Cache

Problem

Design a fixed-capacity cache that evicts the entry with the lowest use count; when several entries tie on use count, evict the one among them that was used least recently. Implement LFUCache with:

• __init__(capacity).
• get(key): return the value or -1 if absent. A hit increments the key's use count.
• put(key, value): insert or update. Updating an existing key increments its use count; inserting a new key gives it a count of 1, evicting first if the cache is full.

Both operations must be O(1) average time.

• 0 <= capacity, up to a few thousand (a capacity of 0 means every put is a no-op and every get returns -1).
• Keys and values are non-negative integers.
• Expect up to a couple hundred thousand operations.

Examples

• Capacity 2: put(10,1), put(20,2), get(10) → 1 (key 10 now has count 2); put(30,3) evicts key 20 (count 1, the minimum); get(20) → -1; get(30) → 3 (count 2); put(40,4): keys 10 and 30 both have count 2, key 10 was used less recently, so key 10 is evicted; get(10) → -1, get(30) → 3, get(40) → 4.
• Capacity 1: put(5,1), put(6,2) evicts key 5; get(5) → -1, get(6) → 2.
• Capacity 0: put(9,1), get(9) → -1.

Hints

1. Tracking counts in a hash map is easy; the hard part is finding the minimum-count key, and among those the least recent, in O(1).
2. Group keys by use count. Within a group, what structure gives you least-recent removal and O(1) move-to-front? You already know it from LRU.
3. Keep a map from count to a doubly linked list of nodes (LRU-ordered), a map from key to node, and a min_count integer. When a key is used, move it from list c to list c+1; min_count only ever needs to change by resetting to 1 on insert or incrementing by one when list min_count becomes empty.