Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

981. Time Based Key-Value Store

Time: Constructor: $O(1)$, set(key: str, value: str, timestamp: int): $O(1)$, get(key: str, timestamp: int): $O(\log n)$, where $n = |\texttt{map[key]}|$

Space: $O(|\texttt{set(key: str, value: str, timestamp: int)}|)$

			


struct T {
  string value;
  int timestamp;
  T(string value, int timestamp) : value(value), timestamp(timestamp) {}
};

class TimeMap {
 public:
  void set(string key, string value, int timestamp) {
    map[key].emplace_back(value, timestamp);
  }

  string get(string key, int timestamp) {
    if (!map.count(key))
      return "";

    const vector<T>& A = map[key];
    int l = 0;
    int r = A.size();

    while (l < r) {
      const int m = (l + r) / 2;
      if (A[m].timestamp > timestamp)
        r = m;
      else
        l = m + 1;
    }

    return l == 0 ? "" : A[l - 1].value;
  }

 private:
  unordered_map<string, vector<T>> map;
};




			


class T {
  public String value;
  public int timestamp;
  public T(String value, int timestamp) {
    this.value = value;
    this.timestamp = timestamp;
  }
}

class TimeMap {
  public void set(String key, String value, int timestamp) {
    map.putIfAbsent(key, new ArrayList<>());
    map.get(key).add(new T(value, timestamp));
  }

  public String get(String key, int timestamp) {
    List<T> A = map.get(key);
    if (A == null)
      return "";

    int l = 0;
    int r = A.size();

    while (l < r) {
      final int m = (l + r) / 2;
      if (A.get(m).timestamp > timestamp)
        r = m;
      else
        l = m + 1;
    }

    return l == 0 ? "" : A.get(l - 1).value;
  }

  private Map<String, List<T>> map = new HashMap<>();
}




			


class TimeMap:
  def __init__(self):
    self.values = defaultdict(list)
    self.timestamps = defaultdict(list)

  def set(self, key: str, value: str, timestamp: int) -> None:
    self.values[key].append(value)
    self.timestamps[key].append(timestamp)

  def get(self, key: str, timestamp: int) -> str:
    if key not in self.timestamps:
      return ''
    i = bisect.bisect(self.timestamps[key], timestamp)
    return self.values[key][i - 1] if i > 0 else ''