Problem

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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

**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.

Solution

Method 1 – String Slicing and Linear Scan

Intuition

Timestamps are fixed-length strings, so we can use string slicing to compare up to the required granularity. For each retrieve, we slice the timestamps and compare them lexicographically.

Approach

  1. Store logs as a list of (id, timestamp) pairs.
  2. For each granularity, define the length of the substring to compare.
  3. For put, append the (id, timestamp) to the log list.
  4. For retrieve, slice the start, end, and log timestamps up to the required granularity and compare.
  5. Return the ids of logs within the range.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class LogSystem {
    vector<pair<int, string>> logs;
    unordered_map<string, int> g2idx = {
        {"Year", 4}, {"Month", 7}, {"Day", 10}, {"Hour", 13}, {"Minute", 16}, {"Second", 19}
    };
public:
    LogSystem() {}
    void put(int id, string timestamp) {
        logs.push_back({id, timestamp});
    }
    vector<int> retrieve(string start, string end, string granularity) {
        int k = g2idx[granularity];
        vector<int> ans;
        for (auto& [id, t] : logs) {
            if (t.substr(0, k) >= start.substr(0, k) && t.substr(0, k) <= end.substr(0, k))
                ans.push_back(id);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

type LogSystem struct {
    logs [][2]interface{}
}
var g2idx = map[string]int{
    "Year": 4, "Month": 7, "Day": 10, "Hour": 13, "Minute": 16, "Second": 19,
}
func Constructor() LogSystem {
    return LogSystem{}
}
func (ls *LogSystem) Put(id int, timestamp string) {
    ls.logs = append(ls.logs, [2]interface{}{id, timestamp})
}
func (ls *LogSystem) Retrieve(start, end, granularity string) []int {
    k := g2idx[granularity]
    ans := []int{}
    for _, log := range ls.logs {
        t := log[1].(string)
        if t[:k] >= start[:k] && t[:k] <= end[:k] {
            ans = append(ans, log[0].(int))
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class LogSystem {
    private List<int[]> logs = new ArrayList<>();
    private List<String> times = new ArrayList<>();
    private static final Map<String, Integer> g2idx = Map.of(
        "Year", 4, "Month", 7, "Day", 10, "Hour", 13, "Minute", 16, "Second", 19
    );
    public LogSystem() {}
    public void put(int id, String timestamp) {
        logs.add(new int[]{id, times.size()});
        times.add(timestamp);
    }
    public List<Integer> retrieve(String start, String end, String granularity) {
        int k = g2idx.get(granularity);
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < logs.size(); ++i) {
            String t = times.get(logs.get(i)[1]);
            if (t.substring(0, k).compareTo(start.substring(0, k)) >= 0 &&
                t.substring(0, k).compareTo(end.substring(0, k)) <= 0) {
                ans.add(logs.get(i)[0]);
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class LogSystem {
    private val logs = mutableListOf<Pair<Int, String>>()
    private val g2idx = mapOf(
        "Year" to 4, "Month" to 7, "Day" to 10, "Hour" to 13, "Minute" to 16, "Second" to 19
    )
    fun put(id: Int, timestamp: String) {
        logs.add(id to timestamp)
    }
    fun retrieve(start: String, end: String, granularity: String): List<Int> {
        val k = g2idx[granularity]!!
        return logs.filter { it.second.substring(0, k) >= start.substring(0, k) && it.second.substring(0, k) <= end.substring(0, k) }
            .map { it.first }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class LogSystem:
    def __init__(self):
        self.logs: list[tuple[int, str]] = []
        self.g2idx = {
            'Year': 4, 'Month': 7, 'Day': 10, 'Hour': 13, 'Minute': 16, 'Second': 19
        }
    def put(self, id: int, timestamp: str) -> None:
        self.logs.append((id, timestamp))
    def retrieve(self, start: str, end: str, granularity: str) -> list[int]:
        k = self.g2idx[granularity]
        return [id for id, t in self.logs if start[:k] <= t[:k] <= end[:k]]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

use std::collections::HashMap;
struct LogSystem {
    logs: Vec<(i32, String)>,
    g2idx: HashMap<&'static str, usize>,
}
impl LogSystem {
    fn new() -> Self {
        let mut g2idx = HashMap::new();
        g2idx.insert("Year", 4);
        g2idx.insert("Month", 7);
        g2idx.insert("Day", 10);
        g2idx.insert("Hour", 13);
        g2idx.insert("Minute", 16);
        g2idx.insert("Second", 19);
        Self { logs: vec![], g2idx }
    }
    fn put(&mut self, id: i32, timestamp: String) {
        self.logs.push((id, timestamp));
    }
    fn retrieve(&self, start: &str, end: &str, granularity: &str) -> Vec<i32> {
        let k = *self.g2idx.get(granularity).unwrap();
        self.logs.iter().filter_map(|(id, t)| {
            if &t[..k] >= &start[..k] && &t[..k] <= &end[..k] { Some(*id) } else { None }
        }).collect()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class LogSystem {
    private logs: [number, string][] = [];
    private g2idx: Record<string, number> = {
        Year: 4, Month: 7, Day: 10, Hour: 13, Minute: 16, Second: 19
    };
    put(id: number, timestamp: string): void {
        this.logs.push([id, timestamp]);
    }
    retrieve(start: string, end: string, granularity: string): number[] {
        const k = this.g2idx[granularity];
        return this.logs.filter(([id, t]) => t.slice(0, k) >= start.slice(0, k) && t.slice(0, k) <= end.slice(0, k)).map(([id]) => id);
    }
}

Complexity

  • ⏰ Time complexity: O(n) per retrieve, where n is the number of logs.
  • 🧺 Space complexity: O(n), for storing all logs.