Process LRU Cache Operations
Company: TikTok
Role: Backend Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Process LRU Cache Operations
Implement `process_lru(capacity, operations)` for a least recently used cache with integer keys and values.
Each operation is one of the following strings:
- `"PUT key value"`: insert or update `key`. A successful update makes the key most recently used. If insertion makes the cache exceed `capacity`, evict the least recently used key.
- `"GET key"`: append the stored value to the result, or append `-1` if the key is absent. A successful lookup makes the key most recently used; a miss does not change recency.
Return the list of results from `GET` operations in their original order. This operation grammar is a pedagogical assumption that makes the named cache-design exercise deterministic.
## Function Contract
`process_lru(capacity: int, operations: list[str]) -> list[int]`
## Constraints
- `1 <= capacity <= 100000`
- `0 <= len(operations) <= 200000`
- Keys and values are integers in the inclusive range `[-10^9, 10^9]`.
- Every operation follows one of the two formats above.
## Examples
### Example 1
```text
Input:
capacity = 2
operations = ["PUT 1 10", "PUT 2 20", "GET 1", "PUT 3 30", "GET 2", "GET 3"]
Output: [10, -1, 30]
```
The lookup of key `1` makes key `2` least recently used, so inserting key `3` evicts key `2`.
### Example 2
```text
Input:
capacity = 1
operations = ["PUT 7 4", "PUT 7 9", "GET 7", "PUT 8 5", "GET 7", "GET 8"]
Output: [9, -1, 5]
```
Updating key `7` replaces its value without creating a second entry. Inserting key `8` later evicts it.
Overview: Implement an LRU cache through a deterministic stream of put and get operations, including updates, misses, and eviction order. The prompt defines an exact portable function contract and examples suitable for a later four-language console handoff.
Read the full TikTok Backend Software Engineer interview experience this question came from
Implement process_lru(capacity, operations) for a least recently used cache with integer keys and values. Each operation is a string in exactly one of two forms: "PUT key value" inserts or updates a key, makes it most recently used, and evicts the least recently used key if a new insertion exceeds capacity; "GET key" appends the value or -1 for a miss, with only a successful lookup changing recency. Return GET results in operation order. This string grammar is the source's explicit pedagogical assumption.
Constraints
- 1 <= capacity <= 100,000
- 0 <= operations.length <= 200,000
- Every operation is exactly "PUT key value" or "GET key".
- Keys and values are integers in [-10^9, 10^9].
- A PUT update and a successful GET make their key most recently used.
- A missing GET appends -1 and does not change recency.
Examples
Input: (2, ['PUT 1 10', 'PUT 2 20', 'GET 1', 'PUT 3 30', 'GET 2', 'GET 3'])
Expected Output: [10, -1, 30]
Explanation: The first source example makes key one recent before inserting key three.
Input: (1, ['PUT 7 4', 'PUT 7 9', 'GET 7', 'PUT 8 5', 'GET 7', 'GET 8'])
Expected Output: [9, -1, 5]
Explanation: The second source example updates at capacity one and then evicts the key.
Hints
- Pair a hash table with an order structure that supports moving a known key to the newest end.
- A miss must leave the order untouched; an update must move its existing key without growing the cache.