981. Time Based Key-Value Store

class TimeMap:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.d = {}

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

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.d:
            return ""
        num = ord('z') + 1 
        idx = bisect.bisect(self.d[key],(timestamp,chr(num)))
        return self.d[key][idx-1][1] if idx else ""
        

class TimeMap:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.d = {}

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

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.d:
            return ""
        l = 0
        r = len(self.d[key])
        arr = self.d[key]
        while l < r:
            mid = l + (r-l)//2 
            if arr[mid][0] == timestamp:
                return arr[mid][1]
            elif arr[mid][0] < timestamp:
                l = mid +1
            else:
                r = mid 
        return "" if r == 0  else arr[r-1][1] 

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