Fixed-Capacity Least-Recently-Used Cache Driven by Get and Put Operations
Company: Waymo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Design a least-recently-used (LRU) cache. In the interview this was an object-oriented design round: design a cache class with a fixed capacity that supports reading a key and writing a key-value pair, evicting the least recently used entry when it is full. Both operations should run in O(1) average time.
For this console version, the cache is driven by a list of operations and you return the results of the reads.
### Function Signature
```python
def run_lru_cache(capacity: int, operations: list[str], arguments: list[list[int]]) -> list[int]:
```
### Rules
- Start with an empty cache that holds at most `capacity` entries. Process `operations[i]` with `arguments[i]`, in order.
- `"get"` with arguments `[key]`: if `key` is in the cache, the result is its value and the entry becomes the most recently used. Otherwise the result is `-1` and the cache is unchanged.
- `"put"` with arguments `[key, value]`: if `key` is already in the cache, replace its value and make it the most recently used; nothing is evicted. Otherwise, if the cache already holds `capacity` entries, first remove the least recently used entry, then insert the new entry as the most recently used.
- An entry's recency is updated by every successful `get` and every `put` of its key.
- Return the results of all `"get"` operations, in order.
### Constraints
- `1 <= capacity <= 10^4`
- `1 <= len(operations) == len(arguments) <= 2 * 10^5`
- Each operation is `"get"` or `"put"`.
- `0 <= key <= 10^9` and `0 <= value <= 10^9`.
### Examples
**Example 1**
- Input: `capacity = 2`, `operations = ["put", "put", "get", "put", "get", "get", "put", "get", "get"]`, `arguments = [[1, 10], [2, 20], [1], [3, 30], [2], [3], [1, 11], [1], [3]]`
- Output: `[10, -1, 30, 11, 30]`
- Explanation: Reading key 1 makes key 2 the least recently used, so inserting key 3 evicts key 2. Writing key 1 again updates its value without evicting anything.
**Example 2**
- Input: `capacity = 2`, `operations = ["put", "put", "put", "get", "put", "get", "get"]`, `arguments = [[4, 1], [5, 2], [4, 3], [5], [6, 4], [4], [5]]`
- Output: `[2, -1, 2]`
- Explanation: Updating key 4 makes it the most recently used, but reading key 5 afterwards makes key 4 the least recently used again, so inserting key 6 evicts key 4.
**Example 3**
- Input: `capacity = 1`, `operations = ["get", "put", "put", "get", "get"]`, `arguments = [[5], [5, 7], [6, 8], [5], [6]]`
- Output: `[-1, -1, 8]`
Overview: Design a fixed-capacity least-recently-used cache as an object-oriented exercise, driven here by a list of get and put operations whose read results you return. Tests O(1) lookup, recency updates on reads and writes, and correct eviction order.