Retrieve the Latest Timestamped Value for Each Key
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Retrieve the Latest Timestamped Value for Each Key
Implement an object that receives `set` and `get` operations. A `set` operation supplies a key, timestamp, and integer value. A `get` operation asks for the value stored for that key at the greatest timestamp seen so far.
Implement `latestValues(operations)`, which processes the operations in their given order and returns the result of every `get`.
## Operation Format
Each operation is an array of strings:
- `["set", key, timestamp, value]` stores `value` for `key` at `timestamp`.
- `["get", key]` returns the value for `key` whose timestamp is greatest among earlier `set` operations.
Timestamps and values are decimal integer strings in the input. The return value is an array containing an integer for each successful lookup and `null` when the key has not been set.
## Constraints
- `1 <= operations.length <= 200,000`
- Keys contain 1 to 50 lowercase English letters.
- `0 <= timestamp <= 10^18`
- `-10^9 <= value <= 10^9`
- Timestamps are unique within each key.
- `set` operations for a key may arrive out of timestamp order.
- `get` does not remove or reorder stored values, and this practice version has no capacity or eviction rule.
## Example 1
```text
Input: operations = [["set", "a", "5", "40"], ["set", "a", "2", "9"], ["get", "a"], ["set", "b", "7", "-3"], ["get", "b"]]
Output: [40, -3]
```
For key `a`, timestamp `5` remains the latest even though timestamp `2` arrived afterward.
## Example 2
```text
Input: operations = [["get", "x"], ["set", "x", "1", "4"], ["set", "x", "9", "12"], ["set", "x", "5", "7"], ["get", "x"]]
Output: [null, 12]
```
The first lookup occurs before any value for `x` has been stored.
Quick Answer: Process timestamped set and get operations so each lookup returns the value with the greatest timestamp for its key. The exercise covers out-of-order updates, repeated keys, missing-key behavior, and an operation count that rules out rescanning history.
Implement latestValues(operations). Process each string-array operation in order. ["set", key, timestamp, value] stores the integer value for that key at the given timestamp. ["get", key] returns the value at the greatest timestamp among earlier set operations for the key. Set operations for one key may arrive out of timestamp order and have unique timestamps. Return one integer for each successful get and null for a get before that key has been set. A get does not remove or reorder data, and there is no capacity or eviction rule.
Constraints
- 1 <= operations.length <= 200,000
- Every operation is ["set", key, timestamp, value] or ["get", key].
- Keys contain 1 to 50 lowercase English letters.
- 0 <= timestamp <= 10^18 and timestamps are unique within each key.
- -10^9 <= value <= 10^9
- Set operations for a key may arrive out of timestamp order.
- Return null for a key that has not been set; get does not mutate stored data.
Examples
Input: ([['set', 'a', '5', '40'], ['set', 'a', '2', '9'], ['get', 'a'], ['set', 'b', '7', '-3'], ['get', 'b']],)
Expected Output: [40, -3]
Explanation: The first source example keeps the greater timestamp after an older write arrives.
Input: ([['get', 'x'], ['set', 'x', '1', '4'], ['set', 'x', '9', '12'], ['set', 'x', '5', '7'], ['get', 'x']],)
Expected Output: [None, 12]
Explanation: The second source example checks a missing key and several out-of-order writes.
Hints
- A future get needs only one timestamp-value pair per key.
- Compare every arriving timestamp with the greatest timestamp retained for that key.