#246MediumDesign· Versioned Map with Binary Search

Time-Based Key-Value Store

A configuration service keeps the full history of every setting. Each time a setting changes, the new value is stored together with the time of the change. Operators then ask questions such as "what was the value of this setting at time 42?". Design a class `TimeMap`: - `TimeMap()` creates an empty store. - `set(key, value, timestamp)` records that `key` has `value` from `timestamp` on. For one key, the timestamps of successive `set` calls are strictly increasing. - `get(key, timestamp)` returns the value that was stored with the **largest timestamp not greater than** the given one. If the key has no such record, return the empty string `""`.

Input format

`operations`: the method names in call order (the first is the constructor); `arguments`: the argument list of each call.

Output format

One value per operation: `null` for the constructor and for `set`, the value string for `get`.

Examples

Input: operations = ["TimeMap", "set", "get", "get", "set", "get", "get"], arguments = [[], ["mode", "eco", 1], ["mode", 1], ["mode", 3], ["mode", "turbo", 4], ["mode", 4], ["mode", 3]]

Output: [null, null, "eco", "eco", null, "turbo", "eco"]

At time 1 the mode becomes eco; at times 1 and 3 the latest change is eco. At time 4 it becomes turbo. A query for time 3 still sees eco because turbo was recorded later.

Input: operations = ["TimeMap", "get", "set", "get", "get"], arguments = [[], ["volume", 5], ["volume", "low", 10], ["volume", 9], ["brightness", 20]]

Output: [null, "", null, "", ""]

Querying a key that has never been set returns an empty string, and so does asking for a time before the first record (9 < 10).

Constraints

1 <= key.length, value.length <= 10
Keys and values consist of lowercase letters and digits
1 <= timestamp <= 10^7 for set; 0 <= timestamp <= 10^7 for get
At most 2 * 10^5 calls
Timestamps of set calls for the same key strictly increase

#design
#hash-table
#binary-search
#versioning