Retrieve the Latest Timestamped Value for Each Key

Problem Statement

Design a timestamped key-value store that records string values associated with a string key and an integer timestamp. The system must support out-of-order writes and provide fast point-in-time as well as overall latest lookups.

Implement the LatestValueStore class:

• LatestValueStore(): Initializes the object.
• void set(String key, String value, int timestamp): Stores the value for key at the given timestamp. Operations are not guaranteed to arrive in chronological order. If a set operation is called with a (key, timestamp) pair that has been set previously, the new value overwrites the old value for that timestamp.
• String get(String key, Integer timestamp = null): Returns the value associated with key that has the greatest timestamp less than or equal to timestamp. If timestamp is null (or omitted), returns the value with the greatest timestamp overall for key. If no such entry exists (e.g., the key does not exist or all recorded timestamps for that key are strictly greater than timestamp), return an empty string "".

The volume of operations is high, so rescanning the entire history on each lookup is too slow and will exceed time limits.

Interface

class LatestValueStore:
    def __init__(self):
        pass

    def set(self, key: str, value: str, timestamp: int) -> None:
        pass

    def get(self, key: str, timestamp: int | None = None) -> str:
        pass

Examples

Example 1

store = LatestValueStore()
store.set("device_1", "standby", 10)
store.set("device_1", "active", 20)
store.set("device_1", "idle", 5)        # Out-of-order write

store.get("device_1")                   # Returns "active" (max timestamp is 20)
store.get("device_1", 15)               # Returns "standby" (greatest timestamp <= 15 is 10)
store.get("device_1", 4)                # Returns "" (no timestamp <= 4)
store.get("device_2")                   # Returns "" (key does not exist)

Example 2

store = LatestValueStore()
store.set("status", "yellow", 100)
store.set("status", "red", 100)          # Overwrite at timestamp 100
store.set("status", "green", 50)

store.get("status", 100)                # Returns "red"
store.get("status")                     # Returns "red"
store.get("status", 75)                 # Returns "green"

Constraints

• 1 <= key.length, value.length <= 50
• key and value consist only of lowercase English letters, digits, and underscores.
• 1 <= timestamp <= 10^9
• At most 2 * 10^5 calls will be made in total to set and get.
• Writes can arrive in arbitrary timestamp order.

Edge Cases

• Querying a key that has never been set.
• Querying a timestamp strictly smaller than any timestamp recorded for the key.
• Multiple writes at the exact same (key, timestamp) pair (latest write wins).
• Out-of-order writes arriving both before and after historical reads.