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 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.
Examples
Example 1:
|
|
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
.
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
- Store logs as a list of (id, timestamp) pairs.
- For each granularity, define the length of the substring to compare.
- For
put
, append the (id, timestamp) to the log list. - For
retrieve
, slice the start, end, and log timestamps up to the required granularity and compare. - Return the ids of logs within the range.
Code
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n)
per retrieve, wheren
is the number of logs. - 🧺 Space complexity:
O(n)
, for storing all logs.