TTL Cache with LRU Eviction

NetflixPhone screenMedium

Design an in-memory cache keyed by strings, holding integer values. Every method takes the current timestamp at as its first argument, and timestamps never decrease between calls. Each test drives one TTLCache(capacity) instance through a sequence of calls and records every call's return value (None for methods that return nothing).

Part 1: Entries that expire

Design a cache where each entry lives for a limited time. The capacity is given but this part never fills the cache, so eviction is not needed yet.

put(at, key, value, ttl) stores value under key. The entry is live at every timestamp t with at <= t < at + ttl, and expired from at + ttl onward. Writing over a live entry replaces both its value and its ttl.
get(at, key) returns the value of the live entry for key, or None if there is none.
count(at) returns how many entries are live at at.

An expired entry must behave as if it was never written.

Example 1

init: [1000]
operations: [["put",[1,"a",10,5]],["get",[2,"a"]],["get",[5,"a"]],["get",[6,"a"]],["count",[6]],["put",[7,"b",0,3]],["get",[8,"b"]],["put",[9,"b",7,1]],["get",[9,"b"]],["get",[10,"b"]],["count",[10]]]
Output: [null,10,10,null,0,null,0,null,7,null,0]

Why: a is stored at time 1 with ttl 5, so it is live through time 5 and expired at 6. b is stored at 7, replaced at 9 with a one-unit ttl, readable at 9 and gone at 10. count sees only live entries.

Constraints

1 <= len(operations) <= 10^4
1 <= capacity <= 10^4
1 <= len(key) <= 10
'a' <= key[i] <= 'z'
-10^9 <= value <= 10^9
1 <= ttl <= 10^9
0 <= at <= 10^9, and at never decreases between calls