Implement an LRU cache with constant-time lookup, recency updates, and eviction, including existing-key updates, zero capacity, and concurrency pitfalls.
Implement a cache of fixed capacity with `get(key)` and `put(key, value)`. A successful get and any insertion or update make that key most recently used. When inserting a new key into a full cache, evict the least recently used key. Return `-1` for a missing key.
### Constraints & Assumptions
Use the standard LRU formulation. Capacity is nonnegative; a zero-capacity cache stores nothing. Target average O(1) time per operation.
### Clarifying Questions to Ask
- Does updating an existing key refresh its recency?
- Can a stored value be `-1`, and would a distinct missing-value result be preferable in a production interface?
```hint Two forms of access
You need both direct key lookup and constant-time movement within a recency order.
```
### What a Strong Answer Covers
- A hash index paired with a mutable recency order.
- Existing-key updates, hit promotion, and eviction of the correct endpoint.
- Consistent removal from both structures and behavior at capacity zero.
### Follow-up Questions
- How would concurrent gets and puts preserve a single recency order?
- How would time-based expiration interact with least-recently-used eviction?
Overview: Implement an LRU cache with constant-time lookup, recency updates, and eviction, including existing-key updates, zero capacity, and concurrency pitfalls.
Implement a cache of fixed capacity with get(key) and put(key, value). A successful get and any insertion or update make that key most recently used. When inserting a new key into a full cache, evict the least recently used key. Return -1 for a missing key.
Constraints & Assumptions
Use the standard LRU formulation. Capacity is nonnegative; a zero-capacity cache stores nothing. Target average O(1) time per operation.
Clarifying Questions to Ask Guidance
Does updating an existing key refresh its recency?
Can a stored value be
-1
, and would a distinct missing-value result be preferable in a production interface?
What a Strong Answer Covers Guidance
A hash index paired with a mutable recency order.
Existing-key updates, hit promotion, and eviction of the correct endpoint.
Consistent removal from both structures and behavior at capacity zero.
Follow-up Questions Guidance
How would concurrent gets and puts preserve a single recency order?
How would time-based expiration interact with least-recently-used eviction?