Versioned Key-Value Store

Implement a key-value store that keeps every version of each key. Each version is stored with a timestamp, and a lookup asks for the value a key had at a given time.

Implement the class TimeMap:

• TimeMap() creates an empty store.
• set(key, value, timestamp) stores value as the version of key at time timestamp.
• get(key, timestamp) returns the value of the latest version of key whose time is at most timestamp. If key has no version at or before timestamp, it returns the empty string "".

You can assume the timestamps of the set calls are strictly increasing, across all keys. The timestamps of get calls can be anything in range, in any order.

How Your Class Is Run

The provided run function creates the store and applies each operation; your code only needs the class.

run receives four lists of the same length: ops, keys, values, and times. Operation i is ops[i], which is "set" or "get":

• For "set", run calls set(keys[i], values[i], times[i]).
• For "get", run calls get(keys[i], times[i]). Here values[i] is "" and is ignored.

run returns the result of every get, in order. A set adds nothing to the result.

Examples

Example 1

Input: ops = ["set","get","get","set","get","get"], keys = ["foo","foo","foo","foo","foo","foo"], values = ["bar","","","bar2","",""], times = [1,1,3,4,4,5]
Output: ["bar","bar","bar2","bar2"]
Explanation: At times 1 and 3 the latest version of "foo" is "bar", stored at time 1.
The version "bar2" is stored at time 4, so get("foo", 4) and get("foo", 5) return "bar2".

Example 2

Input: ops = ["set","get","get","set","set","get","get","get"], keys = ["a","a","b","b","a","a","a","b"], values = ["x","","","y","z","","",""], times = [5,4,10,7,9,8,9,6]
Output: ["","","x","z",""]
Explanation: get("a", 4) asks for a time before the first version of "a", so it returns "". Key "b" has no version yet at the second get.
At time 8 the latest version of "a" is "x" (time 5), and at time 9 it is "z". The only version of "b" is at time 7, so get("b", 6) returns "".