| comments | difficulty | edit_url | tags | ||||
|---|---|---|---|---|---|---|---|
true |
Medium |
|
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 theLogSystemobject.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 fromstarttoendinclusive.startandendall have the same format astimestamp, andgranularitymeans how precise the range should be (i.e. to the exactDay,Minute, etc.). For example,start = "2017:01:01:23:59:59",end = "2017:01:02:23:59:59", andgranularity = "Day"means that we need to find the logs within the inclusive range from Jan. 1st 2017 to Jan. 2nd 2017, and theHour,Minute, andSecondfor each log entry can be ignored.
Example 1:
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 <= 5002000 <= Year <= 20171 <= Month <= 121 <= Day <= 310 <= Hour <= 230 <= Minute, Second <= 59granularityis one of the values["Year", "Month", "Day", "Hour", "Minute", "Second"].- At most
500calls will be made toputandretrieve.
Store the id and timestamp of the logs as tuples in an array. Then in the retrieve() method, truncate the corresponding parts of start and end based on granularity, and traverse the array, adding the id that meets the conditions to the result array.
In terms of time complexity, the time complexity of the put() method is retrieve() method is
class LogSystem:
def __init__(self):
self.logs = []
self.d = {
"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]:
i = self.d[granularity]
return [id for id, ts in self.logs if start[:i] <= ts[:i] <= end[:i]]
# Your LogSystem object will be instantiated and called as such:
# obj = LogSystem()
# obj.put(id,timestamp)
# param_2 = obj.retrieve(start,end,granularity)class LogSystem {
private List<Log> logs = new ArrayList<>();
private Map<String, Integer> d = new HashMap<>();
public LogSystem() {
d.put("Year", 4);
d.put("Month", 7);
d.put("Day", 10);
d.put("Hour", 13);
d.put("Minute", 16);
d.put("Second", 19);
}
public void put(int id, String timestamp) {
logs.add(new Log(id, timestamp));
}
public List<Integer> retrieve(String start, String end, String granularity) {
List<Integer> ans = new ArrayList<>();
int i = d.get(granularity);
String s = start.substring(0, i);
String e = end.substring(0, i);
for (var log : logs) {
String t = log.ts.substring(0, i);
if (s.compareTo(t) <= 0 && t.compareTo(e) <= 0) {
ans.add(log.id);
}
}
return ans;
}
}
class Log {
int id;
String ts;
Log(int id, String ts) {
this.id = id;
this.ts = ts;
}
}
/**
* Your LogSystem object will be instantiated and called as such:
* LogSystem obj = new LogSystem();
* obj.put(id,timestamp);
* List<Integer> param_2 = obj.retrieve(start,end,granularity);
*/class LogSystem {
public:
LogSystem() {
d["Year"] = 4;
d["Month"] = 7;
d["Day"] = 10;
d["Hour"] = 13;
d["Minute"] = 16;
d["Second"] = 19;
}
void put(int id, string timestamp) {
logs.push_back({id, timestamp});
}
vector<int> retrieve(string start, string end, string granularity) {
vector<int> ans;
int i = d[granularity];
auto s = start.substr(0, i);
auto e = end.substr(0, i);
for (auto& [id, ts] : logs) {
auto t = ts.substr(0, i);
if (s <= t && t <= e) {
ans.emplace_back(id);
}
}
return ans;
}
private:
vector<pair<int, string>> logs;
unordered_map<string, int> d;
};
/**
* Your LogSystem object will be instantiated and called as such:
* LogSystem* obj = new LogSystem();
* obj->put(id,timestamp);
* vector<int> param_2 = obj->retrieve(start,end,granularity);
*/type LogSystem struct {
logs []pair
d map[string]int
}
func Constructor() LogSystem {
d := map[string]int{
"Year": 4,
"Month": 7,
"Day": 10,
"Hour": 13,
"Minute": 16,
"Second": 19,
}
return LogSystem{[]pair{}, d}
}
func (this *LogSystem) Put(id int, timestamp string) {
this.logs = append(this.logs, pair{id, timestamp})
}
func (this *LogSystem) Retrieve(start string, end string, granularity string) (ans []int) {
i := this.d[granularity]
s, e := start[:i], end[:i]
for _, log := range this.logs {
t := log.ts[:i]
if s <= t && t <= e {
ans = append(ans, log.id)
}
}
return
}
type pair struct {
id int
ts string
}
/**
* Your LogSystem object will be instantiated and called as such:
* obj := Constructor();
* obj.Put(id,timestamp);
* param_2 := obj.Retrieve(start,end,granularity);
*/