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"]