Simulate a Least-Recently-Used Cache over Get and Put Operations
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A cache holds key-value pairs up to a fixed capacity. When it is full and a new key must be added, it evicts the key that was used least recently. Simulate such a cache over a sequence of `get` and `put` operations and return the result of every `get`.
### Function Signature
```python
def simulate_lru_cache(capacity: int, operations: list[str], arguments: list[list[int]]) -> list[int]:
```
### Rules
- The cache starts empty and never holds more than `capacity` keys.
- `operations[i]` is `"get"` or `"put"`, and `arguments[i]` holds that operation's arguments.
- `"get"` with `[key]`: if `key` is in the cache, the result is its value and `key` becomes the most recently used key. Otherwise the result is `-1` and nothing changes.
- `"put"` with `[key, value]`: if `key` is in the cache, replace its value and make it the most recently used key. Otherwise, if the cache already holds `capacity` keys, first evict the least recently used key, then insert `key` with `value` as the most recently used key. A `put` produces no result.
- A key's recency is set by its latest successful `get` or its latest `put`.
- Return one integer per `"get"`, in the order the operations appear.
- The intended solution handles every operation in O(1) average time.
### Constraints
- `1 <= capacity <= 3000`
- `1 <= len(operations) == len(arguments) <= 2 * 10^5`
- `arguments[i]` has length 1 when `operations[i]` is `"get"` and length 2 when it is `"put"`.
- `0 <= key <= 10^4`
- `0 <= value <= 10^9`, so a stored value is never `-1`, and every number fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: capacity = 2
operations = ["put", "put", "get", "put", "get", "get", "get"]
arguments = [[5, 50], [7, 70], [5], [9, 90], [7], [5], [9]]
Output: [50, -1, 50, 90]
```
Reading key `5` makes key `7` the least recently used key, so `put 9` evicts key `7`.
**Example 2**
```text
Input: capacity = 2
operations = ["put", "put", "put", "put", "get", "get", "get"]
arguments = [[1, 10], [2, 20], [1, 15], [3, 30], [1], [2], [3]]
Output: [15, -1, 30]
```
The third operation replaces key `1`'s value with `15` and makes it the most recently used key, so `put 3` evicts key `2`.
**Example 3**
```text
Input: capacity = 1
operations = ["get", "put", "get", "put", "get", "get"]
arguments = [[4], [4, 0], [4], [6, 1], [4], [6]]
Output: [-1, 0, -1, 1]
```
A stored value can be `0`. With capacity `1`, inserting key `6` evicts key `4`.
Overview: A coding problem that simulates a fixed-capacity least-recently-used cache over a sequence of get and put operations and returns the result of every get. It tests exact recency rules for reads, updates and evictions, and an implementation that handles each operation in constant average time.