Problem Statement:


Design a hit counter which counts the number of hits received in the past 5 minutes (i.e., the past 300 seconds).

Your system should accept a timestamp parameter (in seconds granularity).

All the calls are being made to the system in chronological order, i.e., timestamp is monotonically increasing. Several hits may arrive roughly at the same time.

Implement the HitCounter class:
HitCounter() Initializes the object of the hit counter system.
void hit(int timestamp) Records a hit that happened at timestamp (in seconds). Several hits may happen at the same timestamp.
int getHits(int timestamp) Returns the number of hits in the past 5 minutes from timestamp (i.e., the past 300 seconds).

Example 1:
Input
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]
Output
[null, null, null, null, 3, null, 4, 3]
Explanation
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1); // hit at timestamp 1.
hitCounter.hit(2); // hit at timestamp 2.
hitCounter.hit(3); // hit at timestamp 3.
hitCounter.getHits(4); // get hits at timestamp 4, return 3.
hitCounter.hit(300); // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3.

Solution:



It may at first seem like solving this problem would require a lot of of complex system desigining knowledge, but being focused on what we are trying to achieve and by systematic thinking we would be able to come up with a simple yet elegant solution.

What we are trying to achieve is: to keep track of number of hits for every second for last 300 seconds, at any point of time. We can achieve this by keeping an array of size 300 to store hit counts for every seond for last 300 seconds. Let's say this array is hits[].

Since all the calls are being made to the system in chronological order, at any point of time we only need to keep data about last 300 seconds. We could discard the data for timestamps before that.

hit(timestamp) would increment the hit count for hits[i] where i represents time. The challenge lies how to reuse the indices in hits[] array of size 300. For hit(timestamo) we could use increment the hit count for hits[time % 300] and this way we can reuse the indices of hits[] array to for any timestamp whether timestamp < 300 or timestamp == 300 or timestamp > 300.

But when timestamp > 300 how would we know when hit(timestamp) is called for the first time. When timestamp <= 300, hits[timestamp] would be initialized to 0 so we can just go on incrementing hits[timestamp] whenever hits(timestamp) is called. But when timestamp > 300, hits[timestamp] could be non-zero even when hit(timestamp) is called for the first time, since we are reusing the indices of hits[] to accomodate for all timestamps.We could solve this problem by having another array timestamp[] of size 300 to store what timestamp an index of hits[] array is mapped to. If hits[i] is currently keeping hit count for timestamp = 500 then timestamp[i] = 500. We would know hit(i) is called for the first time if timestamp[i % 300] != i . We did (i % 300) since i could be greater than 300. When hit(i) is called for the first time for timestamp = i, we should set hits[i] = 1 and timestamp[i % 300] = i. From second invocation of hit(i) we just go on incementing value of hits[i % 300].

Let's look at the code below. That would make the whole approach described above super clear.


public class HitCounter {
    private int[] timestamp;
    private int[] hits;

    public HitCounter() {
        timestamp = new int[300];
        hits = new int[300];
    }

    public void hit(int time) { // time - The current time (in seconds granularity)
        int index = time % 300;
        if (timestamp[index] != time) {
            timestamp[index] = time;
            hits[index] = 1;
        } else {
            hits[index]++;
        }
    }
    
    public int getHits(int time) { // time - The current time (in seconds granularity)
        int total = 0;
        for (int i = 0; i < 300; i++) {
            if (time - timestamp[i] < 300) { // take value of hits[i] only if hits[i] was populated in last 300 seconds.
                                    // If hit() was not called for a certain timestamp in last
                                    // 300 seconds then we do not count them. This is important because for
                                    // timestamp > 300 hits[timestamp] could still be non-zero even if there was no hit for that specific
                                    // timestamp due to using mod and thereby reuse the indices.
                total += hits[i];
            }
        }
        return total;
    }
}





The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave