Design Log Storage System

Problem Statement

In the presented scenario, you have been tasked with designing a system called LogSystem that efficiently handles time-based queries on logs. Each log in this system is characterized by a unique identifier and a timestamp formatted as Year:Month:Day:Hour:Minute:Second, where all numeric values are zero-padded to a standard length. The main functionalities of LogSystem include storing logs and retrieving logs based on a time range with varying granularity. Granularity in this context refers to the precision of the time range, which could be as broad as a year or as specific as a second. Thus, when retrieving logs, the system can ignore more specific time components based on the specified granularity, efficiently filtering logs that fall within the time bounds from start to end.

Examples

Example 1

Input:

["LogSystem", "put", "put", "put", "retrieve", "retrieve"]
[[], [1, "2017:01:01:23:59:59"], [2, "2017:01:01:22:59:59"], [3, "2016:01:01:00:00:00"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Year"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Hour"]]

Output:

[null, null, null, null, [3, 2, 1], [2, 1]]

Explanation:

LogSystem logSystem = new LogSystem();
logSystem.put(1, "2017:01:01:23:59:59");
logSystem.put(2, "2017:01:01:22:59:59");
logSystem.put(3, "2016:01:01:00:00:00");
// return [3,2,1], because you need to return all logs between 2016 and 2017.
logSystem.retrieve("2016:01:01:01:01:01", "2017:01:01:23:00:00", "Year");
// return [2,1], because you need to return all logs between Jan. 1, 2016 01:XX:XX and Jan. 1, 2017 23:XX:XX.
// Log 3 is not returned because Jan. 1, 2016 00:00:00 comes before the start of the range.
logSystem.retrieve("2016:01:01:01:01:01", "2017:01:01:23:00:00", "Hour");

Constraints

• 1 <= id <= 500
• 2000 <= Year <= 2017
• 1 <= Month <= 12
• 1 <= Day <= 31
• 0 <= Hour <= 23
• 0 <= Minute, Second <= 59
• granularity is one of the values ["Year", "Month", "Day", "Hour", "Minute", "Second"].
• At most 500 calls will be made to put and retrieve.

Approach and Intuition

Understanding the Structure and Execution

1. First, we will initialize the LogSystem to prepare it for accepting logs through the LogSystem() function.
2. Next, we will populate the system with logs using the put(id, timestamp) method, where each log is identified uniquely by an id and tagged with a timestamp.
3. Finally, the retrieval of logs based on certain criteria will be done through the retrieve(start, end, granularity) method. This method will filter logs based on their timestamps constrained by start, end, and the defined granularity.

How Granularity Impacts Range Queries

• For instance, if the granularity is set to "Day", the system ignores finer time details such as the hour, minute, or second of the logs. This means, for a start time of "2017:01:01:23:59:59" and an end time of "2017:01:02:23:59:59", all logs stamped on "2017:01:01" through "2017:01:02" regardless of the time of day will be considered.
• A different granularity, say "Minute", would consider logs up to the exact minute, making the range more precise and potentially reducing the number of logs retrieved.

Example Case Analysis

• In the example provided, the LogSystem object is first instantiated.
• Logs with IDs 1, 2, and 3 are stored with respective timestamps.
• When retrieved with a granularity of "Year", all logs between the years 2016 and 2017 are considered, which includes logs 1, 2, and 3.
• A subsequent retrieval with the granularity of "Hour" ignores logs outside the specific hour range but considers seconds and minutes, fetching logs 1 and 2 only, as they fall within the specified hourly bounds.

Handling Constraints

• Each ID in the system is unique and ranges from 1 to 500, ensuring a fixed limit on the possible number of logs.
• Timestamps are constrained between the years 2000 and 2017, and every other component of the timestamp (month, day, hour, minute, and second) falls within typical calendar and time bounds.
• These bounds and constraints ensure predictability in handling operations and guarantee that operations such as insertions (put) and queries (retrieve) remain efficient up to 500 operations.

Solutions

public class EventLogger {
    TreeMap<Long, Integer> eventMap;
        
    public EventLogger() {
        eventMap = new TreeMap<Long, Integer>();
    }
    
    public void storeEvent(int eventId, String timePoint) {
        int[] parsedTime = Arrays.stream(timePoint.split(":")).mapToInt(Integer::parseInt).toArray();
        eventMap.put(timeConverter(parsedTime), eventId);
    }
        
    public long timeConverter(int[] time) {
        time[1] = time[1] - (time[1] == 0 ? 0 : 1);
        time[2] = time[2] - (time[2] == 0 ? 0 : 1);
        return (time[0] - 1999L) * 31 * 12 * 24 * 60 * 60 + time[1] * 31 * 24 * 60 * 60 + time[2] * 24 * 60 * 60 + time[3] * 60 * 60 + time[4] * 60 + time[5];
    }
        
    public List<Integer> fetchEvents(String startTime, String endTime, String granularity) {
        ArrayList<Integer> result = new ArrayList<>();
        long start = adjustGranularity(startTime, granularity, false);
        long end = adjustGranularity(endTime, granularity, true);
        for (long key : eventMap.tailMap(start).keySet()) {
            if (key >= start && key < end)
                result.add(eventMap.get(key));
        }
        return result;
    }
    
    public long adjustGranularity(String time, String granularity, boolean isEnd) {
        HashMap<String, Integer> levels = new HashMap<>();
        levels.put("Year", 0);
        levels.put("Month", 1);
        levels.put("Day", 2);
        levels.put("Hour", 3);
        levels.put("Minute", 4);
        levels.put("Second", 5);
            
        String[] defaultTime = {"1999", "00", "00", "00", "00", "00"};
        String[] parts = time.split(":");
        for (int i = 0; i <= levels.get(granularity); i++) {
            defaultTime[i] = parts[i];
        }
        int[] timeComponents = Arrays.stream(defaultTime).mapToInt(Integer::parseInt).toArray();
        if (isEnd)
            timeComponents[levels.get(granularity)]++;
        return timeConverter(timeComponents);
    }
}