Weighted LRU Cache: Capacity Counted by Item Quantity
Company: xAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Design a variant of the classic least-recently-used (LRU) cache. In the classic version, the capacity limits the **number** of items stored. In this variant, every item carries a positive integer **quantity**, and the capacity limits the **total quantity** across all stored items — an item with quantity 3 consumes 3 units of capacity, not 1. All other behavior (recency tracking, eviction order) is identical to a standard LRU cache.
Implement the class `WeightedLRUCache`:
- `WeightedLRUCache(int capacity)` — initializes the cache with a positive integer `capacity`, the maximum total quantity the cache may hold at any time.
- `int get(int key)` — if `key` exists in the cache, returns its value and marks the key as the most recently used; otherwise returns `-1`.
- `void put(int key, int value, int quantity)` — inserts or updates an entry:
1. If `key` already exists, overwrite its value and quantity, and mark it as the most recently used.
2. Otherwise, insert `key` as the most recently used entry.
3. Afterwards, while the sum of quantities of all stored items exceeds `capacity`, evict the least recently used item.
An evicted key is removed entirely; a later `get` on it returns `-1` (and a later `put` re-inserts it as a fresh entry).
### Example
```
Input:
["WeightedLRUCache", "put", "put", "get", "put", "get", "get"]
[[5], [1, 10, 2], [2, 20, 2], [1], [3, 30, 3], [2], [1]]
Output:
[null, null, null, 10, null, -1, 10]
```
Explanation (capacity = 5):
1. `put(1, 10, 2)` — cache holds {1}, total quantity 2.
2. `put(2, 20, 2)` — cache holds {1, 2}, total quantity 4.
3. `get(1)` returns `10` and makes key 1 the most recently used; key 2 is now the least recently used.
4. `put(3, 30, 3)` — total quantity would become 7 > 5, so the least recently used key 2 is evicted; cache holds {1, 3}, total quantity 5.
5. `get(2)` returns `-1` (evicted).
6. `get(1)` returns `10`.
### Constraints
- `1 <= capacity <= 10^9`
- `1 <= quantity <= capacity` for every `put` call
- `0 <= key, value <= 10^9`
- At most `2 * 10^5` calls will be made to `get` and `put` combined.
### Performance requirement
Both `get` and `put` must run in average `O(1)` time. The eviction loop inside `put` is amortized `O(1)`: every stored item is evicted at most once, so total eviction work is bounded by the total number of insertions.
Quick Answer: This question evaluates understanding of cache design and LRU eviction semantics with weighted resource accounting, plus data-structure and amortized-complexity reasoning needed to support O(1) average-time operations.
Design a variant of the classic least-recently-used (LRU) cache. In the classic version, the capacity limits the **number** of items stored. In this variant, every item carries a positive integer **quantity**, and the capacity limits the **total quantity** across all stored items -- an item with quantity 3 consumes 3 units of capacity, not 1. All other behavior (recency tracking, eviction order) is identical to a standard LRU cache.
Implement the class `WeightedLRUCache`:
- `WeightedLRUCache(int capacity)` -- initializes the cache with a positive integer `capacity`, the maximum total quantity the cache may hold at any time.
- `int get(int key)` -- if `key` exists in the cache, returns its value and marks the key as the most recently used; otherwise returns `-1`.
- `void put(int key, int value, int quantity)` -- inserts or updates an entry: (1) if `key` already exists, overwrite its value and quantity and mark it most recently used; (2) otherwise insert `key` as most recently used; (3) afterwards, while the sum of quantities of all stored items exceeds `capacity`, evict the least recently used item.
An evicted key is removed entirely; a later `get` on it returns `-1` (and a later `put` re-inserts it as a fresh entry).
### How this console runs your code
You implement the `WeightedLRUCache` class. A fixed `solution(operations, values)` driver replays a sequence of calls: `operations[i]` is the method name (`"WeightedLRUCache"`, `"get"`, or `"put"`) and `values[i]` is its argument list. The driver returns one entry per call -- `null` for the constructor and for `put`, and the returned value for `get` -- matching the standard operation-log format.
### Example
```
operations = ["WeightedLRUCache", "put", "put", "get", "put", "get", "get"]
values = [[5], [1, 10, 2], [2, 20, 2], [1], [3, 30, 3], [2], [1]]
output = [null, null, null, 10, null, -1, 10]
```
Explanation (capacity = 5): put(1,10,2) -> {1} total 2; put(2,20,2) -> {1,2} total 4; get(1) -> 10 and makes key 1 most recently used (key 2 now LRU); put(3,30,3) -> total would be 7 > 5, so the LRU key 2 is evicted, leaving {1,3} total 5; get(2) -> -1 (evicted); get(1) -> 10.
Constraints
- 1 <= capacity <= 10^9
- 1 <= quantity <= capacity for every put call
- 0 <= key, value <= 10^9
- At most 2 * 10^5 calls will be made to get and put combined
- get and put must run in average O(1) time
Examples
Input: (["WeightedLRUCache", "put", "put", "get", "put", "get", "get"], [[5], [1, 10, 2], [2, 20, 2], [1], [3, 30, 3], [2], [1]])
Expected Output: [None, None, None, 10, None, -1, 10]
Explanation: Spec example (capacity 5). get(1) makes key 1 most recently used; put(3,30,3) pushes total to 7>5 so the LRU key 2 is evicted; get(2) is then -1 and get(1) is 10.
Input: (["WeightedLRUCache", "put", "put", "put", "get", "get"], [[5], [1, 10, 2], [2, 20, 2], [1, 15, 4], [2], [1]])
Expected Output: [None, None, None, None, -1, 15]
Explanation: Updating an existing key changes its quantity: put(1,15,4) overwrites key 1 (total 2+2-2+4=6>5) and marks it most recently used, so the LRU key 2 is evicted. get(2)=-1, get(1)=15 (new value).
Hints
- Combine a hash map (O(1) key lookup) with a doubly linked list, or use an OrderedDict, to track recency order in O(1).
- Store each entry's quantity next to its value and keep a running total of all stored quantities, so the over-capacity check is O(1) instead of summing every time.
- On put of a key that already exists, subtract its OLD quantity from the running total before adding the new quantity.
- After inserting, evict from the least-recently-used end while total > capacity. Because 1 <= quantity <= capacity, the item you just inserted can never be the one evicted, so the loop always terminates leaving it in place.