635. Design Log Storage System π
Description
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 theLogSystem
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 fromstart
toend
inclusive.start
andend
all have the same format astimestamp
, andgranularity
means 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
, andSecond
for 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 <= 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 toput
andretrieve
.
Solutions
Solution 1: String Comparison
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 $O(1)$, and the time complexity of the retrieve()
method is $O(n)$, where $n$ is the length of the array.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
|
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
|
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
|