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.

Versioned Key-Value Store with Point-in-Time Reads

Hints

1. A get can only see sets that appear before it in the list, so each get can be answered at the moment you reach it while walking through the operations once.
2. Given the rule about set timestamps, in what order are the versions of any single key recorded?
3. A read wants the last version of its key at or before the read's time; consider how the ordering of a key's versions lets you find it without checking every version.

Approach

Process the operations once, in list order, and answer each get the moment it is reached. For every key keep two parallel arrays: the timestamps of its sets and the matching values, appended as those sets are reached. Because set timestamps strictly increase in list order across all keys, each key's timestamp array is strictly increasing, so it is always sorted without any extra work. Invariant: when a get is reached, its key's arrays hold exactly the sets of that key that appear earlier in the list, which is precisely the get's visibility rule (a later-listed set is not stored yet, even if its timestamp is smaller than the get's). The required answer is the version with the largest timestamp <= the get's timestamp; in a sorted array that is the element immediately before the first timestamp strictly greater than the query (an upper-bound binary search), found in O(log m) for a key with m versions instead of scanning them. If that position is 0, every visible version is later than the query, and if the key has no versions it was never set; both return "". Edge cases: a list with no gets returns []; a query equal to a version's timestamp returns that version (upper bound, not lower bound); a query between two versions returns the earlier one (floor, not ceiling); a query after the last version returns the last; another key's nearer version never leaks because versions are stored per key; keys and values may themselves be the words set or get, so the operation kind is read only from the first field. Timestamps are at most 10^7, so 32-bit integers suffice.

• Time complexity: O(n log n)
• Space complexity: O(n)