361. Timestamped Store

MediumDesignHash TableBinary SearchString3 hints
RPby Rohit Parihar

Build a small settings service that remembers how each setting changed over time. Every update has a key (the setting's name), a value and a timestamp. The service must also answer questions of the form: what was the value of this setting at a given moment?

Implement the class TimeStore with a constructor that takes no arguments and two methods. save(key, value, timestamp) records that key holds value from timestamp on. valueAt(key, timestamp) returns the value recorded for key with the largest timestamp that is at most the given timestamp, or an empty string if there is none. Timestamps passed to save are strictly increasing over all calls.

Example 1

Input:
operations = ["TimeStore","save","valueAt","valueAt","save","valueAt"]arguments = [[],["mode","dark",2],["mode",2],["mode",1],["mode","light",7],["mode",5]]
Output:
[null,null,"dark","",null,"dark"]
Explanation:

After save at time 2, valueAt at time 2 returns dark. At time 1 nothing was recorded, so the result is an empty string. At time 5 the latest record is still dark, because light only starts at time 7.

Example 2

Input:
operations = ["TimeStore","save","save","valueAt","valueAt"]arguments = [[],["a","x",1],["b","y",2],["a",9],["b",1]]
Output:
[null,null,null,"x",""]
Explanation:

Each key keeps its own history. a holds x from time 1; b has nothing before time 2.

Constraints

1 ≤ key.length, value.length ≤ 100
1 ≤ timestamp ≤ 109 for save calls, and timestamps given to save strictly increase
0 ≤ timestamp ≤ 109 for valueAt calls
At most 2 * 105 calls in total.

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time
O(1) save, O(log m) valueAt
Space
O(total updates)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.