1
class TimeMap:
2

3
    def __init__(self):
4
        self.dict = {}
5

6
    def set(self, key: str, value: str, timestamp: int) -> None:
7
        if key not in self.dict:
8
            self.dict[key] = ([], [])
9
            self.dict[key][0].append(value)
10
            self.dict[key][1].append(timestamp)
11
        else:
12
            self.dict[key][0].append(value)
13
            self.dict[key][1].append(timestamp)
14

15
    def bsearch(self, nums, target):
16
        beg = 0
17
        end = len(nums) - 1
18
        lastIndex = len(nums) - 1
19

20
        while beg <= end:
21
            mid = (beg + end) // 2
22
            if target == nums[mid]:
23
                return mid
24
            elif target < nums[mid]:
25
                end = mid - 1
26
            elif target > nums[mid]:
27
                beg = mid + 1
28

29
        if target < nums[mid] and mid == 0:
30
            return -1
31
        if target > nums[mid]:
32
            return mid
33
        return mid - 1
34

35
    def get(self, key: str, timestamp: int) -> str:
36
        if key not in self.dict:
37
            return ""
38

39
        index = self.bsearch(self.dict[key][1], timestamp)
40
        return self.dict[key][0][index] if 0 <= index < len(self.dict[key][0]) else ""
41

42

43
# Your TimeMap object will be instantiated and called as such:
44
# obj = TimeMap()
45
# obj.set(key,value,timestamp)
46
# param_2 = obj.get(key,timestamp)