Design Log Storage System - Solution & Explanation

Problem Overview: You need to design a system that stores log entries with an id and a timestamp formatted as YYYY:MM:DD:HH:MM:SS. The system must support inserting logs and retrieving all log IDs between a start and end timestamp based on a specified granularity such as Year, Month, Day, Hour, Minute, or Second.

Approach 1: Brute Force Scan (O(n) time per query, O(n) space)

The most direct implementation stores every log in a list or array. When a retrieve request arrives, iterate through every stored log and check whether its timestamp falls within the requested range. To respect granularity, truncate both the stored timestamp and the query boundaries to the required prefix length. For example, if the granularity is Day, compare only the first 10 characters (YYYY:MM:DD). This approach relies on simple string comparisons and works because timestamps are lexicographically ordered. The downside is that every query scans all logs, resulting in O(n) time.

Approach 2: String Comparison with Granularity Mapping (O(n) time per query, O(n) space)

A cleaner implementation maps each granularity to the substring length that represents it: Year → 4, Month → 7, Day → 10, Hour → 13, Minute → 16, Second → 19. During retrieval, slice the start time, end time, and each stored timestamp to that prefix length and perform lexicographic comparisons. Because the timestamp format is fixed and zero‑padded, string ordering naturally matches chronological ordering. This avoids parsing dates or converting to integers. Insert operations run in O(1), while retrieval iterates over all logs in O(n) time. The implementation mainly uses string operations and simple storage, often backed by a hash table or list.

Approach 3: Ordered Set / Sorted Structure (O(log n + k) query, O(n) space)

If retrieval happens frequently, store logs in a sorted structure such as a TreeMap, OrderedSet, or sorted list keyed by timestamp. Convert the start and end timestamps according to the requested granularity and perform a range query. This allows binary search or tree traversal to locate the first valid timestamp in O(log n) time, then collect matching logs. The approach reduces scanning but increases insertion overhead. It relies on ordered data structures commonly discussed under system design problems.

Recommended for interviews: The string comparison approach is what most interviewers expect. It leverages the lexicographic ordering of timestamps and keeps the implementation simple. Showing the brute force scan first demonstrates understanding of the problem, but using substring comparison with a granularity map shows you recognize the structure of the timestamp and can design a clean, efficient solution.