Problem · Design
Expiring Key Set
Learn this problem● Hard
AmazonNEW GRADONSITE INTERVIEW
See Amazon hiring insightsAmazonNEW GRADONSITE INTERVIEWProblem statement
Simulate a set of string keys over time. The aligned arrays describe operations in nondecreasing timestamp order:
add: insert or refreshkeys[i]. It expires attimestamps[i] + ttl[i].contains: append whetherkeys[i]is currently present.remove: deletekeys[i]immediately if present.
At the start of every operation, delete entries whose expiration time is less than or equal to the current timestamp. For non-add operations, ttl[i] is zero. Return the answers to contains operations in encounter order.
Function
runExpiringSet(operations: String[], keys: String[], timestamps: int[], ttl: int[]) → boolean[]Examples
Example 1
operations = ["add","contains","contains"]keys = ["a","a","a"]timestamps = [0,4,5]ttl = [5,0,0]return = [true,false]The key is present before time 5 and absent exactly at its expiration time.
Example 2
operations = ["add","add","contains","contains"]keys = ["job","job","job","job"]timestamps = [0,2,3,7]ttl = [3,5,0,0]return = [true,false]Refreshing at time 2 replaces expiration 3 with expiration 7.
Example 3
operations = ["add","contains","remove","contains"]keys = ["x","x","x","x"]timestamps = [1,2,3,3]ttl = [10,0,0,0]return = [true,false]Removal takes effect for a later operation at the same timestamp.
Constraints
1 <= operations.length = keys.length = timestamps.length = ttl.length <= 100000.- Operations are
add,contains, orremove. - Keys are nonempty alphanumeric strings of length at most
40. 0 <= timestamps[i] <= 2 * 10^9and timestamps are nondecreasing.- For add,
1 <= ttl[i] <= 10^9; otherwisettl[i] == 0.