Timestamped key-value store: return each key's value as of a query time

Build a key-value store that keeps every version of each key. Each write records a value for a key at a timestamp. Each read asks what the value of a key was at a given time: the value written by the latest write to that key whose timestamp is less than or equal to the query time.

Process a sequence of operations and return the result of every read.

Function Signature

def run_time_store(operations: list[list]) -> list[str]:

Each operation is one of:

• ["set", key, value, timestamp] records value for key at timestamp. It produces no output.
• ["get", key, timestamp] produces the value written by the set for key with the largest timestamp less than or equal to timestamp, or "" if there is no such set.

key and value are strings, and timestamp is an integer.

Rules

• Operations are processed in list order. A get sees only the set operations that appear before it in the list.
• set timestamps are strictly increasing in the order the set operations appear, across all keys, so a key never has two writes with the same timestamp.
• A get timestamp can be any value in the allowed range, earlier or later than any write.
• The output contains one string per get, in the order the get operations appear. If there are no get operations, return an empty list.

Constraints

• 1 <= len(operations) <= 2 * 10^5
• Every key and value is a nonempty string of at most 20 lowercase English letters and digits.
• 1 <= timestamp <= 10^9

Examples

Example 1

Input: operations = [["set", "color", "red", 3], ["get", "color", 2], ["get", "color", 3], ["get", "color", 5], ["set", "color", "blue", 8], ["get", "color", 7], ["get", "color", 8], ["get", "color", 100]]
Output: ["", "red", "red", "red", "blue", "blue"]

At time 2 nothing has been written to color. Times 3, 5 and 7 see the write at time 3. Times 8 and 100 see the write at time 8.

Example 2

Input: operations = [["set", "a", "x", 1], ["set", "b", "y", 2], ["get", "a", 2], ["get", "b", 1], ["get", "c", 5]]
Output: ["x", "", ""]

b was first written at time 2, so it has no value at time 1, and c was never written.

Example 3

Input: operations = [["set", "k", "v1", 10], ["get", "k", 50], ["set", "k", "v2", 20], ["get", "k", 50], ["get", "k", 15]]
Output: ["v1", "v2", "v1"]

The first get sees only the write at time 10. After the write at time 20, time 50 sees "v2", while time 15 still sees "v1".