Design Log Storage System
Medium · Design · Design · Hash Table · String · Ordered Set
Problem
Build a small log store that answers time-range questions at a chosen precision.
Each log has an integer id and a timestamp written Year:Month:Day:Hour:Minute:Second, every field zero-padded, for example "2017:01:01:23:59:59".
- LogSystem(): start with an empty store
- put(id, timestamp): save one log
- retrieve(start, end, granularity): return the ids of every saved log whose timestamp falls between start and end, both inclusive, once all three are cut down to granularity
granularity is one of "Year", "Month", "Day", "Hour", "Minute", "Second". Every field finer than it is ignored, on the bounds and on the logs alike. With "Day", start = "2017:01:01:23:59:59" and end = "2017:01:02:23:59:59" mean all of January 1 and 2, 2017, at any hour.
Return the ids in any order. Ids are unique; two logs may share a timestamp.
Your tests replay a call sequence: the first entry names the class, each later entry is a method with its arguments, and calls returning nothing report None.
Examples
Input: put(1, "2017:01:01:23:59:59"), put(2, "2017:01:01:22:59:59"), put(3, "2016:01:01:00:00:00"), retrieve("2016:01:01:01:01:01", "2017:01:01:23:00:00", "Year"), retrieve("2016:01:01:01:01:01", "2017:01:01:23:00:00", "Hour")
Output: [3,2,1], then [2,1]At Year precision the range is all of 2016 and 2017, so every log matches. At Hour precision it runs from Jan 1, 2016 01:xx to Jan 1, 2017 23:xx: log 3 (hour 00 of Jan 1, 2016) is too early.
Input: put(1, "2017:01:01:23:59:59"), put(2, "2017:01:02:00:00:00"), retrieve("2017:01:01:23:59:59", "2017:01:01:23:59:59", "Second"), retrieve("2017:01:31:00:00:00", "2017:01:01:00:00:00", "Month")
Output: [1], then [1,2]Equal bounds at Second precision match one exact instant. At Month precision both bounds become 2017:01, so the start being later in the month than the end no longer matters.
Constraints
- 1 <= id <= 500, and ids are unique
- 2000 <= Year <= 2017, 1 <= Month <= 12, 1 <= Day <= 31
- 0 <= Hour <= 23, 0 <= Minute, Second <= 59
- granularity is one of Year, Month, Day, Hour, Minute, Second
- At most 500 calls to put and retrieve; the stress tests go well past that to show what an index buys
Approaches
- Scan every log, comparing timestamp prefixes — time O(1) put, O(n) retrieve, space O(n)
Follow-up
What if the store holds millions of logs and most calls are retrieves? And what if logs arrive from servers in different time zones? A sorted index (a balanced tree or a B-tree, as a database would use) turns each query into two binary searches plus the ids it returns. Time zones must be normalized to UTC before storing: the string trick only orders stamps written on the same clock.
Related problems
Start free on Cariara · Coding problems · System design studio
