The "Design Log Storage System" problem from LeetCode asks you to implement a system that can store log entries, each with a unique id and a timestamp. The timestamps are formatted as Year:Month:Day:Hour:Minute:Second (e.g., "2017:01:01:23:59:59"). The system must support two operations:
id and timestamp.
ids of all logs whose timestamps fall within the range from start to end (inclusive), using the specified granularity (such as "Year", "Month", "Day", etc.).
The key constraints are:
id is unique.retrieve queries must respect the granularity by comparing only the relevant prefix of the timestamp.
The initial approach might be to store all logs in a list and, for each retrieve operation, scan through every log to check if its timestamp is in the given range. However, this brute-force method is inefficient, especially for large datasets.
To optimize, we should consider how timestamps are formatted: they are zero-padded and lexicographically sortable. This means we can compare timestamp strings directly, and the order will match chronological order. Furthermore, since granularity can vary, we only need to compare the relevant portion (prefix) of the timestamp.
For efficient retrieval, we might also consider sorting or using a data structure that supports range queries. However, since the problem does not require real-time performance and the number of logs is manageable, we can stick with a simple list and optimize the comparison logic.
Let's break down the solution step by step:
(timestamp, id) in a list.granularity (e.g., "Year", "Month", etc.) to the number of characters to consider in the timestamp. For example, "Year" maps to 4, "Month" to 7, and so on.(timestamp, id) pair to the list.start, end, and granularity, determine the prefix length.start and end.id in the result.This approach is simple, leverages the properties of the timestamp format, and is easy to implement.
Suppose we perform the following operations:
put(1, "2017:01:01:23:59:59")put(2, "2017:01:02:23:59:59")put(3, "2016:12:31:00:00:00")retrieve("2016:12:31:00:00:00", "2017:01:02:23:59:59", "Day")Step-by-step:
YYYY:MM:DD).
start_prefix = "2016:12:31", end_prefix = "2017:01:02"
"2017:01:01:23:59:59" → prefix "2017:01:01" (between start and end) → include id 1"2017:01:02:23:59:59" → prefix "2017:01:02" (equal to end) → include id 2"2016:12:31:00:00:00" → prefix "2016:12:31" (equal to start) → include id 3[1, 2, 3].
This demonstrates how the prefix-based comparison works for different granularities.
Brute-force Approach:
retrieve operation, we scan all n logs and compare prefixes. Thus, each query is O(n).
Overall, time complexity for put is O(1), for retrieve is O(n), and space complexity is O(n).
The solution to the "Design Log Storage System" problem leverages the lexicographical order of zero-padded timestamps, allowing us to compare prefixes for different granularities efficiently. By mapping granularities to prefix lengths, we can easily check if a log's timestamp falls within a specified range. The approach is simple, easy to implement, and efficient for the problem's constraints, making it an elegant solution for log storage and retrieval based on time ranges.
class LogSystem:
def __init__(self):
self.logs = []
self.gra_to_idx = {
"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, start: str, end: str, granularity: str) -> list:
idx = self.gra_to_idx[granularity]
start_prefix = start[:idx]
end_prefix = end[:idx]
res = []
for timestamp, id in self.logs:
if start_prefix <= timestamp[:idx] <= end_prefix:
res.append(id)
return res
class LogSystem {
vector<pair<string, int>> logs;
unordered_map<string, int> gra_to_idx = {
{"Year", 4},
{"Month", 7},
{"Day", 10},
{"Hour", 13},
{"Minute", 16},
{"Second", 19}
};
public:
LogSystem() {}
void put(int id, string timestamp) {
logs.push_back({timestamp, id});
}
vector<int> retrieve(string start, string end, string granularity) {
int idx = gra_to_idx[granularity];
string start_prefix = start.substr(0, idx);
string end_prefix = end.substr(0, idx);
vector<int> res;
for (auto &p : logs) {
string t_prefix = p.first.substr(0, idx);
if (start_prefix <= t_prefix && t_prefix <= end_prefix) {
res.push_back(p.second);
}
}
return res;
}
};
import java.util.*;
class LogSystem {
private List<Pair> logs;
private Map<String, Integer> graToIdx;
public LogSystem() {
logs = new ArrayList<>();
graToIdx = new HashMap<>();
graToIdx.put("Year", 4);
graToIdx.put("Month", 7);
graToIdx.put("Day", 10);
graToIdx.put("Hour", 13);
graToIdx.put("Minute", 16);
graToIdx.put("Second", 19);
}
public void put(int id, String timestamp) {
logs.add(new Pair(timestamp, id));
}
public List<Integer> retrieve(String start, String end, String granularity) {
int idx = graToIdx.get(granularity);
String startPrefix = start.substring(0, idx);
String endPrefix = end.substring(0, idx);
List<Integer> res = new ArrayList<>();
for (Pair p : logs) {
String tPrefix = p.timestamp.substring(0, idx);
if (startPrefix.compareTo(tPrefix) <= 0 && tPrefix.compareTo(endPrefix) <= 0) {
res.add(p.id);
}
}
return res;
}
private class Pair {
String timestamp;
int id;
Pair(String t, int i) {
this.timestamp = t;
this.id = i;
}
}
}
class LogSystem {
constructor() {
this.logs = [];
this.graToIdx = {
"Year": 4,
"Month": 7,
"Day": 10,
"Hour": 13,
"Minute": 16,
"Second": 19
};
}
put(id, timestamp) {
this.logs.push([timestamp, id]);
}
retrieve(start, end, granularity) {
const idx = this.graToIdx[granularity];
const startPrefix = start.slice(0, idx);
const endPrefix = end.slice(0, idx);
const res = [];
for (const [timestamp, id] of this.logs) {
const tPrefix = timestamp.slice(0, idx);
if (startPrefix <= tPrefix && tPrefix <= endPrefix) {
res.push(id);
}
}
return res;
}
}