⚡Flashcard Drill➔
NeetCode #167LC-635MediumArrays & Hashing
← Back to All Problems

#167 · #635 · Design Log Storage System(设计日志存储系统)

📌 Problem Statement & Constraints

Design a log storage system. put(id, timestamp) stores a log with a timestamp formatted as "Year:Month:Day:Hour:Minute:Second". retrieve(start, end, granularity) returns the ids of logs whose timestamp matches the range when truncated to the given granularity. Constraints: at most 500 logs and 500 calls.

💡 Core Algorithmic Approaches

  1. Store the logs as (id, timestamp) pairs without sorting; the small limits make linear scans acceptable.
  2. Each granularity corresponds to a fixed prefix length of the timestamp string: Year 4, Month 7, Day 10, Hour 13, Minute 16, Second 19.
  3. Truncate both the query bounds and each stored timestamp to that prefix and compare as strings -- lexicographic comparison of the fixed-format prefixes matches chronological order.
  4. Return the matching ids sorted.

💻 Benchmark Python3 Implementation

class LogSystem:
    def __init__(self):
        self.logs = []                     # (id, timestamp)

    def put(self, id: int, timestamp: str) -> None:
        self.logs.append((id, timestamp))

    def retrieve(self, start: str, end: str, granularity: str) -> List[int]:
        # prefix length for each granularity of "YYYY:MM:DD:HH:MM:SS"
        idx = {"Year": 4, "Month": 7, "Day": 10,
               "Hour": 13, "Minute": 16, "Second": 19}[granularity]
        s, e = start[:idx], end[:idx]
        return sorted(i for i, t in self.logs if s <= t[:idx] <= e)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(q * n) for q retrieve calls over n stored logs; the limits (500 and 500) make this trivial.
💾 Space Complexity
O(n) for the log list.

⚠️ Interview Pitfalls & Follow-ups

  • Comparing full timestamps regardless of granularity: a query at Year granularity must ignore month and later fields, hence the truncation.
  • Using the wrong prefix lengths: the separators count as characters, so Year is 4 and Month is 7 ("YYYY:MM"), not 5 and 6.
  • Sorting the stored logs by timestamp: unnecessary and does not help, since the granularity varies per query.
  • Parsing timestamps into numeric components: string prefix comparison is equivalent and much simpler given the fixed-width format.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems