Design Log Storage System - Leetcode Solution

The Design Log Storage System problem on Leetcode asks us to design a system that can store logs according to their timestamps and retrieve them based on some query conditions. The logs have the following format:

id:integer, timestamp: string, content: string

We need to support two operations on this log storage system:

1. addLog(id:integer, timestamp:string, content:string) - Adds a new log to the system.
2. retrieve(String:start, String:end, String:granularity) - Retrieves all logs whose timestamps lie between start and end (inclusive) and have a granularity level of either "Year", "Month", "Day", "Hour", or "Minute".

To solve this problem, we can use a combination of data structures and algorithms to perform both the operations efficiently. One approach is to use a hash table to store the logs with their ids as the keys. We can also maintain a separate list of timestamps for each granularity level - year, month, day, hour, and minute - and store the corresponding log ids in each list based on their timestamps.

For example, for the log with timestamp = "2017:01:01:23:59:59", we can store its id in the following lists:

• Year: 2017
• Month: 2017-01
• Day: 2017-01-01
• Hour: 2017-01-01:23
• Minute: 2017-01-01:23:59

Now, let's see how we can implement the two operations:

1. addLog(id:integer, timestamp:string, content:string) - This operation involves adding a new log to the system. We can first parse the timestamp string to extract its year, month, day, hour, and minute values. Then, we can store the log id in each list corresponding to the granularity level of its timestamp. Finally, we can add the log to the hash table with its id as the key.

Here's the code for addLog operation:

private HashMap<Integer, String[]> logMap; // id -> [timestamp, content]
private HashMap<String, TreeSet<Integer>> yearMap; // year -> [id]
private HashMap<String, TreeSet<Integer>> monthMap; // year-month -> [id]
private HashMap<String, TreeSet<Integer>> dayMap; // year-month-day -> [id]
private HashMap<String, TreeSet<Integer>> hourMap; // year-month-day-hour -> [id]
private HashMap<String, TreeSet<Integer>> minuteMap; // year-month-day-hour-minute -> [id]

public LogSystem() {
    logMap = new HashMap<>();
    yearMap = new HashMap<>();
    monthMap = new HashMap<>();
    dayMap = new HashMap<>();
    hourMap = new HashMap<>();
    minuteMap = new HashMap<>();
}

public void addLog(int id, String timestamp, String content) {
    logMap.put(id, new String[]{timestamp, content});

    String[] timeParts = timestamp.split(":");
    String year = timeParts[0];
    String month = year + "-" + timeParts[1];
    String day = month + "-" + timeParts[2];
    String hour = day + "-" + timeParts[3];
    String minute = hour + "-" + timeParts[4];

    addToMap(year, id, yearMap);
    addToMap(month, id, monthMap);
    addToMap(day, id, dayMap);
    addToMap(hour, id, hourMap);
    addToMap(minute, id, minuteMap);
}

private void addToMap(String key, int id, HashMap<String, TreeSet<Integer>> map) {
    if (!map.containsKey(key)) {
        map.put(key, new TreeSet<>());
    }
    map.get(key).add(id);
}

2. retrieve(String:start, String:end, String:granularity) - This operation involves retrieving all logs whose timestamps lie between start and end (inclusive) and have a granularity level of either "Year", "Month", "Day", "Hour", or "Minute". To perform this operation efficiently, we can first build the appropriate key strings for start and end timestamps based on the given granularity level. Then, we can retrieve the log ids from the corresponding lists using the subSet() method of TreeSet. Finally, we can retrieve the log details from the hash table using their ids.

Here's the code for retrieve operation:

public List<Integer> retrieve(String start, String end, String granularity) {
    String startKey = getKey(start, granularity, true);
    String endKey = getKey(end, granularity, false);

    TreeSet<Integer> idSet = getIdSet(startKey, endKey, granularity);
    List<Integer> result = new ArrayList<>();
    for (int id : idSet) {
        result.add(id);
    }
    return result;
}

private String getKey(String timestamp, String granularity, boolean isStart) {
    String[] timeParts = timestamp.split(":");
    StringBuilder keyBuilder = new StringBuilder();
    switch (granularity) {
        case "Year":
            keyBuilder.append(timeParts[0]);
            if (isStart) {
                keyBuilder.append(":01:01:00:00:00");
            } else {
                keyBuilder.append(":12:31:23:59:59");
            }
            break;
        case "Month":
            keyBuilder.append(timeParts[0]).append(":").append(timeParts[1]);
            if (isStart) {
                keyBuilder.append(":01:00:00:00");
            } else {
                keyBuilder.append(":31:23:59:59");
            }
            break;
        case "Day":
            keyBuilder.append(timeParts[0]).append(":").append(timeParts[1]).append(":").append(timeParts[2]);
            if (isStart) {
                keyBuilder.append(":00:00:00");
            } else {
                keyBuilder.append(":23:59:59");
            }
            break;
        case "Hour":
            keyBuilder.append(timeParts[0]).append(":").append(timeParts[1]).append(":").append(timeParts[2]).append(":").append(timeParts[3]);
            if (isStart) {
                keyBuilder.append(":00:00");
            } else {
                keyBuilder.append(":59:59");
            }
            break;
        case "Minute":
            keyBuilder.append(timestamp);
            if (isStart) {
                keyBuilder.append(":00");
            } else {
                keyBuilder.append(":59");
            }
            break;
    }
    return keyBuilder.toString();
}

private TreeSet<Integer> getIdSet(String startKey, String endKey, String granularity) {
    switch (granularity) {
        case "Year":
            return getLogIds(yearMap, startKey, endKey);
        case "Month":
            return getLogIds(monthMap, startKey, endKey);
        case "Day":
            return getLogIds(dayMap, startKey, endKey);
        case "Hour":
            return getLogIds(hourMap, startKey, endKey);
        case "Minute":
            return getLogIds(minuteMap, startKey, endKey);
        default:
            return new TreeSet<>();
    }
}

private TreeSet<Integer> getLogIds(HashMap<String, TreeSet<Integer>> map, String startKey, String endKey) {
    TreeSet<Integer> idSet = new TreeSet<>();
    for (String key : map.keySet()) {
        if (key.compareTo(startKey) >= 0 && key.compareTo(endKey) <= 0) {
            idSet.addAll(map.get(key));
        }
    }
    return idSet;
}

With these two operations implemented, we now have a complete solution for the Design Log Storage System problem on Leetcode.

1