TTL Cache

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() 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.

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: []
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 <= 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

Practice this question

Import your own questions

Paste a question you were asked and get a full problem: statement, tests and a checked solution.

Import a question