Time Based Key-Value Store

Build a key-value store that remembers the history of every key. Each write is stamped with a time, and a read asks what a key held at a given moment. Implement the TimeMap class:

• TimeMap() creates an empty store.
• set(key, value, timestamp) records that key was given value at time timestamp.
• get(key, timestamp) returns the value from the latest set on key whose timestamp is at most timestamp. If there is no such set, because key was never written or was only written later, it returns the empty string "".

Each example lists the calls in order, then the arguments of each call, then what each call returns: null for the constructor and for set, which returns nothing.

Example 1

Input:
["TimeMap", "set", "set", "get", "get", "get", "get"]
[[], ["lamp", "off", 2], ["lamp", "on", 6], ["lamp", 2], ["lamp", 5], ["lamp", 9], ["lamp", 1]]
Output: [null, null, null, "off", "off", "on", ""]

At time 2 the lamp was set to "off", and nothing changed until time 6, so times 2 and 5 both read "off". Time 9 reads the later write, "on". At time 1 the lamp had not been written yet, so the answer is "".

Example 2

Input:
["TimeMap", "set", "set", "get", "get", "set", "get", "get"]
[[], ["a1", "x", 3], ["b2", "y", 4], ["b2", 3], ["a1", 4], ["a1", "z", 8], ["a1", 7], ["c3", 10]]
Output: [null, null, null, "", "x", null, "x", ""]

Each key has its own history. "b2" was first written at time 4, so reading it at 3 gives "". "a1" read at 7 still gives "x", because the write of "z" comes later, at 8. "c3" was never written.

Constraints

• 1 <= key.length, value.length <= 100
• key and value consist of lowercase English letters and digits.
• 1 <= timestamp <= 10⁷
• The timestamps passed to set strictly increase from one set call to the next.
• At most 2 * 10⁵ calls are made in total to set and get.