Recent Hit Counter
Learn this problem
Amazon Web ServicesNEW GRADONSITE INTERVIEWProblem statement
Simulate a hit counter over a finite ordered operation sequence. Each operation has a type and an integer timestamp:
- Type
0records one hit at that timestamp. - Type
1queries how many recorded hits occurred during the trailing 300 seconds.
For a query at timestamp t, count hits whose timestamps are in the interval (t - 300, t]. Multiple hits at the same timestamp count separately.
Return the query results in the order in which type-1 operations occur.
Function
countRecentHits(operationTypes: int[], timestamps: int[]) → int[]Examples
Example 1
operationTypes = [0,0,0,1,1]timestamps = [1,2,3,4,300]return = [3,3]At timestamp 4, all three hits are recent. At timestamp 300, the hit at timestamp 1 is still inside (0, 300], so the count remains 3.
Example 2
operationTypes = [0,0,1,0,1]timestamps = [1,1,1,300,301]return = [2,1]The first query counts both hits at timestamp 1. At timestamp 301, those hits lie exactly on the excluded left boundary, while the hit at timestamp 300 remains.
Example 3
operationTypes = [1,0,1]timestamps = [100,400,400]return = [0,1]The first query occurs before any hit. The hit recorded at timestamp 400 is immediately visible to the following query at the same timestamp.
Constraints
1 ≤ operationTypes.length = timestamps.length ≤ 200000.- Every operation type is
0or1. 1 ≤ timestamps[i] ≤ 10^9.timestampsis nondecreasing.