# Hit Counter

Posted: 10 Mar, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### 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
`````` Approach 1

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-

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