Design Log Storage System

Medium Design Data Structures Pre-processing + tradeoffs Original on LeetCode

Design Log Storage System is a medium design data structures problem solved with the pre-processing + tradeoffs pattern. The best approach, optimal (sorted map + padded bounds), runs in O(log n) put, O(log n + m) retrieve time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan every log and compare prefixes) up.

Problem

Design a store for log entries, LogSystem. Each log has an integer id and a timestamp string of the form Year:Month:Day:Hour:Minute:Second, such as 2011:04:19:07:05:33, where every field is zero-padded.

LogSystem() creates an empty store. put(int id, String timestamp) saves a log. retrieve(String start, String end, String granularity) returns the ids of all saved logs whose timestamp lies between start and end inclusive, comparing only the fields up to and including granularity (one of Year, Month, Day, Hour, Minute, Second). For example, with granularity Day, the hour, minute and second of every timestamp and of both bounds are ignored.

The ids may be returned in any order.

Examples

Example 1

Input
LogSystem(), put(1, "2015:06:10:08:30:00"), put(2, "2015:06:11:22:05:09"), put(3, "2014:12:31:23:59:59"), retrieve("2015:01:01:00:00:00", "2015:12:31:23:59:59", "Year"), retrieve("2015:06:10:00:00:00", "2015:06:10:00:00:00", "Day")
Output
[1, 2], [1]
Why
At Year granularity only the year counts, so every 2015 log matches. At Day granularity both bounds become 2015-06-10, and only log 1 falls on that day.

Example 2

Input
LogSystem(), put(7, "2003:03:03:10:00:00"), put(8, "2003:03:03:11:45:00"), retrieve("2003:03:03:10:59:59", "2003:03:03:11:00:00", "Hour"), retrieve("2003:03:03:10:59:59", "2003:03:03:11:00:00", "Second")
Output
[7, 8], []
Why
Cut to hours, the range is 10:xx to 11:xx, which covers both logs. With full precision the range is just two seconds wide and neither log is inside it.

Constraints

  • 1 <= id <= 500, and each id is passed to put at most once.
  • Timestamps have the form Year:Month:Day:Hour:Minute:Second with 2000 <= Year <= 2017 and every field zero-padded (4 digits for the year, 2 for the rest).
  • granularity is one of "Year", "Month", "Day", "Hour", "Minute", "Second".
  • start <= end when compared field by field.
  • At most 500 calls to put and retrieve in total.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (scan every log and compare prefixes)O(1) put, O(n) retrieveO(n)
Optimal (sorted map + padded bounds)O(log n) put, O(log n + m) retrieveO(n)

1Brute force (scan every log and compare prefixes)

TimeO(1) put, O(n) retrieveEach query looks at all n stored logs, each in constant time (timestamps have fixed length).
SpaceO(n)All logs are stored once.

Store the logs in a list. For a query, cut the start, the end and each log's timestamp to the prefix that the granularity keeps, and keep the logs whose prefix lies between the two bounds (string comparison works since all fields are zero-padded).

  1. put: append (id, timestamp) to the list.
  2. retrieve: L = prefix length for the granularity (Year 4, Month 7, Day 10, Hour 13, Minute 16, Second 19).
  3. lo = start[0..L), hi = end[0..L); add every id whose timestamp[0..L) is between lo and hi, inclusive.
class LogSystem {
    private final List<Integer> ids = new ArrayList<>();
    private final List<String> times = new ArrayList<>();

    public LogSystem() {}

    public void put(int id, String timestamp) {
        ids.add(id);
        times.add(timestamp);
    }

    private int cut(String granularity) {
        switch (granularity) {
            case "Year": return 4;
            case "Month": return 7;
            case "Day": return 10;
            case "Hour": return 13;
            case "Minute": return 16;
            default: return 19;
        }
    }

    public List<Integer> retrieve(String start, String end, String granularity) {
        int len = cut(granularity);
        String lo = start.substring(0, len), hi = end.substring(0, len);
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < ids.size(); i++) {
            String t = times.get(i).substring(0, len);
            if (t.compareTo(lo) >= 0 && t.compareTo(hi) <= 0) res.add(ids.get(i));
        }
        return res;
    }
}

2Optimal (sorted map + padded bounds)

TimeO(log n) put, O(log n + m) retrieveInserting and locating the range are binary-search steps; then the m matching logs are read off.
SpaceO(n)The sorted map stores each log once.

Keep the logs in a map sorted by timestamp. For a query, keep the granularity prefix of start and fill the rest with the smallest possible tail ("0000:00:00:00:00:00"), and keep the prefix of end and fill the rest with the largest tail ("9999:99:99:99:99:99"). All matching logs now form one contiguous range of the sorted map, found with two binary searches.

  1. put: add id under its timestamp in a sorted map (timestamp -> list of ids).
  2. retrieve: L = prefix length; lo = start[0..L) + MIN[L..]; hi = end[0..L) + MAX[L..].
  3. Collect the ids of every entry with lo <= timestamp <= hi, in sorted order.
class LogSystem {
    private static final String MIN = "0000:00:00:00:00:00";
    private static final String MAX = "9999:99:99:99:99:99";
    private final TreeMap<String, List<Integer>> logs = new TreeMap<>();

    public LogSystem() {}

    public void put(int id, String timestamp) {
        logs.computeIfAbsent(timestamp, t -> new ArrayList<>()).add(id);
    }

    private int cut(String granularity) {
        switch (granularity) {
            case "Year": return 4;
            case "Month": return 7;
            case "Day": return 10;
            case "Hour": return 13;
            case "Minute": return 16;
            default: return 19;
        }
    }

    public List<Integer> retrieve(String start, String end, String granularity) {
        int len = cut(granularity);
        String lo = start.substring(0, len) + MIN.substring(len);
        String hi = end.substring(0, len) + MAX.substring(len);
        List<Integer> res = new ArrayList<>();
        for (List<Integer> group : logs.subMap(lo, true, hi, true).values()) {
            res.addAll(group);
        }
        return res;
    }
}

Edge cases to test

  • A log exactly on the start or end bound (the range is inclusive)
  • Bounds that differ only in fields finer than the granularity, which collapse to the same unit
  • No log in range (return an empty list)
  • Several logs with the same timestamp

Hints

Hint 1

Because every field is zero-padded, comparing two timestamps as strings gives the same order as comparing them as times.

Hint 2

Granularity just means 'ignore everything after this field'. Each field ends at a fixed position in the string: 4, 7, 10, 13, 16, 19.

Hint 3

Keep logs sorted by timestamp. Pad the cut start with the smallest possible tail and the cut end with the largest, then read off one contiguous range.

FAQ

What is the best time complexity for Design Log Storage System?

Optimal (sorted map + padded bounds) runs in O(log n) put, O(log n + m) retrieve time and O(n) extra space. Inserting and locating the range are binary-search steps; then the m matching logs are read off.

Which pattern does Design Log Storage System use?

It is a design data structures problem that uses the pre-processing + tradeoffs pattern. Other problems with the same pattern: Design Neighbor Sum Service, Simple Bank System, Design File System.

Is there a brute force solution for Design Log Storage System?

Yes. Brute force (scan every log and compare prefixes) takes O(1) put, O(n) retrieve time and O(n) space. Store the logs in a list.

Which edge cases should I test for Design Log Storage System?

A log exactly on the start or end bound (the range is inclusive); Bounds that differ only in fields finer than the granularity, which collapse to the same unit; No log in range (return an empty list); Several logs with the same timestamp.