Time-Based Key-Value Store

Statement

Implement a data structure that can store multiple values of the same key at different timestamps and retrieve the key’s value at a certain timestamp.

You’ll need to implement the TimeStamp class. This class has the following functions:

• Init(): This function initializes the values dictionary and timestamp dictionary.

• Set Value(key, value, timestamp): This function stores the key and value at any given timestamp.

• Get Value(key, timestamp): This function returns the value set for this key at the specified timestamp.

Note: When a query requests the value of a key at a timestamp that is more recent than the most recent entry for that key, our data structure should return the value corresponding to the most recent timestamp.

Constraints:

• $1 \leq$ key.length, value.length $\leq 20$
• key and value consist of lowercase English letters and digits.
• $1 \leq$ timestamp $\leq 10^3$
• At most $1 \times 10^3$ calls will be made to Set Value and Get Value.
• All the timestamps, timestamp, of Set Value are strictly increasing.

Examples