Point-in-Time Reads from a Timestamped Key-Value Store

Implement a key-value store that keeps every version of each key. A write records a value for a key at a timestamp without discarding earlier versions, and a read asks for a key as of a timestamp and returns the value that was current at that time.

The interviewer's focus is the data structure behind the read: a read should not have to scan through every version of its key.

So that the store can be called as one function, it is driven by a list of operations that are processed in order, and you return the results of the reads.

Function Signature

def run_versioned_store(operations: list[tuple]) -> list[str]:

Each operation is one of:

• ("set", key, value, timestamp): store value for key at time timestamp.
• ("get", key, timestamp): read key as of time timestamp.

Rules

• A get considers only the set operations for the same key that appear earlier in the list. Among those, it returns the value of the one with the largest timestamp that is less than or equal to the get's timestamp.
• If there is no such set, because the key has never been set or every earlier set of the key has a larger timestamp, the get returns the empty string "".
• A set never removes earlier versions of its key.
• Return one string per get, in the order the get operations appear. Return an empty list if there are no get operations.

Constraints

• 1 <= len(operations) <= 2 * 10^5
• Every key and value is a non-empty string of at most 100 lowercase English letters and digits.
• 1 <= timestamp <= 10^7 in every operation.
• The timestamps of the set operations strictly increase in the order those operations appear, across all keys. The timestamps of get operations can be any value in range, in any order.

Examples

Example 1

Input: operations = [("set", "price", "10", 5), ("get", "price", 4), ("get", "price", 5),
 ("set", "price", "12", 9), ("get", "price", 8), ("get", "price", 9),
 ("get", "price", 100)]
Output: ["", "10", "10", "12", "12"]

At time 4 the key has no version yet. Reads at times 5 and 8 see the version written at time 5, because the version written at time 9 is later than 8. Reads at times 9 and 100 see the version written at time 9.

Example 2

Input: operations = [("set", "a", "x", 1), ("set", "b", "y", 2), ("get", "a", 2),
 ("get", "b", 1), ("set", "a", "z", 3), ("get", "a", 3), ("get", "c", 3)]
Output: ["x", "", "z", ""]

Key b was first written at time 2, so a read at time 1 finds nothing. Key c is never written.