leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

time-based.py (1282B)

      1 class TimeMap:
      2 
      3     def __init__(self):
      4         self.hash_map = {}
      5 
      6     def set(self, key: str, value: str, timestamp: int) -> None:
      7         current = []
      8         current_val = []
      9 
     10         if key in self.hash_map:
     11             current = self.hash_map[key]
     12             current_val = self.hash_map[key + " value"]
     13 
     14         current.append(timestamp)
     15         current_val.append(value)
     16 
     17         self.hash_map[key] = current
     18         self.hash_map[str(key) + " value"] = current_val
     19 
     20     def get(self, key: str, timestamp: int) -> str:
     21 
     22         current = []
     23         current_vals = []
     24 
     25         if key in self.hash_map:
     26             current = self.hash_map[key]
     27             current_vals = self.hash_map[str(key) + " value"]
     28 
     29         # perform binary search to find the biggest timestamp s.t. prev_timestamp <= timestamp
     30 
     31         left = 0
     32         right = len(current) - 1
     33 
     34         while left <= right:
     35             center = ((right - left) // 2) + left
     36             if (current[center] <= timestamp) and (
     37                 center == len(current) - 1 or current[(center + 1)] > timestamp
     38             ):
     39                 return current_vals[center]
     40             elif current[center] > timestamp:
     41                 right = center - 1
     42             else:
     43                 left = center + 1
     44 
     45         return ""