Hit Counter

Moderate

0/80

Average time to solve is 15m

Contributed by

5 upvotes

Asked in companies

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

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

Sample Output 1:

0
1
2

Explanation of Sample Input 1:

For the first test case first call is done before any hit and the number of hits for the second call is 1.
For the second test case, 2 calls are done at a timestamp 1. At time stamps 301 all calls done at or after 1 are counted.

Sample Input 2:

Sample Output 2:

2
1
1

Hint 1

Can we store all the hits in a double-ended queue?

Approaches (1)

Approach 1

Deque

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’.

Time Complexity

O(N), where ‘N’ is the total number of calls.

Each timestamp is pushed and popped from deque utmost 1. Hence the complexity is of order O(N).

Space Complexity

O(N), where ‘N’ is the total number of calls.

The space complexity due to the dequeue is O(N).

(100% EXP penalty)

Hit Counter

Console