[Google Question][LeetCode] Design Hit Counter

Problem: Design a hit counter which counts the number of hits received in the past 5 minutes.

Each function accepts a timestamp parameter (in seconds granularity) and you may assume that calls are being made to the system in chronological order (i.e. the timestamp is monotonically increasing). You may assume that the earliest timestamp starts at 1.

It is possible that several hits arrive roughly at the same time i.e. the number of hits per second could be very large.

Example:

HitCounter counter = new HitCounter();

// hit at timestamp 1.
counter.hit(1);

// hit at timestamp 2.
counter.hit(2);

// hit at timestamp 3.
counter.hit(3);

// get hits at timestamp 4, should return 3.
counter.getHits(4);

// hit at timestamp 300.
counter.hit(300);

// get hits at timestamp 300, should return 4.
counter.getHits(300);

// get hits at timestamp 301, should return 3.
counter.getHits(301); 

Approach: Given that the timestamps are coming in a sorted order, we can use queue here as whenever we want to remove, we want to remove which were added first. With queue our approach will look like:

hit(timestamp):

• queue.Enqueue(timestamp)

getHits(timestamp):

• WHILE queue not empty AND timestamp - queue.Front >= 0
• queue.Dequeue();
• RETURN queue.Count

This will work fine but we need to consider that case where "the number of hits per second could be very large" so we might end up storing same timestamp multiple times. To reduce the space and hence time, what we can do is, we will store a key-value pair instead of just timestamp. Here key will be the timestamp and value will be the number of occurrences of the key timestamp.

Now whenever we get the same timestamp as the last one, we just increment its count but in a Queue, we can't access and remove the element from back so we are going to use Dequeue here. With Dequeue, the approach will look like:

hit(timestamp):

• count = 1
• IF dequeue not empty and dequeue.Back.Key == timestamp
• count += dequeue.Back.Value;
• dequeue.RemoveBack()
• dequeue.Add({timestamp => count})
• TotalCount = TotalCount + 1

getHits(timestamp):

• WHILE dequeue not empty AND timestamp - dequeue.Front.Key >= 300
• TotalCount = TotalCount - dequeue.Front.Value
• dequeue.RemoveFront()
•  return TotalCount

 That's all!

Implementation in C#:

public class HitCounter 

{

    public HitCounter() 

    {

        this.hitsList = new LinkedList<KeyValuePair<int, int>>();    

    }

    

    public void Hit(int timestamp) 

    {

        int count = 1;

        if (this.hitsList.Count > 0 && this.hitsList.Last.Value.Key == timestamp)

        {

            count += this.hitsList.Last.Value.Value;

            this.hitsList.RemoveLast();

        }

        this.hitsList.AddLast(new KeyValuePair<int, int>(timestamp, count));

        ++this.totalHits;

    }

    

    public int GetHits(int timestamp) 

    {

        while (this.hitsList.Count > 0  && timestamp - this.hitsList.First.Value.Key >= 300)

        {

            this.totalHits -= this.hitsList.First.Value.Value;

            this.hitsList.RemoveFirst();

        }

        return this.totalHits;

    }

    

    private LinkedList<KeyValuePair<int, int>> hitsList;

    private int totalHits = 0;

}

Complexity: hit: O(1), getHits: O(n)