Loading problem…
Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp. Implement the TimeMap class: - TimeMap() Initializes the object of the data structure. - void set(String key, String value, int timestamp) Stores the key with the value value at the given time timestamp. - String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns "".
Example 1
Input: operations = ["TimeMap","set","get","get","set","get","get"], arguments = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
Output: [null,null,"bar","bar",null,"bar2","bar2"]
Explanation: get("foo", 1) and get("foo", 3) both return "bar", the latest value set at or before those times. After "bar2" is set at time 4, get at 4 or 5 returns "bar2".
Example 2
Input: operations = ["TimeMap","set","set","get","get","get"], arguments = [[],["love","high",10],["love","low",20],["love",5],["love",10],["love",15]]
Output: [null,null,null,"","high","high"]
Explanation: At time 5 nothing has been set yet, so the result is "". At time 10 the value is "high". At time 15 the value is still "high", because "low" is not set until time 20.
Example 3
Input: operations = ["TimeMap","get","set","get"], arguments = [[],["a",1],["a","x",2],["a",2]]
Output: [null,"",null,"x"]
Explanation: The first get happens before any set, so it returns "". After "x" is set at time 2, get("a", 2) returns "x".
Because set is called with strictly increasing timestamps, each key's (timestamp, value) entries are naturally sorted. A get is then a binary search for the largest timestamp <= the query.
Run checks all cases above. Submit evaluates all test cases.