Historical Lookups in a Timestamped Key-Value Store

Implement a timestamped key-value store and answer historical lookups. A lookup for a key at time t returns the value written at the greatest timestamp less than or equal to t.

Function Contract

Implement process_operations(operation_types, keys, values, timestamps) -> list[str].

The four arguments are arrays of equal length. Process index i before index i + 1:

• operation_types[i] is either "set" or "get".
• keys[i] is the key used by that operation.
• timestamps[i] is its integer timestamp.
• For "set", values[i] is the nonempty string to store. For "get", values[i] is "" and is ignored.

Return one string for each "get", in operation order. A lookup considers only preceding "set" operations. If that key has no stored timestamp at or before the requested time, return "".

Constraints and Clarifications

These explicit practice assumptions complete the store interface: writes for each individual key have strictly increasing timestamps, historical values are retained, and there are no delete operations. Different keys may share a timestamp. Lookup timestamps may appear in any order and may precede the first write for a key.

• 0 <= n <= 200000, where n is the length of each argument.
• Every timestamp is an integer between 0 and 1000000000, inclusive.
• Keys and stored values contain lowercase English letters or digits and have length 1 through 100.
• The total number of characters across keys and values is at most 2000000.
• Aim for amortized constant time per write and logarithmic time per lookup in that key's stored history, apart from string-processing costs.

Examples

operation_types = ["set", "get", "get", "set", "get", "get"]
keys = ["a", "a", "a", "a", "a", "a"]
values = ["red", "", "", "blue", "", ""]
timestamps = [2, 2, 5, 8, 7, 8]
Output: ["red", "red", "red", "blue"]

The lookup at time 7 still returns "red", although the write at time 8 has already been processed.

operation_types = ["get", "set", "get", "get"]
keys = ["missing", "x", "x", "x"]
values = ["", "v", "", ""]
timestamps = [9, 4, 3, 4]
Output: ["", "", "v"]

Hint: Search within one key's history

The writes for one key already have a useful ordering. For a query time, focus on the boundary between timestamps that qualify and timestamps that are too large.

Replay Timestamped Key-Value Store Operations

You are given four arrays of equal length n that describe a sequence of operations on a timestamped key-value store. Process the operations in index order: index i must be handled before index i + 1.

For each index i:

• operation_types[i] is either "set" or "get".
• keys[i] is the key that operation uses.
• timestamps[i] is that operation's integer timestamp.
• For a "set", values[i] is the nonempty string to store for that key at that timestamp.
• For a "get", values[i] is "" and is ignored.

A "set" stores a value for a key at a timestamp. Historical values are retained and there are no delete operations. A "get" for a key at time t returns the value written for that key at the greatest timestamp less than or equal to t, considering only "set" operations that appear earlier in the arrays. If that key has no stored timestamp at or before the requested time (the key was never written yet, or every earlier write for it happened at a timestamp greater than t), the lookup returns "".

Return a list holding one string per "get" operation, in operation order. "set" operations contribute nothing to the output, so a run containing no "get" returns an empty list.

For each individual key, the timestamps of its "set" operations are strictly increasing in operation order, so one key never has two values at the same timestamp. Different keys may share a timestamp. Lookup timestamps may appear in any order and may precede the first write for a key.

Every timestamp lies between 0 and 1000000000, so no value in this problem exceeds 2^31 - 1: 32-bit integers are sufficient (Java int, C++ int).

Example 1:

operation_types = ["set", "get", "get", "set", "get", "get"]
keys = ["a", "a", "a", "a", "a", "a"]
values = ["red", "", "", "blue", "", ""]
timestamps = [2, 2, 5, 8, 7, 8]
Output: ["red", "red", "red", "blue"]

The lookups at times 2 and 5 see only the write at time 2. The lookup at time 7 still returns "red", although the write at time 8 has already been processed, because 8 > 7. The final lookup at time 8 matches that write exactly.

Example 2:

operation_types = ["get", "set", "get", "get"]
keys = ["missing", "x", "x", "x"]
values = ["", "v", "", ""]
timestamps = [9, 4, 3, 4]
Output: ["", "", "v"]

The key "missing" was never written. The lookup at time 3 precedes x's only write at time 4, so it returns "". The lookup at time 4 matches that write exactly.

Hints

1. Results must reflect the state of the store at the moment each lookup happens, so handle the four arrays in one left-to-right pass instead of pre-scanning all the writes first.
2. The writes recorded for one key already arrive with strictly increasing timestamps, so that key's history is sorted the moment you append to it; different keys are completely independent of one another.
3. For a query time, focus on the boundary between the stored timestamps that qualify (at or before the query time) and the ones that are too large, and remember that the qualifying group can be empty.

Approach

Algorithm. Sweep the four arrays once, left to right, keeping a hash map from key to that key's write history stored as two parallel lists: the timestamps written so far and the values written at them. A "set" appends timestamp and value to the history of its key, which is O(1) amortized. A "get" looks the key up: if the key has no history yet the answer is "", otherwise binary search that key's timestamp list for the rightmost index whose timestamp is <= the query time and return the value at that index, or "" when no index qualifies.

Invariant. Because the sweep is strictly in operation order and appends only when a "set" is reached, at the moment a "get" at index i is handled the history for its key contains exactly the writes at indices j < i for that key, in increasing index order. The problem guarantees that one key's "set" timestamps strictly increase in operation order, so that list is sorted ascending with no duplicates and never needs re-sorting; the binary search precondition holds without any extra work.

Correctness. The binary search maintains 'best' = the largest index seen so far whose timestamp is <= t, narrowing [lo, hi] so that every index outside it has been decided: indices below lo have qualifying timestamps, indices above hi are too large. Because the list is sorted ascending, the qualifying indices form a prefix, so the largest qualifying index is the last element of that prefix, and its value is the one written at the greatest timestamp <= t. If the prefix is empty, best stays -1, which is exactly the case 'the key has no stored timestamp at or before t' and the specification fixes the answer as "". Results are appended only for "get" operations and only during the single forward pass, so the returned list has one entry per "get" in operation order.

Edge cases. n = 0 returns an empty list. A run with only "set" operations returns an empty list. A "get" on a key never written, or on a key whose earlier writes are all later than t, returns "". A query time equal to a stored timestamp matches it (the comparison is <=, not <). A write that appears later in the array is invisible to an earlier lookup even if its timestamp is smaller, and a write already processed is invisible to a lookup whose time is smaller than that write's timestamp. Keys are independent: distinct keys may share timestamps, and keys that are string prefixes of one another are still distinct keys. Timestamps are at most 1000000000, so they fit in a signed 32-bit integer; the references still read them as 64-bit in Java and C++ so no boundary arithmetic can overflow.

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