Last Updated: 10 Mar, 2021

Hit Counter

Moderate

Asked in companies

Solve now

Problem statement

You have to design a hit counter which supports the functionality of accepting a hit and returning the number of hits done in the last 5 minutes. Each call is made with a timestamp which is given in seconds.

It is possible to receive several hit arriving at the same time. All the calls are done in chronological order. The timestamp for a call is equal to or greater than the Timestamp for the call just before it. Timestamp at the start can be considered as 0.

For example:

The counter is hit at 'T'  = 1
The counter is hit at 'T' = 50
The getHit function at 'T' = 100 returns 2
The counter is hit at 'T' = 250
The getHit function at 'T' = 100 returns 2

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains a single integer ‘N’, denoting the number of calls.

The next ‘N’ lines contain two space-separated integers ‘TYPE’, ‘STAMP’ denoting the type of the call and timestamp when this call was made.  
If TYPE = 1 it is a hit call, TYPE = 2 it is a getHit call .

Output Format:

For each test case, for all the calls of the second type RETURN the number of hits in the last 5 minutes.

Note:

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 5 * 10^3
1 <= STAMP <= 10 ^ 9

It is guaranteed that all calls are done in chronological order. 

Time Limit: 1 sec

Solve now

Approaches

01 Approach

We will create a double-ended queue to store all the hits. When we want to store a hit in the queue we will store it in the front of the queue. When we want to get the number of hits we will consider the hits from the rare end, compare their timestamp with the timestamp of the current call.

The algorithm will be-

Create a deque ‘DQ’ to store the timestamp of hits.
If ‘TYPE’ == 1 :
1. ‘DQ.pushrear(STAMP)'
Else:
1. While len('DQ') > 0 and DQ.front() < STAMP - 5 * (60) :
  1. DQ.popfront()
2. Print length of ‘DQ’.

Solve now