Skip to main content
Talentd

Design Log Storage System - Solution & Explanation

MediumPremiumFree on FleetCodeHash TableStringDesignOrdered Set8 min readAsked at: Amazon, Apple, Snowflake +1
Practice this problem

Problem Statement

You are given several logs, where each log contains a unique ID and timestamp. Timestamp is a string that has the following format: Year:Month:Day:Hour:Minute:Second, for example, 2017:01:01:23:59:59. All domains are zero-padded decimal numbers.

Implement the LogSystem class:

  • LogSystem() Initializes the LogSystem object.
  • void put(int id, string timestamp) Stores the given log (id, timestamp) in your storage system.
  • int[] retrieve(string start, string end, string granularity) Returns the IDs of the logs whose timestamps are within the range from start to end inclusive. start and end all have the same format as timestamp, and granularity means how precise the range should be (i.e. to the exact Day, Minute, etc.). For example, start = "2017:01:01:23:59:59", end = "2017:01:02:23:59:59", and granularity = "Day" means that we need to find the logs within the inclusive range from Jan. 1st 2017 to Jan. 2nd 2017, and the Hour, Minute, and Second for each log entry can be ignored.

 

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 Overview

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.

Solution

Store the id and timestamp of the logs as tuples in an array. Then in the retrieve() method, truncate the corresponding parts of start and end based on granularity, and traverse the array, adding the id that meets the conditions to the result array.

In terms of time complexity, the time complexity of the put() method is O(1), and the time complexity of the retrieve() method is O(n), where n is the length of the array.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Log ScanO(n) per queryO(n)Small datasets or quick prototype where simplicity matters
String Comparison with Granularity MapO(n) per queryO(n)Best interview solution; leverages timestamp lexicographic order
Ordered Set / Sorted StructureO(log n + k)O(n)Frequent range queries where scanning all logs becomes expensive

Video Solution

Leetcode 635 - Design Log Storage System • Emerald Bay • 1,096 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Design Log Storage System easy or hard?
Design Log Storage System is considered a medium difficulty problem. The main challenge is recognizing that timestamp strings can be compared lexicographically and that granularity can be handled by truncating prefixes.
Design Log Storage System Python/Java solution
Python and Java implementations typically store logs in a list of pairs and use a dictionary that maps granularity to substring length. Retrieval slices timestamps using that length and compares them lexicographically within the start and end range.
How to solve Design Log Storage System in O(n)?
Store all logs as pairs of (id, timestamp). Maintain a map from granularity to substring length such as Year→4 and Minute→16. During retrieval, truncate the start, end, and stored timestamps to that length and include IDs whose prefixes fall within the lexicographic range.
What is the best approach for Design Log Storage System?
The most practical solution uses string comparison with a granularity-to-prefix-length mapping. Each timestamp is stored as a string, and retrieval compares only the substring relevant to the requested granularity. This avoids date parsing and keeps insertion O(1) and retrieval O(n).
Is Design Log Storage System asked at Google/Amazon/Meta?
Design-style problems involving logs, timestamps, and range queries frequently appear in interviews at companies like Amazon and Google. The problem tests string handling, range comparisons, and basic system design thinking.
What data structure is used in Design Log Storage System?
Most implementations store logs in a list or hash-based structure and rely on string comparisons for filtering. Some optimized solutions use ordered sets or balanced trees to support faster range queries.
What is the time complexity of Design Log Storage System?
Insertion runs in O(1) because the log entry is simply appended or stored. Retrieval typically runs in O(n) time because the algorithm scans all stored logs and performs substring comparisons. Space complexity is O(n) for storing the log entries.

Ready to solve this problem?

Practice Design Log Storage System with our built-in code editor and test cases.

Practice on FleetCode
Previous

Design In-Memory File System