Thread-Safe LRU Cache with TTL
Learn this problem
LinkedInFULLTIMEONSITE INTERVIEWProblem statement
Simulate a fixed-capacity least recently used cache whose entries also expire. You receive a capacity, parallel operation names, and integer argument rows. Process operations atomically in the supplied order.
PUTuses[time,key,value,ttl]. It stores or replaces the key, which expires attime + ttl, and makes the key most recent. Produce"null".GETuses[time,key]. Produce the stored value as a decimal string and make the key most recent, or produce"-1"when absent.
Times are nondecreasing. Before every operation, remove all keys whose expiration time is less than or equal to the current time. Remove expired keys before deciding whether a PUT needs LRU eviction. A non-positive capacity stores nothing.
Return one output string for every operation. The sequence represents a legal linearization of concurrent calls, so each operation must observe and update one complete cache state.
Function
runLRUWithTTL(capacity: int, operations: String[], arguments: int[][]) → String[]Examples
Example 1
capacity = 2operations = ["PUT","PUT","GET","PUT","GET","GET"]arguments = [[0,1,10,5],[1,2,20,10],[2,1],[6,3,30,5],[6,1],[7,2]]return = ["null","null","10","null","-1","20"]Key 1 expires at time 5, so it is removed before the PUT at time 6. Key 2 remains live.
Example 2
capacity = 1operations = ["PUT","PUT","GET","PUT","GET"]arguments = [[0,5,7,3],[2,5,9,10],[4,5],[5,6,1,10],[6,5]]return = ["null","null","9","null","-1"]The second PUT replaces key 5 and extends its TTL. Inserting key 6 later evicts key 5 from the capacity-one cache.
Constraints
-100000 <= capacity <= 100000.1 <= operations.length == arguments.length <= 100000.- Each operation is exactly
PUTorGETand has the stated argument count. -10^9 <= key, value <= 10^9.0 <= time <= 10^9, times are nondecreasing, and1 <= ttl <= 10^9.- The sum
time + ttlfits in a signed 64-bit integer.