Hash Map with TTL
Nike, Inc.● MediumFULLTIMEONSITE INTERVIEWProblem statement
Implement a map whose entries expire after a time to live (TTL). The map starts empty. Process operations in input order and return the result of every get operation, in that order.
Each operation is a row [action, time, key, value, ttl]:
action = 0puts the value at the key and replaces any earlier entry. It expires attime + ttl.action = 1gets the key. The value and TTL fields are both0. Return the stored value if the latest entry has not expired, or-1if the key is absent.
An entry is valid only while the current time is strictly less than its expiration time. A TTL of zero expires immediately. Overwriting a key replaces both its value and its expiration time; an older value never returns after the new entry expires. Equal timestamps still follow input order.
Function
runTtlMap(operations: int[][]) → int[]Examples
Example 1
operations = [[0,2,7,40,3],[1,4,7,0,0],[1,5,7,0,0],[0,5,7,9,0],[1,5,7,0,0]]return = [40,-1,-1]The first entry expires at time 5, so it is available at time 4 and absent at time 5. The later put has zero TTL and is already expired when the final get runs.
Example 2
operations = [[0,1,3,10,10],[0,2,3,20,1],[1,3,3,0,0]]return = [-1]The second put replaces the first entry and expires at time 3. Its expiration does not restore the older value.
Constraints
0 <= operations.length <= 1000.- Each operation has exactly
5integers. - Every integer in
operationsis between-10^9and10^9. - Actions are
0or1. Times are non-negative and nondecreasing. Put values and TTLs are non-negative. Get operations have zero in their last two fields.