Rolling Hit Counter
Learn this problem
DatabricksFULLTIMEPHONE SCREENProblem statement
Process an ordered sequence of operations for a rolling hit counter. 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 inclusive interval [t - 299, t]. Multiple hits at the same timestamp count separately. Operations with the same timestamp are processed in input order, so a hit is visible to a later query at that timestamp.
Return the query results in the order in which type-1 operations occur. If there are no queries, return an empty array.
Function
countRecentHits(operationTypes: int[], timestamps: int[]) → int[]Examples
Example 1
operationTypes = [0,0,0,1,0,1]timestamps = [1,2,3,4,300,301]return = [3,3]The query at time 4 counts the hits at times 1, 2, and 3. At time 301, the hit at time 1 is outside [2, 301], while the hits at times 2, 3, and 300 remain.
Example 2
operationTypes = [0,0,1,0,1]timestamps = [1,1,1,300,301]return = [2,1]The first query counts both hits at time 1. At time 301, those hits lie exactly outside the window, while the hit at time 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 time 400 is immediately visible to the later query at the same timestamp because operations are processed in input order.
Constraints
1 <= operationTypes.length = timestamps.length <= 100000.- Every operation type is
0or1. 1 <= timestamps[i] <= 2147483647.timestampsis nondecreasing.