Solutions

# Use a hash map to store the key and a list of (timestamp, value) pairs for each key. For get, do a binary search on the list of pairs to find the value with the largest timestamp that is <= the given timestamp.
# binary-search

# O(1) time for set, O(log n) time for get, O(n) space
class TimeMap:

    def __init__(self):
        self.kv : dict[str, list[tuple[int, str]]] = {}
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.kv:
            self.kv[key] = []
        self.kv[key].append((timestamp, value))
        

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.kv:
            return ""
        
        values = self.kv[key]

        res = ""
        left, right = 0, len(values) -1
        while left <= right:
            mid = left + (right-left)//2

            if values[mid][0] == timestamp:
                return values[mid][1]
            elif values[mid][0] < timestamp:
                left = mid + 1
                # NB: not exactly mid, but the largest timestamp that is <= the given timestamp, so we set res to the value of mid,
                # and then keep searching in the right half to see if there's a larger timestamp that is still <= the given timestamp
                res = values[mid][1]
            else:
                right = mid -1
        
        return res