LFU Cache

LFU Cache

Least-frequently-used eviction with an LRU tiebreak — the harder sibling of LRU and a genuine O(1)-design challenge.

Requirements

• Every key tracks a use count: 1 on insert, +1 on each get hit and each put update.
• Eviction victim: minimum use count; ties broken by least-recent use (any hit or update refreshes recency).
• Updating an existing key never evicts.
• A new key always enters with count 1 — even if it was previously evicted with a higher count.

API to implement

Implement the class LFUCache. The I/O driver is already written in the starter code — it parses the command script below and calls your methods. You only implement the class.

| Command | Returns | Behavior | |---|---|---| | put <key> <value> | — | Insert or update. Updating bumps the key's use count. Inserting a new key into a full cache first evicts the least-frequently-used key; on a frequency tie, the least-recently-used of those. | | get <key> | int | Return the value or -1. A hit bumps the key's use count and recency. |

Input format

The first line contains Q, the number of operations. The second line contains the constructor argument: capacity — maximum entries (≥ 1). Each of the next Q lines is one command as listed above. String arguments contain no spaces.

Output format

For each command with a non-void return, print its result on its own line, in order. The driver does this for you — your methods just return values.

This is a design problem: the hidden tests exercise edge cases and interaction sequences, not performance tricks. Model the state cleanly and the tests will pass.

10
2
put 1 1
put 2 2
get 1
put 3 3
get 2
get 3
put 4 4
get 1
get 3
get 4

1
-1
3
-1
3
4

5
1
put 1 1
get 1
put 2 2
get 1
get 2

1
-1
2