Time-Based Key-Value Store

Medium · binary search

A store remembers how the value of each key changed over time. It starts empty and receives a list of operations. For operation i, operations[i] is "set" or "get", and keys[i], values[i] and timestamps[i] are its arguments.

"set" records that key keys[i] had the value values[i] from time timestamps[i] on.
"get" asks for the value of the key keys[i] at time timestamps[i]: the value recorded with the latest timestamp that is not later than the asked time. If the key has no such record, the answer is the empty string "". For a "get", values[i] is "" and should be ignored.

Return a list with the answer to every "get", in the order they appear.

For any one key, the "set" operations come with strictly increasing timestamps, in the order they appear in the list. Different keys are independent, and a "get" can ask about any time.

Examples

Example 1

Input: operations = ["set", "get", "get", "set", "get", "get"], keys = ["a", "a", "a", "a", "a", "a"], values = ["x", "", "", "y", "", ""], timestamps = [2, 2, 1, 5, 4, 9]

Output: ["x", "", "x", "y"]

At time 2 the value is x. At time 1 there is no record yet, so the answer is empty. At time 4 the latest record not after 4 is still x, and at time 9 it is y.

Example 2

Input: operations = ["set", "set", "get", "get"], keys = ["p", "q", "q", "p"], values = ["red", "blue", "", ""], timestamps = [1, 3, 8, 2]

Output: ["blue", "red"]

The two keys are independent.

Constraints

1 <= len(operations) <= 10^4
len(keys) == len(values) == len(timestamps) == len(operations)
operations[i] is set or get
keys[i] has 1 to 20 lower-case letters or digits. For a set, values[i] has 1 to 20 lower-case letters or digits.
1 <= timestamps[i] <= 10^7
For each key, the timestamps of its set operations strictly increase in list order.