We have to design a hit counter which can counts the number of hits received in a specified time interval. This method should also provide total number of hits received in the specified time interval.
Algorithm
- Define two array (timestamp and hitcounter) with size = time in seconds.
- Whenever there is a hit received.
- Check the timestamp array and current timestamp.
- If both are same
- Update hitcounter array with hits.
- Else
- Clear the exiting hit count from hitcounter array.
- Update the timestamp array with current timestamp.
- Update hitcounter array with hits.
- If both are same
- Check the timestamp array and current timestamp.
- Whenever total hits request received
- Iterate through hitcounter and timestamp array.
- If timestamp array contains timestamp which is out of count zone then ignore the hits.
- Else sum the hits.
- Return the sum.
- Iterate through hitcounter and timestamp array.
Implementation
Let’s look into the program implementation to understand it better.
#include <iostream>
#define TIME_PERIOD_IN_SECONDS 300
int timestamp[TIME_PERIOD_IN_SECONDS];
int hitcounter[TIME_PERIOD_IN_SECONDS];
void clear_hit_count (int time_stamp)
{
timestamp[time_stamp % TIME_PERIOD_IN_SECONDS] = time_stamp;
hitcounter[time_stamp % TIME_PERIOD_IN_SECONDS] = 0;
}
void increment_hit_count (int time_stamp, int count)
{
if (timestamp[time_stamp % TIME_PERIOD_IN_SECONDS] != time_stamp) {
clear_hit_count (time_stamp);
}
hitcounter[time_stamp % TIME_PERIOD_IN_SECONDS] += count;
}
int get_total_hits (int time_stamp)
{
int start_time = time_stamp - TIME_PERIOD_IN_SECONDS;
int total = 0;
for (int i = 0; i < TIME_PERIOD_IN_SECONDS; i++) {
if (start_time <= timestamp[i]) {
total += hitcounter[i];
}
}
return total;
}
int main ()
{
for (int i = 0; i < 5000; i++) {
if (rand () % 100 == 0) {
std::cout << "At time: " << i << " Total hitcount: " << get_total_hits (i) << std::endl;
}
increment_hit_count (i, rand () % 100);
}
}
Let’s look into the output of above program.
At time: 135 Total hitcount: 6246
At time: 210 Total hitcount: 10138
At time: 230 Total hitcount: 11138
At time: 262 Total hitcount: 12786
At time: 294 Total hitcount: 14705
At time: 420 Total hitcount: 14846
At time: 496 Total hitcount: 15143
At time: 525 Total hitcount: 15065
At time: 558 Total hitcount: 15325
At time: 648 Total hitcount: 14666
At time: 769 Total hitcount: 15264
At time: 787 Total hitcount: 15005
At time: 847 Total hitcount: 15167
At time: 901 Total hitcount: 15286
At time: 902 Total hitcount: 15236
At time: 929 Total hitcount: 14885
At time: 941 Total hitcount: 15027
At time: 1026 Total hitcount: 15292
At time: 1174 Total hitcount: 14394
At time: 1294 Total hitcount: 13708
At time: 1360 Total hitcount: 13924
At time: 1647 Total hitcount: 14394
At time: 2041 Total hitcount: 15659
At time: 2056 Total hitcount: 15621
At time: 2105 Total hitcount: 15152
At time: 2288 Total hitcount: 14470
At time: 2393 Total hitcount: 14832
At time: 2441 Total hitcount: 15039
At time: 2591 Total hitcount: 14343
At time: 2802 Total hitcount: 14951
At time: 2982 Total hitcount: 15367
At time: 3173 Total hitcount: 15120
At time: 3187 Total hitcount: 14845
At time: 3191 Total hitcount: 14778
At time: 3407 Total hitcount: 14465
At time: 3516 Total hitcount: 14621
At time: 3527 Total hitcount: 14636
At time: 3565 Total hitcount: 14955
At time: 3653 Total hitcount: 14867
At time: 3762 Total hitcount: 14732
At time: 3815 Total hitcount: 14832
At time: 3893 Total hitcount: 14720
At time: 3920 Total hitcount: 14760
At time: 4102 Total hitcount: 14656
At time: 4122 Total hitcount: 14565
At time: 4134 Total hitcount: 14607
At time: 4323 Total hitcount: 14714
At time: 4673 Total hitcount: 14604
At time: 4922 Total hitcount: 14213
At time: 4924 Total hitcount: 14297
At time: 4952 Total hitcount: 14544