981. Time Based Key-Value Store

Problem Statement

link: LeetCode.cn LeetCode

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key’s value at a certain timestamp.

Implement the TimeMap class:

TimeMap() Initializes the object of the data structure. void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp. String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns “”.

Example:

Input: ["TimeMap", "set", "get", "get", "set", "get", "get"][[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]] Output: [null, null, "bar", "bar", null, "bar2", "bar2"]

Solution Approach

The solution utilizes a dictionary where each key maps to a SortedDict, storing timestamps as keys and corresponding values as values. When setting a value for a key at a particular timestamp, it is added to the SortedDict associated with that key. When retrieving a value for a key at a given timestamp, the SortedDict is accessed, and the value associated with the largest timestamp less than or equal to the given timestamp is returned.

Algorithm

1. Initialization: Create a dictionary to map keys to SortedDicts, ensuring ordered storage of timestamp-value pairs.
2. Setting Values: Implement the set method to add key-value pairs with timestamps into the corresponding SortedDicts.
3. Retrieving Values: Develop the get method to access the SortedDict associated with the given key, then locate the nearest preceding timestamp and return its corresponding value, or an empty string if no such timestamp exists.

Implement

    class TimeMap:
    def __init__(self):
      self.dic = defaultdict(SortedDict)
      #{key:{time:value}}
    def set(self, key: str, value: str, timestamp: int) -> None:
      self.dic[key][timestamp] = value

    def get(self, key: str, timestamp: int) -> str:
      if key not in self.dic:
          return ""
      keys = self.dic[key].keys()
      idx = self.dic[key].bisect_left(timestamp)
      if idx == len(keys) or key[idx] > timestamp:
          idx -= 1
      return self.dic[key][keys[idx]] if idx >= 0 else ""
      


class TimeMap:

  def __init__(self):
      self.word_time = {}
      self.value = {}

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

  def get(self, key: str, timestamp: int) -> str:
      if key not in self.word_time:
          return ''
      times = self.word_time[key][0]
      values = self.word_time[key][1]
      if timestamp < times[0]:
          return ''
      b = bisect.bisect_right(times, timestamp)
      c = bisect.bisect_left(times,timestamp)
      #print('right,',b,'left:',c,'times',times,'timestamp',timestamp)
      return values[b-1]

    
    

Twitter  facebook  Email