Design Log Storage System — Timestamp Range Retrieval

Problem Statement#

Design a log storage system with two operations: put(id, timestamp) stores a log with a string timestamp in format "2017:01:01:23:59:59"; retrieve(s, e, gra) returns all log IDs where the timestamp falls within [s, e] at the specified granularity. Granularity options: Year, Month, Day, Hour, Minute, Second.

Constraints:

• 1 <= id <= 500
• 2000 <= year <= 2017
• 1 <= s.length, e.length <= 19
• granularity is one of the six specified options
• At most 500 calls to put and retrieve

Input:  put(1,"2017:01:01:23:59:59"), put(2,"2017:01:01:22:59:59"),
        retrieve("2017:01:01:23:00:00","2017:01:01:23:59:59","Hour")
Output: [1, 2]

Input:  ... retrieve("2017:01:01:23:00:00","2017:01:01:23:59:59","Minute")
Output: [1]

Why This Problem Matters#

Log aggregation systems like AWS CloudWatch, Elasticsearch, and Splunk all support time-range queries at configurable granularities. A query like "show all errors in the last hour" is conceptually identical to this problem's retrieve operation. The key design insight—truncating timestamps to the granularity level and comparing as strings—maps directly to how time-series databases partition and index log data.

This problem appears in Amazon interviews because it tests your ability to model a real-world logging system with minimal complexity. The string comparison approach exploits the lexicographic ordering of ISO-format timestamps, which is a fundamental property used by databases like Cassandra and DynamoDB for range scans on timestamp primary keys.

Understanding when string comparison is equivalent to numeric comparison (as it is for zero-padded timestamps) is a valuable insight that generalises to many database indexing problems.

The Core Insight#

Map granularity names to prefix lengths: Year uses the first 4 characters ("2017"), Month uses 7 ("2017:01"), Day uses 10, Hour uses 13, Minute uses 16, Second uses 19 (the full string). Truncate the stored timestamp and the query bounds to the same prefix length, then compare as strings.

Since timestamps use zero-padded components in a fixed-width format, lexicographic string comparison is identical to numeric comparison at any prefix boundary. This means "2017:01" >= "2016:12" is true and correct without any numeric parsing.

The retrieve operation is O(N) per call (linear scan). For the problem's constraints, this is acceptable. Production systems use inverted indices or time-partitioned storage for sub-linear retrieval.

Visual Dry Run#

Solution (Optimal)#

class LogSystem:
    def __init__(self):
        self.logs = []
        self.gra_map = {
            'Year': 4, 'Month': 7, 'Day': 10,
            'Hour': 13, 'Minute': 16, 'Second': 19
        }
 
    def put(self, id: int, timestamp: str) -> None:
        self.logs.append((timestamp, id))
 
    def retrieve(self, s: str, e: str, gra: str) -> list:
        g = self.gra_map[gra]
        return [
            lid for ts, lid in self.logs
            if s[:g] <= ts[:g] <= e[:g]
        ]

class LogSystem {
    constructor() {
        this.logs = [];
        this.g = {
            Year: 4, Month: 7, Day: 10,
            Hour: 13, Minute: 16, Second: 19
        };
    }
 
    put(id, ts) {
        this.logs.push([ts, id]);
    }
 
    retrieve(s, e, gra) {
        const g = this.g[gra];
        return this.logs
            .filter(([ts]) => ts.slice(0, g) >= s.slice(0, g) && ts.slice(0, g) <= e.slice(0, g))
            .map(([, id]) => id);
    }
}

Time: O(N) per retrieve call — linear scan over all stored logs
Space: O(N) — one entry per put call

Common Mistakes#

• Using incorrect prefix lengths: Month is 7 not 6 (includes the separator: "2017:01"), Day is 10 not 8
• Off-by-one in prefix slicing: Python s[:4] gives 4 characters ("2017"), which is correct for Year
• Comparing full timestamps instead of truncated ones at the specified granularity—this gives Minute precision even when Year was requested
• Using < instead of <= for the boundary check: both start and end timestamps are inclusive
• Forgetting that the separator ":" is part of the format and contributes to prefix length counting

Interview Tips#

• Walk through the granularity map explicitly: draw a table of "Year=4, Month=7, Day=10..." before coding
• Explain WHY string comparison works: the timestamp format is zero-padded and colon-separated in fixed-width components, so lexicographic order equals chronological order at any prefix boundary
• For the production follow-up, mention time-partitioned indexes: Elasticsearch stores documents in daily indices, enabling O(1) range pruning at the Day granularity
• Mention that this is conceptually equivalent to querying WHERE timestamp BETWEEN s AND e in SQL with a time truncation function

Follow-up Questions#

• How would you make retrieval O(1) for a specific granularity? (Partition logs into separate buckets per granularity level at insert time)
• How would you handle continuous log ingestion at millions of entries per second? (Kafka for ingestion, time-partitioned storage in Elasticsearch or S3)
• How would you support deletion of logs older than N days? (Background compaction job that removes expired partitions by timestamp prefix)
• What if timestamps could arrive out of order? (Append with ingestion timestamp, but query using event timestamp—same logic applies)
• How would you support aggregation queries such as count logs per hour? (Pre-aggregate into time buckets at write time using a counter per time partition)

Key Takeaways#

• Map granularity names to prefix lengths: Year=4, Month=7, Day=10, Hour=13, Minute=16, Second=19
• Truncate timestamps using Python slice ts[:g] or JavaScript ts.slice(0, g) before comparing
• String comparison works correctly for ISO-format zero-padded timestamps because lexicographic order equals chronological order
• Both boundary timestamps are inclusive: use s[:g] <= ts[:g] <= e[:g]
• The separator ":" is included in prefix length counting—Month is 7 not 6 because "2017:01" has 7 characters
• This is an O(N) scan per retrieve; production systems use inverted time indexes for sub-linear retrieval
• The same prefix-truncation pattern is used in SQL DATE_TRUNC and Elasticsearch date histogram aggregations