Time Based Key-Value Store

A time-based key-value store keeps every value a key has ever had, each with the time it was set. You can then ask what a key's value was at any moment: the value that was set most recently at or before that moment.

Implement the class TimeMap:

• TimeMap() creates an empty store.
• set(key, value, timestamp) stores the string value for the string key at the time timestamp. The key's earlier values are kept.
• get(key, timestamp) returns the value that was set for key with the largest timestamp that is still <= timestamp. If no value was set for key at or before timestamp, or key was never set at all, it returns the empty string "".

The input is a list of operations, applied in order to one new TimeMap. The output lists what the get calls return, in order; an empty string is shown as "". The starter code spells these names the way your language does.

Example 1:

Input:
    set("foo", "bar", 1)
    get("foo", 1)
    get("foo", 3)
    set("foo", "bar2", 4)
    get("foo", 4)
    get("foo", 5)
Output: bar bar bar2 bar2
Explanation:
At time 1, "foo" was set to "bar", so get("foo", 1) is "bar".
Nothing was set for "foo" between 1 and 3, so at time 3 the value is still "bar".
At time 4, "foo" was set to "bar2": from then on, get returns "bar2", at time 4 and at time 5.

Example 2:

Input:
    set("love", "high", 10)
    set("love", "low", 20)
    get("love", 5)
    get("love", 10)
    get("love", 15)
    get("love", 20)
    get("love", 25)
    get("hate", 25)
Output: "" high high low low ""
Explanation:
At time 5, "love" had no value yet, so the answer is the empty string.
At times 10 and 15 the latest value is "high"; at 20 and 25 it is "low".
"hate" was never set, so its answer is the empty string too.

Example 3:

Input:
    set("a", "x", 1)
    set("b", "y", 2)
    set("a", "z", 3)
    get("a", 2)
    get("b", 1)
    get("b", 2)
    get("a", 3)
Output: x "" y z
Explanation: Each key keeps its own values. At time 2, "a" still has "x": "z" comes only at time 3. "b" gets its first value at time 2, so at time 1 it has none.

Constraints:

• 1 <= key.length, value.length <= 20
• key and value consist of lowercase English letters and digits.
• 1 <= timestamp <= 107
• The timestamps of the set calls are strictly increasing: each set has a larger timestamp than every set before it.
• At most 105 calls in total are made to set and get.