Skip to content

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()}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
struct T {
  string value;
  int 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.contains(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;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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<>();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class TimeMap:
  def __init__(self):
    self.values = collections.defaultdict(list)
    self.timestamps = collections.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 ''