timemap.py

class TimeMap:
    def __init__(self):
        self._tm: dict[str, dict[int, str]] = {}
        self._stamps: dict[str, list[int]] = defaultdict(list)

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

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

        if timestamp < self._stamps[key][0]:
            return ""

        if timestamp > self._stamps[key][-1]:
            return self._tm[key][self._stamps[key][-1]]

        def _bin_search(lft, rgt, times, target, bound=0):
            if lft > rgt:
                return bound

            mdpt = (lft + rgt) // 2

            if times[mdpt] < target:
                return _bin_search(mdpt + 1, rgt, times, target, mdpt)
            else:
                return _bin_search(lft, mdpt - 1, times, target, bound)

        time = _bin_search(0, len(self._stamps[key]) - 1, self._stamps[key], timestamp)
        return self._tm[key][self._stamps[key][time]]