Simulate a TTL Cache with LRU Eviction
Company: Netflix
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Simulate a TTL Cache with LRU Eviction
Implement a deterministic simulator for a cache that combines per-key expiration with a fixed-capacity least-recently-used policy.
~~~python
def run_cache(operations: list[list[object]], capacity: int) -> list[object]:
...
~~~
Each operation is one of these JSON-marshalable lists:
- ["put", time_ms, key, value, ttl_ms]
- ["get", time_ms, key]
- ["delete", time_ms, key]
- ["size", time_ms]
Keys are strings and values are integers. Times are nonnegative integers and are nondecreasing across the input. A positive TTL expires at time put_time + ttl_ms; an entry is expired when the operation time is greater than or equal to that deadline. A TTL of zero never expires.
Return one result per operation:
- put returns null;
- get returns the cached integer or null;
- delete returns true only when a currently live key was removed; and
- size returns the number of live keys.
Before each operation, expired entries are ineligible for reads, size, and eviction. A successful get makes its key most recently used. Putting either a new or existing key makes it most recently used. After a put, if the number of live keys exceeds capacity, evict the least recently used live key. If two accesses have the same timestamp, their order in operations breaks the tie.
## Constraints
- 1 <= capacity <= 100000
- 0 <= len(operations) <= 200000
- ttl_ms is nonnegative.
- A malformed operation, decreasing timestamp, unknown operation name, or invalid value type must raise ValueError.
- The returned list contains only JSON-marshalable values and is compared exactly.
## Example
~~~text
Input:
operations = [
["put", 0, "a", 10, 5],
["put", 1, "b", 20, 0],
["get", 2, "a"],
["put", 3, "c", 30, 0],
["get", 4, "b"],
["get", 5, "a"],
["size", 5]
]
capacity = 2
Output:
[null, null, 10, null, null, null, 1]
~~~
The put of c evicts b because the successful read of a refreshed a. At time 5, a expires, leaving only c.
## Hints
- Separate expiration validity from recency order.
- Decide how stale bookkeeping records can be recognized without changing visible behavior.
- Aim for logarithmic or constant amortized work per operation rather than scanning the whole cache.
Quick Answer: Simulate a fixed-capacity cache that combines per-key TTL expiration with LRU eviction. Process timestamped operations deterministically, distinguish live from expired entries, update recency correctly, and avoid scanning the entire cache on each request.
Simulate a fixed-capacity cache with per-entry expiration and least-recently-used eviction. Purge entries whose deadline is at or before each operation time, refresh recency on successful get and every put, and return one exact result per operation.
Constraints
- Capacity is between 1 and 100,000.
- Operation times are nonnegative and nondecreasing.
- A positive TTL expires at put_time + ttl; zero never expires.
- Keys are strings and values are non-Boolean integers.
- Malformed operations raise ValueError.
Examples
Input: {'operations':[['put',0,'a',10,5],['put',1,'b',20,0],['get',2,'a'],['put',3,'c',30,0],['get',4,'b'],['get',5,'a'],['size',5]],'capacity':2}
Expected Output: [None, None, 10, None, None, None, 1]
Explanation: The supplied sequence combines recency, eviction, and expiration.
Input: {'operations':[['put',0,'a',1,1],['put',1,'b',2,0],['size',1]],'capacity':1}
Expected Output: [None, None, 1]
Explanation: Expiration frees capacity before the next put.
Hints
- Use an ordered dictionary for live recency.
- Use a min-heap of expiration records tagged with entry versions so stale records are ignored.