Design Log Storage System

medium design string

Problem

put(id, ts) and retrieve(s, e, granularity) → ids in [s,e] when both timestamps are truncated to that granularity.

Inputput(1,'2017:01:01:23:59:59'); retrieve('2017:01:01','2017:01:01','Hour')

Output[1]

Truncate to 'YYYY:MM:DD:HH' for both ends and the log.

input

class LogSystem:
    def __init__(self): self.logs = []
    def put(self, i, ts): self.logs.append((i, ts))
    def retrieve(self, s, e, g):
        i = {'Year':4,'Month':7,'Day':10,'Hour':13,'Minute':16,'Second':19}[g]
        return [x for x, t in self.logs if s[:i] <= t[:i] <= e[:i]]

class LogSystem {
  constructor() { this.logs = []; }
  put(id, ts) { this.logs.push([id, ts]); }
  retrieve(s, e, g) {
    const idx = { Year: 4, Month: 7, Day: 10, Hour: 13, Minute: 16, Second: 19 }[g];
    return this.logs.filter(([, t]) => s.slice(0, idx) <= t.slice(0, idx) && t.slice(0, idx) <= e.slice(0, idx)).map(l => l[0]);
  }
}

class LogSystem {
    List logs = new ArrayList<>(); List times = new ArrayList<>();
    Map g = Map.of("Year",4,"Month",7,"Day",10,"Hour",13,"Minute",16,"Second",19);
    public void put(int id, String ts) { logs.add(new int[]{id, logs.size()}); times.add(ts); }
    public List retrieve(String s, String e, String gr) {
        int i = g.get(gr); List out = new ArrayList<>();
        for (int k = 0; k < logs.size(); k++) {
            String t = times.get(k).substring(0, i);
            if (t.compareTo(s.substring(0, i)) >= 0 && t.compareTo(e.substring(0, i)) <= 0) out.add(logs.get(k)[0]);
        }
        return out;
    }
}

class LogSystem {
    vector> logs;
    map g = {{"Year",4},{"Month",7},{"Day",10},{"Hour",13},{"Minute",16},{"Second",19}};
public:
    void put(int id, string ts) { logs.push_back({id, ts}); }
    vector retrieve(string s, string e, string gr) {
        int i = g[gr]; vector out;
        for (auto& [id, t] : logs) if (t.substr(0, i) >= s.substr(0, i) && t.substr(0, i) <= e.substr(0, i)) out.push_back(id);
        return out;
    }
};

Explanation

Timestamps here look like 2017:01:01:23:59:59 — year, month, day, hour, minute, second, all in a fixed layout. The clever observation is that because every field has a fixed width, you can compare timestamps at any granularity just by comparing a prefix of the string.

The map {'Year':4,'Month':7,'Day':10,'Hour':13,'Minute':16,'Second':19} tells you how many characters to keep. For example, granularity Hour keeps the first 13 characters, which is exactly YYYY:MM:DD:HH.

put(id, ts) just stores the log as-is. retrieve(s, e, g) truncates the start s, end e, and each log timestamp to the same prefix length i, then keeps every id whose truncated time falls in the range s[:i] <= t[:i] <= e[:i].

String comparison works directly because the format is zero-padded and goes from biggest unit to smallest, so lexicographic order matches chronological order.

Example: a log at 2017:01:01:23:59:59 with granularity Hour truncates to 2017:01:01:23. Querying the range 2017:01:01 to 2017:01:01 truncated to hour gives 2017:01:01:00 on both ends, so that log only matches if the chosen range actually includes hour 23.

Time: O(n) Space: O(n)