Skip to content

635. Design Log Storage System

  • Time:
    • Constructor: $O(1)$
    • put(id: int, timestamp: str): $O(1)$
    • retrieve(start: str, end: str, granularity: str): $O(|\texttt{put()}|)$
  • Space: $O(|\texttt{put()}|)$
 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
class LogSystem {
 public:
  void put(int id, string timestamp) {
    idAndTimestamps.emplace_back(id, timestamp);
  }

  vector<int> retrieve(string start, string end, string granularity) {
    vector<int> ans;
    const int index = granularityToIndices.at(granularity);
    const string s = start.substr(0, index);
    const string e = end.substr(0, index);

    for (const auto& [id, timestamp] : idAndTimestamps) {
      const string& t = timestamp.substr(0, index);
      if (s <= t && t <= e)
        ans.push_back(id);
    }

    return ans;
  }

 private:
  const unordered_map<string, int> granularityToIndices{
      {"Year", 4},  {"Month", 7},   {"Day", 10},
      {"Hour", 13}, {"Minute", 16}, {"Second", 19}};
  vector<pair<int, string>> idAndTimestamps;
};

 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
class LogSystem {
  public LogSystem() {
    granularityToIndices.put("Year", 4);
    granularityToIndices.put("Month", 7);
    granularityToIndices.put("Day", 10);
    granularityToIndices.put("Hour", 13);
    granularityToIndices.put("Minute", 16);
    granularityToIndices.put("Second", 19);
  }

  public void put(int id, String timestamp) {
    idAndTimestamps.add(new Pair<>(id, timestamp));
  }

  public List<Integer> retrieve(String start, String end, String granularity) {
    List<Integer> ans = new ArrayList<>();
    final int index = granularityToIndices.get(granularity);
    final String s = start.substring(0, index);
    final String e = end.substring(0, index);

    for (Pair<Integer, String> idAndTimestamp : idAndTimestamps) {
      final String timestamp = idAndTimestamp.getValue();
      final String t = timestamp.substring(0, index);
      if (t.compareTo(s) >= 0 && t.compareTo(e) <= 0)
        ans.add(idAndTimestamp.getKey());
    }

    return ans;
  }

  private Map<String, Integer> granularityToIndices = new HashMap<>();
  private List<Pair<Integer, String>> idAndTimestamps = new ArrayList<>();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class LogSystem:
  def __init__(self):
    self.granularityToIndices = {'Year': 4, 'Month': 7, 'Day': 10,
                                 'Hour': 13, 'Minute': 16, 'Second': 19}
    self.idAndTimestamps = []

  def put(self, id: int, timestamp: str) -> None:
    self.idAndTimestamps.append((id, timestamp))

  def retrieve(self, start: str, end: str, granularity: str) -> list[int]:
    index = self.granularityToIndices[granularity]
    s = start[:index]
    e = end[:index]
    return [id for id, timestamp in self.idAndTimestamps
            if s <= timestamp[:index] <= e]