Design a Least Frequently Used (LFU) Cache with O(1) Operations
Company: xAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Design and implement a data structure for a **least frequently used (LFU) cache**.
Implement a class `LFUCache` with the following operations:
- `LFUCache(int capacity)` — initializes the cache with a positive integer `capacity`.
- `int get(int key)` — returns the value associated with `key` if it exists in the cache; otherwise returns `-1`.
- `void put(int key, int value)` — if `key` already exists, updates its value. Otherwise, inserts the key–value pair. If inserting the new pair would exceed `capacity`, the cache must first **evict the least frequently used key**. If two or more keys are tied for the lowest use frequency, evict the **least recently used** key among them.
**Frequency rules:**
- A key's use counter is set to `1` when it is inserted with `put`.
- Every subsequent `get` or `put` on an existing key increments its use counter by `1`.
- When a key is evicted and later re-inserted, its counter starts again at `1`.
Both `get` and `put` must run in **O(1)** average time complexity.
**Example:**
```
LFUCache cache = new LFUCache(2);
cache.put(1, 10); // cache = {1: 10}, freq(1) = 1
cache.put(2, 20); // cache = {1: 10, 2: 20}, freq(1) = 1, freq(2) = 1
cache.get(1); // returns 10; freq(1) = 2
cache.put(3, 30); // capacity full: key 2 has the lowest frequency, so evict 2
// cache = {1: 10, 3: 30}, freq(3) = 1
cache.get(2); // returns -1 (evicted)
cache.get(3); // returns 30; freq(3) = 2
cache.put(4, 40); // keys 1 and 3 are tied at frequency 2; key 1 is the
// least recently used of the two, so evict 1
// cache = {3: 30, 4: 40}
cache.get(1); // returns -1 (evicted)
cache.get(3); // returns 30
cache.get(4); // returns 40
```
**Constraints:**
- `1 <= capacity <= 10^4`
- `0 <= key <= 10^5`
- `0 <= value <= 10^9`
- At most `2 * 10^5` total calls will be made to `get` and `put`.
Quick Answer: This question evaluates understanding of data structures and algorithm design for implementing a Least Frequently Used (LFU) cache with O(1) get and put operations, emphasizing frequency tracking and least-recently-used tie-breaking.
Design and implement a data structure for a **least frequently used (LFU) cache** that supports `get` and `put` in **O(1)** average time.
Because the online judge drives your code with a single entry point, you implement a function `solution(operations, values)` that **replays a sequence of operations** against your cache and returns the results.
- `operations` is a list of operation names, e.g. `["LFUCache", "put", "put", "get", ...]`. The first entry is always `"LFUCache"` (the constructor).
- `values` is a list of argument lists, aligned with `operations`:
- `["LFUCache", [capacity]]` initializes the cache with the given positive `capacity`.
- `["put", [key, value]]` inserts or updates the pair.
- `["get", [key]]` looks up `key`.
**Return** a list containing the result of each `get` call, in the order the `get` calls occur (`put` and the constructor produce no output).
**Cache semantics:**
- `get(key)` returns the value for `key` if present, otherwise `-1`.
- `put(key, value)` updates an existing key, or inserts a new pair. If the cache is at `capacity`, it first **evicts the least frequently used key**; ties are broken by evicting the **least recently used** among the tied keys.
**Frequency rules:**
- A key's use counter is `1` when first inserted with `put`.
- Every subsequent `get` or `put` on an existing key increments its counter by `1`.
- A key that is evicted and later re-inserted restarts its counter at `1`.
**Example**
```
operations = ["LFUCache","put","put","get","put","get","get","put","get","get","get"]
values = [[2],[1,10],[2,20],[1],[3,30],[2],[3],[4,40],[1],[3],[4]]
// get(1)=10, then put(3,30) evicts key 2 (lowest freq)
// get(2)=-1, get(3)=30, then put(4,40): keys 1 and 3 tie at freq 2,
// key 1 is least-recently-used, so evict 1
// get(1)=-1, get(3)=30, get(4)=40
return [10, -1, 30, -1, 30, 40]
```
**Constraints:**
- `1 <= capacity <= 10^4`
- `0 <= key <= 10^5`
- `0 <= value <= 10^9`
- At most `2 * 10^5` total `get` and `put` calls.
Constraints
- 1 <= capacity <= 10^4
- 0 <= key <= 10^5
- 0 <= value <= 10^9
- At most 2 * 10^5 total calls to get and put
- get and put must run in O(1) average time
Examples
Input: (['LFUCache','put','put','get','put','get','get','put','get','get','get'], [[2],[1,10],[2,20],[1],[3,30],[2],[3],[4,40],[1],[3],[4]])
Expected Output: [10, -1, 30, -1, 30, 40]
Explanation: capacity 2. get(1)=10 (freq1->2). put(3,30) evicts key 2 (lowest freq). get(2)=-1, get(3)=30 (freq3->2). put(4,40): keys 1 and 3 tie at freq 2, key 1 is least recently used so evict 1. get(1)=-1, get(3)=30, get(4)=40.
Input: (['LFUCache','put','get','put','get','get'], [[1],[1,1],[1],[2,2],[1],[2]])
Expected Output: [1, -1, 2]
Explanation: capacity 1. get(1)=1. put(2,2) evicts the only key (1). get(1)=-1, get(2)=2.
Hints
- Keep three maps: key->value, key->frequency, and frequency->ordered set of keys at that frequency. An OrderedDict per frequency preserves recency so you can break ties by least-recently-used.
- Track a running `min_freq`. On eviction, remove the oldest key in the bucket at `min_freq`.
- On any access (get, or put on an existing key), move the key from its current frequency bucket to the next one. If the old bucket was the `min_freq` bucket and it becomes empty, increment `min_freq`.
- A brand-new insert always has frequency 1, so set `min_freq = 1` right after inserting. Handle capacity 0 as a no-op if you ever generalize it.