LFU cache with constant-time get and put

Implement a least-frequently-used (LFU) cache with get and put in O(1) average time. When the cache is full, evict the key used least often; among ties, evict the least recently used one.

Interface

Unless you agree on a different interface with the interviewer, assume:

• LFUCache(capacity: int)
• get(key: int) -> int — the value or -1; a hit counts as a use.
• put(key: int, value: int) -> None — updates an existing key (counts as a use) or inserts a new one with use count 1, evicting first if the cache is full.

A key evicted and inserted again starts over at count 1.

Example

c = LFUCache(2)
c.put(1, 10)            # freq(1) = 1
c.put(2, 20)            # freq(2) = 1
c.get(1)    ->  10      # freq(1) = 2
c.put(3, 30)            # full: key 2 has the lowest count -> evict 2
c.get(2)    ->  -1
c.get(3)    ->  30      # freq(3) = 2
c.put(4, 40)            # 1 and 3 both at 2; 1 was used less recently -> evict 1
c.get(1)    ->  -1
c.get(3)    ->  30
c.get(4)    ->  40

Constraints

• 1 <= capacity <= 10^4; keys up to 10^5, values up to 10^9; up to 2 * 10^5 calls.

Clarifying questions

• Does updating an existing key with put count as a use?
• How are frequency ties broken?
• Does a re-inserted key keep its old count?
• What if the capacity is zero?

What a strong answer covers

• A map from key to (value, count), a map from count to an ordered set of keys in recency order (a linked list or OrderedDict), and the current minimum count.
• On a use: move the key from bucket f to f + 1; if bucket f was the minimum and is now empty, the minimum becomes f + 1.
• On an insert into a full cache: evict the oldest key in the minimum bucket, then set the minimum to 1.
• Why each step is O(1), and tests for ties, updates and re-insertion.

Follow-ups

• Add counts that decay over time, so old popularity fades.
• Make it thread-safe.
• Compare LFU with LRU: which workloads favour each?