Simulate a Fixed-Capacity Least-Recently-Used Cache over a Stream of Operations
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a key-value cache that holds at most `capacity` entries and, when it is full, evicts the entry that was used least recently. Run the cache over a list of operations and return the results of the lookups.
### Function Signature
```python
def run_lru_cache(capacity: int, operations: list[tuple[str, int, int]]) -> list[int]:
```
Each operation is a tuple `(op, key, value)`:
- `("get", key, 0)` looks up `key`. The third field is unused and is always `0`.
- `("put", key, value)` stores `value` under `key`.
### Rules
- The cache starts empty.
- `get`: if `key` is in the cache, the result is its value and the entry becomes the most recently used one. Otherwise the result is `-1` and the cache does not change.
- `put` of a key that is already in the cache replaces its value and makes the entry the most recently used one; nothing is evicted.
- `put` of a new key adds it as the most recently used entry. If the cache already holds `capacity` entries, first evict the least recently used entry, then add the new one.
- An entry's recency is the time of its latest successful `get` or of the latest `put` of its key.
- Return one integer per `get`, in the order the `get` operations appear. Return an empty list if there are none.
- Aim for O(1) average time per operation.
### Constraints
- `1 <= capacity <= 10^5`
- `1 <= len(operations) <= 2 * 10^5`
- `0 <= key <= 10^9`
- `0 <= value <= 10^9`, so `-1` never collides with a stored value.
### Examples
**Example 1**
```text
Input: capacity = 2
operations = [("put", 1, 10), ("put", 2, 20), ("get", 1, 0), ("put", 3, 30),
("get", 2, 0), ("get", 3, 0), ("get", 1, 0)]
Output: [10, -1, 30, 10]
```
After the two puts, key 1 is the least recently used. `get(1)` returns 10 and makes key 2 the least recently used, so `put(3)` evicts key 2. The later lookups return -1 for key 2, then 30 and 10.
**Example 2**
```text
Input: capacity = 2
operations = [("put", 1, 1), ("put", 2, 2), ("put", 1, 5), ("put", 3, 3),
("get", 1, 0), ("get", 2, 0), ("get", 3, 0)]
Output: [5, -1, 3]
```
`put(1, 5)` updates key 1 without evicting anything and makes it the most recently used, so `put(3)` evicts key 2.
**Example 3**
```text
Input: capacity = 1
operations = [("get", 7, 0), ("put", 7, 70), ("put", 8, 80), ("get", 7, 0), ("get", 8, 0)]
Output: [-1, -1, 80]
```
The first lookup misses on an empty cache. With room for one entry, `put(8)` evicts key 7.
Overview: A coding question that asks you to implement a fixed-capacity key-value cache with least-recently-used eviction and run it over a stream of get and put operations. It tests precise recency and eviction rules, updates to keys already in the cache, and the design of a data structure with constant-time operations.
Read the full Apple Software Engineer interview experience this question came from
Implement a key-value cache that holds at most `capacity` entries and, when it is full, evicts the entry that was used least recently. Run the cache over a list of operations and return the results of the lookups.
Implement `run_lru_cache(capacity, operations)`. Each operation is a triple `(op, key, value)`:
- `("get", key, 0)` looks up `key`. The third field is unused and is always `0`.
- `("put", key, value)` stores `value` under `key`.
### Rules
- The cache starts empty.
- `get`: if `key` is in the cache, the result is its value and the entry becomes the most recently used one. Otherwise the result is `-1` and the cache does not change.
- `put` of a key that is already in the cache replaces its value and makes the entry the most recently used one; nothing is evicted.
- `put` of a new key adds it as the most recently used entry. If the cache already holds `capacity` entries, first evict the least recently used entry, then add the new one.
- An entry's recency is the time of its latest successful `get` or of the latest `put` of its key.
- Return one integer per `get`, in the order the `get` operations appear. Return an empty list if there are none.
- Aim for O(1) average time per operation.
Each operation is passed as a three-element sequence: a Python tuple, a JavaScript array `[op, key, value]`, a Java `java.util.List<Object>` holding a `String` followed by two numbers, or a C++ `std::tuple<std::string, int, int>`.
### Constraints
- `1 <= capacity <= 10^5`
- `1 <= len(operations) <= 2 * 10^5`
- Every operation is either `("get", key, 0)` or `("put", key, value)`.
- `0 <= key <= 10^9`
- `0 <= value <= 10^9`, so `-1` never collides with a stored value.
- Every key, value and result fits in a signed 32-bit integer; no value exceeds 2^31 - 1.
### Example 1
```text
Input: capacity = 2
operations = [("put", 1, 10), ("put", 2, 20), ("get", 1, 0), ("put", 3, 30),
("get", 2, 0), ("get", 3, 0), ("get", 1, 0)]
Output: [10, -1, 30, 10]
```
After the two puts, key 1 is the least recently used. `get(1)` returns 10 and makes key 2 the least recently used, so `put(3)` evicts key 2. The later lookups return -1 for key 2, then 30 and 10.
### Example 2
```text
Input: capacity = 2
operations = [("put", 1, 1), ("put", 2, 2), ("put", 1, 5), ("put", 3, 3),
("get", 1, 0), ("get", 2, 0), ("get", 3, 0)]
Output: [5, -1, 3]
```
`put(1, 5)` updates key 1 without evicting anything and makes it the most recently used, so `put(3)` evicts key 2.
Constraints
- 1 <= capacity <= 10^5
- 1 <= len(operations) <= 2 * 10^5
- Each operation is either ("get", key, 0) or ("put", key, value)
- 0 <= key <= 10^9
- 0 <= value <= 10^9, so -1 never collides with a stored value
- Every key, value and result fits in a signed 32-bit integer
Examples
Input: (2, [('put', 1, 10), ('put', 2, 20), ('get', 1, 0), ('put', 3, 30), ('get', 2, 0), ('get', 3, 0), ('get', 1, 0)])
Expected Output: [10, -1, 30, 10]
Explanation: Source Example 1: get(1) refreshes key 1, so put(3) evicts key 2; the later get(2) misses.
Input: (2, [('put', 1, 1), ('put', 2, 2), ('put', 1, 5), ('put', 3, 3), ('get', 1, 0), ('get', 2, 0), ('get', 3, 0)])
Expected Output: [5, -1, 3]
Explanation: Source Example 2: put(1, 5) updates key 1 in place and refreshes it without evicting, so put(3) evicts key 2.
Hints
- Each operation needs two things quickly: the value currently stored under a key, and which stored entry has gone longest without a successful get or a put.
- Only a successful get or a put changes an entry's recency. A missed get changes nothing, and overwriting a key that is already stored never evicts.
- Eviction happens only when a key that is not already stored arrives while the cache already holds capacity entries.