Design a time-based key-value store that stores multiple values for the same key at different timestamps and retrieves the key's value at a certain timestamp.
Implement the TimeMap class:
TimeMap() - initializes the data structure.set(key, value, timestamp) - stores the key with the value at the given timestamp. Timestamps are strictly increasing across all calls to set.get(key, timestamp) - returns a value such that set(key, value, t) was called previously, with t <= timestamp, and t is as large as possible. If no such value exists, return "".Input:
set("foo", "bar", 1)
get("foo", 1)
get("foo", 3)
set("foo", "bar2", 4)
get("foo", 4)
get("foo", 5)
Output: [null, "bar", "bar", null, "bar2", "bar2"]
Explanation: At t=1, "foo" -> "bar". At t=3, the most recent set at or before 3 is t=1, so return "bar". At t=4, "foo" -> "bar2". At t=5, the most recent set at or before 5 is t=4, so return "bar2".
Input:
set("love", "high", 10)
set("love", "low", 20)
get("love", 5)
get("love", 10)
get("love", 15)
get("love", 20)
Output: [null, null, "", "high", "high", "low"]
Explanation: No value was stored at or before t=5, so return "". At t=10, return "high". At t=15, the most recent at or before 15 is t=10, so return "high". At t=20, return "low".
set are strictly increasing.set and get.set("foo", "bar", 1); get("foo", 1)