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
- Store the logs as
(id, timestamp)pairs without sorting; the small limits make linear scans acceptable. - Each granularity corresponds to a fixed prefix length of the timestamp string: Year 4, Month 7, Day 10, Hour 13, Minute 16, Second 19.
- 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.
- 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
Yeargranularity 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.