Problem

The task is to design a hit counter which counts the number of hits received in the past 5 minutes. In this system, each function accepts a timestamp parameter in seconds granularity. The system receives calls in chronological order meaning the timestamp is monotonically increasing. However, it is possible to have several hits at roughly the same time.

For example, if the hit counter is initiated and receives hit at timestamps 1, 2, 3. If queried for the number of hits at timestamp 4, it should return 3.

Approach

The approach used to solve this task uses the concept of a circular buffer with the number of slots equivalent to the granularity of the time interval we're interested in. In this case, we choose a circular buffer with 300 slots, each representing 1 second inside a time frame of 5 minutes.

We map each time stamp to a specific slot in this buffer using the modulo operation. If the timestamp is the same as the one stored in the slot, we increment the count of hits in that slot. If it is different, it means we are currently in a new time frame and we need to reset the hit count to 1.

To get the total hits in the past 5 minutes at a specific timestamp, we traverse all slots and add up the hit counts in the slots where the timestamp stored in the slot is within the last 5 minutes.

Lastly, to handle a large number of hits per second, this design scales up well as the number of slots in the buffer remains constant at 300. The only increasing factor will be the hit count in each slot which can be accommodated as per the data type used.

Walkthrough

Let's walk through the example in the problem statement to better understand this approach:

• We have a hit counter and it receives hits at timestamps 1, 2, and 3. So, in the buffer, the slots mapped as 1, 2, and 3 now each contain a count of 1 and timestamp of their respective hits.

• Now, when queried for the number of hits at timestamp 4, the hit counter traverses each slot and finds that the timestamps 1, 2, and 3 are within the last 5 minutes of 4. So, it adds the hit counts in these slots and returns 3.

• The hit counter now receives a hit at timestamp 300. The slot mapped as 0 (300 modulo 300) is updated with hit count as 1 and timestamp as 300.

• When queried for the hits at timestamp 300, all slots within the last 5 minutes are added up and hence it returns 4 (1+1+1+1).

• Similarly, at timestamp 301, only slots with timestamps 3, 2, 1, and 300 are within the last 5 minutes. Hence, it returns 3.

Solution

Python Solution

1
2python
3class HitCounter:
4
5    def __init__(self):
6        self.times = [0]*300
7        self.hits = [0]*300
8
9    def hit(self, timestamp: int) -> None:
10        index = timestamp % 300
11        if self.times[index] != timestamp:
12            self.times[index] = timestamp
13            self.hits[index] = 1
14        else:
15            self.hits[index] += 1
16
17    def getHits(self, timestamp: int) -> int:
18        total = 0
19        for i in range(300):
20            if timestamp - self.times[i] < 300:
21                total += self.hits[i]
22        return total

Java Solution

1
2java
3public class HitCounter {
4    private int[] times;
5    private int[] hits;
6
7    public HitCounter() {
8        times = new int[300];
9        hits = new int[300];
10    }
11
12    public void hit(int timestamp) {
13        int index = timestamp % 300;
14        if (times[index] != timestamp) {
15            times[index] = timestamp;
16            hits[index] = 1;
17        } else {
18            hits[index]++;
19        }
20    }
21
22    public int getHits(int timestamp) {
23        int total = 0;
24        for (int i = 0; i < 300; i++) {
25            if (timestamp - times[i] < 300) {
26                total += hits[i];
27            }
28        }
29        return total;
30    }
31}

JavaScript Solution

1
2javascript
3class HitCounter {
4    constructor() {
5        this.times = new Array(300).fill(0);
6        this.hits = new Array(300).fill(0);
7    }
8
9    hit(timestamp) {
10        let index = timestamp % 300;
11        if (this.times[index] !== timestamp) {
12            this.times[index] = timestamp;
13            this.hits[index] = 1;
14        } else {
15            this.hits[index]++;
16        }
17    }
18
19    getHits(timestamp) {
20        let total = 0;
21        for (let i = 0; i < 300; i++) {
22            if (timestamp - this.times[i] < 300) {
23                total += this.hits[i];
24            }
25        }
26        return total;
27    }
28}

C++ Solution

1
2cpp
3class HitCounter {
4public:
5    HitCounter() {
6        times = vector<int>(300, 0);
7        hits = vector<int>(300, 0);
8    }
9
10    void hit(int timestamp) {
11        int index = timestamp % 300;
12        if (times[index] != timestamp) {
13            times[index] = timestamp;
14            hits[index] = 1;
15        } else {
16            hits[index]++;
17        }
18    }
19
20    int getHits(int timestamp) {
21        int total = 0;
22        for (int i = 0; i < 300; i++) {
23            if (timestamp - times[i] < 300) {
24                total += hits[i];
25            }
26        }
27        return total;
28    }
29private:
30    vector<int> times;
31    vector<int> hits;
32};

C# Solution

1
2csharp
3public class HitCounter {
4    private int[] times;
5    private int[] hits;
6
7    public HitCounter() {
8        times = new int[300];
9        hits = new int[300];
10    }
11
12    public void Hit(int timestamp) {
13        int index = timestamp % 300;
14        if (times[index] != timestamp) {
15            times[index] = timestamp;
16            hits[index] = 1;
17        } else {
18            hits[index]++;
19        }
20    }
21
22    public int GetHits(int timestamp) {
23        int total = 0;
24        for (int i = 0; i < 300; i++) {
25            if (timestamp - times[i] < 300) {
26                total += hits[i];
27            }
28        }
29        return total;
30    }
31}

Conclusion

The approach covered the usage of a circular buffer as a data structure for our hit counter. The timestamps received in each slot of the buffer were mapped using the % operator. And then iterating over the buffer within the specific time interval to return the total hits within the period.

This design is quite efficient as the buffer size remains constant at 300 regardless of the number of hits. It could handle a large number of hits per second. Therefore, it provides a scalable and performant solution for a hit counter system.

The solutions in Python, Java, JavaScript, C++ and C# followed the same concept and logic to solve the problem.

In the future, if you're tasked with designing a hit counter that needs to track hits over different granularities of time, such as minutes or hours, you can still utilize the same approach. You would need to adjust the size of the buffer and the mappings accordingly to fit the granularity and range desired.

Furthermore, the hit counter can be further optimized or extended by adding mechanisms to handle distributed hit counts, logging mechanisms to keep a more detailed record of the hits, dealing with collisions if the timestamp granularity is larger than the buffer size, and handling the case of not all hits being exactly in chronological order due to network delays or other technical issues.

The principles and design covered in this approach should serve as a good foundation for tackling these additional complexities.