Time-Based Key-Value Store

Problem Statement

Design a time-based key-value data structure that can store multiple values for the same key at different timestamps and retrieve the key's value at a specific timestamp.

Implement the TimeMap class:

• TimeMap(): Initializes the data structure.
• set(key: str, value: str, timestamp: int) -> None: Stores the key with the value at the given timestamp.
• get(key: str, timestamp: int) -> str: Returns the value associated with key such that prev_timestamp <= timestamp and prev_timestamp is maximized. If no such value exists (e.g., all recorded timestamps for that key are strictly greater than timestamp, or the key does not exist), return an empty string "".

Class Interface

class TimeMap:
    def __init__(self):
        pass

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

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

Constraints

• 1 <= key.length, value.length <= 100
• key and value consist of lowercase English letters.
• 1 <= timestamp <= 10^7
• All timestamp values in calls to set are strictly increasing for each given key.
• At most 2 * 10^5 calls total will be made to set and get.

Examples

Example 1

time_map = TimeMap()
time_map.set("user", "alice", 1)

time_map.get("user", 1)  # returns "alice"
time_map.get("user", 3)  # returns "alice" (latest timestamp <= 3 is 1)

time_map.set("user", "bob", 4)
time_map.get("user", 4)  # returns "bob"
time_map.get("user", 5)  # returns "bob" (latest timestamp <= 5 is 4)
time_map.get("user", 0)  # returns "" (no timestamp <= 0 exists)

Example 2

time_map = TimeMap()
time_map.set("config", "v1", 10)
time_map.set("config", "v2", 20)
time_map.set("config", "v3", 30)

time_map.get("config", 15)  # returns "v1"
time_map.get("config", 20)  # returns "v2"
time_map.get("config", 29)  # returns "v2"
time_map.get("system", 10)  # returns "" (key does not exist)

Edge Cases to Consider

• Looking up a key that has never been set.
• Querying a timestamp strictly less than the smallest timestamp stored for a key.
• Multiple set operations on the same key with consecutive timestamps.