LFU Cache

HardObject-Oriented Design

Description

Design and implement a data structure for a **Least Frequently Used (LFU) cache**. - `get(key)`: Returns the value if `key` exists, else `-1`. Each access (get or put-existing) increments the key's frequency by 1. - `put(key, value)`: Insert or update. If at capacity, evict the **least frequently used** key. Tie-break by the **least recently used** among keys with the lowest frequency. Both operations must run in **O(1) average time**. **For the auto-grader:** implement `lfuCacheOps(capacity, operations)` returning the result of each call in order: - `["put", key, value]` → `null` / `None` - `["get", key]` → value or `-1`

Example 1

Input: capacity = 2, operations = [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["get",3],["put",4,4],["get",1],["get",3],["get",4]]

Output: [null,null,1,null,-1,3,null,-1,3,4]

Explanation: After get(1), key 1 has freq 2, key 2 has freq 1. put(3,3) evicts key 2 (lowest freq). put(4,4) evicts key 1 (key 1 has freq 2, key 3 has freq 2, but key 1 was used less recently).

Constraints

- 0 <= capacity <= 10^4 - 0 <= key, value <= 10^9 - At most 2 * 10^5 calls.

Loading editor...