447. Hit Counter
A web server logs every request together with the second it arrived. An operator wants to see how many requests were handled in the last five minutes, and the answer has to be available at any moment without rereading the whole log.
Implement HitCounter with a constructor that takes no arguments. hit(timestamp) records a request at the given second. getHits(timestamp) returns the number of requests recorded at seconds in the range (timestamp - 300, timestamp], that is the last 300 seconds ending at timestamp, with the current second included. The timestamps passed to all calls never decrease, and several requests may share the same second.
Example 1
- Input:
- operations = ["HitCounter","hit","hit","hit","getHits","getHits","getHits","hit","getHits"]arguments = [[],[20],[20],[150],[150],[319],[320],[330],[450]]
- Output:
- [null,null,null,null,3,3,1,null,1]
- Explanation:
At 150 all three hits count. At 319 the window is (19, 319], so all three remain. At 320 the window is (20, 320] and the two hits at second 20 are gone, leaving 1. At 450 the window (150, 450] keeps only the hit at 330.
Example 2
- Input:
- operations = ["HitCounter","getHits","hit","hit","getHits","getHits"]arguments = [[],[60],[61],[61],[360],[361]]
- Output:
- [null,0,null,null,2,0]
- Explanation:
No hit exists at 60, so the answer is 0. At 360 the window (60, 360] holds both hits at 61. At 361 the window (61, 361] holds none.
Constraints
1 ≤ timestamp ≤ 109
Timestamps over all calls are in non-decreasing order
At most 3 * 104 calls in total.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Input
- Each case is an operation log.
operationsnames the class first and then each method call;argumentsholds the arguments for each, in the same order. Your answer is one list with a result per operation -nullfor the constructor and for methods that return nothing.
Expected complexity
- Time
- O(1) amortized per call
- Space
- O(w)