981. Time Based Key Value Store

class TimeMap:
  def __init__(self):
    self.hashMap = {}

  def set(self, key, value, timestamp):
    self.hashMap.setdefault(key, []).append((timestamp, value))

  def get(self, key, timestamp):
    arr = self.hashMap[key]
    left = 0
    right = len(arr) - 1
    mid = (left + right)//2

    if timestamp < arr[0][0]:
      return ''
    while(True):
      if left > right:
        return arr[right][1]
      if arr[mid][0] == timestamp:
        return arr[mid][1]

      if timestamp < arr[mid][0]:
        right = mid -1
      else:
        left = mid + 1
      mid = (left + right)//2

obj = TimeMap()
obj.set('love', 'high', 10)
obj.set('love', 'low', 20)
print(obj.get('love', 5))
print(obj.get('love', 10))
print(obj.get('love', 15))
print(obj.get('love', 20))
print(obj.get('love', 25))