Implement a cache that supports get(key) and put(key, value, ttl) in O(1) average time. The cache has a fixed capacity. When the capacity is full, evict the least recently used unexpired entry first. Each entry also expires ttl seconds after insertion; expired entries must not be returned and should be removed lazily during normal operations.
Return -1 from get(key) if the key is missing or expired. Assume a monotonic integer current_time is provided to each operation in non-decreasing order.
Example 1:
Input: capacity = 2
ops = [
put(1, 10, 5, 0),
put(2, 20, 3, 1),
get(1, 2),
get(2, 5),
put(3, 30, 10, 6),
get(1, 7)
]
Output: [None, None, 10, -1, None, -1]
Explanation: Key 2 expires at time 4, so it cannot be returned at time 5.
Example 2:
Input: capacity = 1
ops = [
put(1, 100, 2, 0),
put(2, 200, 10, 1),
get(1, 2),
get(2, 2)
]
Output: [None, None, -1, 200]
Explanation: Key 1 is evicted when key 2 is inserted because the cache is full.
1 <= capacity <= 10^51 <= number of operations <= 10^51 <= key <= 10^9-10^9 <= value <= 10^91 <= ttl <= 10^9current_time is non-decreasing across operationsget and put must run in average O(1) time
