Capacity-Limited Timed Cache

Implement a key-value cache with a fixed positive capacity. Every entry has its own expiration time, and the cache processes operations whose timestamps are nondecreasing.
Each row in operations has one of these forms:
[0, key, value, ttl, timestamp] is a PUT. It creates or replaces key with value. The entry expires at timestamp + ttl. A successful PUT sets the entry's age to this timestamp.
[1, key, timestamp] is a GET. It returns the current value for key, or -1 when the key is absent or expired. A GET does not change an entry's age.
Before processing every operation, remove all entries whose expiration time is less than or equal to the operation's timestamp. When a PUT inserts a new key and the cache still contains capacity live entries, evict the live entry with the smallest most-recent PUT timestamp. If several live entries have that same timestamp, evict the one with the smaller key. Replacing an existing live key refreshes its value, expiration time, and age without evicting another entry.
Return the results of the GET operations in encounter order. PUT operations do not add a result.

Function
runCapacityTimedCache(capacity: int, operations: int[][]) → int[]

Examples
Example 1
capacity = 2
operations = [[0,1,10,10,0],[0,2,20,10,1],[1,1,2],[0,3,30,10,3],[1,1,3],[1,2,3],[1,3,3]]
return = [10,-1,20,30]
The cache is full when key 3 is inserted at time 3. Key 1 has the oldest live PUT timestamp, so it is evicted. Keys 2 and 3 remain available.
Example 2
capacity = 2
operations = [[0,1,10,2,0],[0,2,20,10,0],[0,3,30,10,2],[1,1,2],[1,2,2],[1,3,2]]
return = [-1,20,30]
Key 1 expires exactly at time 2 and is removed before key 3 is inserted. The expired entry frees capacity, so no live key is evicted.
Example 3
capacity = 2
operations = [[0,2,20,10,0],[0,1,10,10,0],[0,3,30,10,0],[1,1,0],[1,2,0],[1,3,0]]
return = [-1,20,30]
Keys 1 and 2 have equal age when key 3 arrives. The smaller key, 1, is evicted by the tie rule.

Constraints
1 <= capacity <= 100000.
1 <= operations.length <= 200000, and at least one operation is a GET.
Every PUT row is [0, key, value, ttl, timestamp].
Every GET row is [1, key, timestamp].
0 <= key, value, timestamp <= 10^9.
1 <= ttl <= 10^9.
Operation timestamps are nondecreasing.
Expiration times fit a signed 64-bit integer.

Keep a hash map from key to (value, expiry, age). Add a min-heap on (expiry, key) and a second ordered set, or heap, on (age, key). Before each operation, pop from the expiry heap while expiry <= timestamp and delete those entries from the map and the age structure. The pitfall is stale data. A replaced key leaves old records behind, so use lazy deletion: when you pop a record, check it still matches the map's current expiry or age, otherwise skip it. Same check when evicting from the age heap. Also remember GET never changes age, so no refresh there. Replacing a live key evicts nothing. Expiry uses <=, so an entry with expiry equal to the timestamp is already dead. Total cost is O(n log n), fine for 200000 operations. StealthCoder covers you on the live OA if the lazy-deletion details slip.

Memorize the pattern. If you can't, run StealthCoder. The proctor sees the IDE. They don't see what's behind it.