Implement an LRU Cache
Company: Gimlet Labs
Role: Member of Technical Staff, ML Systems
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Problem
Implement a fixed-capacity least-recently-used cache supporting `get(key)` and
`put(key, value)`. `get` returns the stored value or `-1` when absent and marks a
hit as most recently used. `put` inserts or updates a key, marks it most recent,
and evicts the least-recently-used key when capacity would be exceeded. Process a
sequence of operations and return the results of all `get` operations.
### Constraints & Assumptions
- Capacity is between 1 and 100,000.
- There are at most 200,000 operations.
- Keys and values are 32-bit signed integers; stored values are never `-1`.
- Both operations should run in expected constant time.
### Clarifications
- Updating an existing key changes its value and recency without changing cache size.
- A cache miss does not affect recency.
- Exactly one key is evicted when a new insertion exceeds capacity.
### Examples
```text
capacity = 2
operations = [put(1,1), put(2,2), get(1), put(3,3), get(2)]
get results = [1, -1]
```
### Hints
```hint Separate lookup and order
One structure can find a key quickly while another maintains recency under removals and moves.
```
```hint Make moves constant time
Store direct references to recency nodes rather than searching the order structure.
```
Overview: Implement an LRU cache with expected constant-time reads, writes, recency updates, and eviction by combining direct key lookup with a movable ordering structure.
Process a fresh fixed-capacity least-recently-used cache. Operations are ["get", key] and ["put", key, value]. Get returns the stored value or -1 when absent; a hit becomes most recently used and a miss does not change recency. Put inserts or updates a key, makes it most recent, and evicts exactly the least-recently-used key when a new insertion exceeds capacity. Return only get results in operation order.
Constraints
- 1 <= capacity <= 100000.
- operations contains at most 200000 encoded get or put lists.
- Keys and values are signed 32-bit integers.
- Stored values are never -1.
- A cache miss does not affect recency.
- Updating an existing key changes its value and recency without changing cache size.
- Each get and put runs in expected O(1) time.
Examples
Input: (2, [['put', 1, 1], ['put', 2, 2], ['get', 1], ['put', 3, 3], ['get', 2]])
Expected Output: [1, -1]
Explanation: This is the source example; get(1) promotes key 1, so key 2 is evicted.
Input: (3, [])
Expected Output: []
Explanation: No get operations produce an empty result.
Hints
- Keep key lookup separate from the recency order.
- Store direct references or iterators so hits and updates can move entries without searching.