# Design Hit Counter

• Write a hit counter for hits received in the past 5 minutes.

The HitCounter has two methods:

``````void hit()   // record a hit.

long getHits()   // Return the number of hits in the last 5 minutes.
``````

• can you specify what is the maximum load of the counter? How many hits per second? Probably to fit in long ?

• @elmirap Yes you can assume it fits in long.

• @1337c0d3r I was thinking the same way as it was suggested in the design topic you offer us

• Here is a suggestion. I assume that we use granularity second.ArrayDeque (thanks to @diptesh for the remind) is used, in which each element is time slot which corresponds to different seconds, when hit arrive. When hit arrives or information about it is looked for , list is resized according to the time.

``````
public class HitCounter {
private final int WINDOW_SIZE = 300;
class TimeSlot {
public TimeSlot(long t) {
time = t;
hits = 1;

}
private long time;
private long hits;
}

private long hits;
private long time;

private Deque<TimeSlot> slots = new ArrayDeque<>(WINDOW_SIZE * 60);

HitCounter() {
time = System.currentTimeMillis()/1000;
}
private   void resize(long current) {
long before = current - WINDOW_SIZE;
while (slots.size() > 0 && slots.getFirst().time < before) {
hits -= slots.removeFirst().hits;
}
if (slots.size() == 0) {

}
time = slots.getFirst().time;

}
public void hit() {
long current = System.currentTimeMillis()/1000;
if (time < current - WINDOW_SIZE)  {
resize(current);
}
else {
if (slots.size() > 0 && slots.getLast().time == time) {
slots.getLast().hits++;
} else {
}
}
hits++;
}

public long getHits() {
long current = System.currentTimeMillis()/1000;
if (time < current - WINDOW_SIZE)
resize(current);
return hits;
}
}``````

• @elmirap why not use ArrayDeque, instead of LinkedList. We get significant performance gain in ArrayDeque as compared to LinkedList.

• @diptesh yes , good observation, I will edit implementation

• @elmirap Great solution.

I modified to use HashMap instead .

``````Map<Long, Long> map = new HashMap<Long, Long>();
Long hits = 0L, earliestTime = 0L;
int SLOTS = 300 * 60;
public void logHits(long time) { // time in seconds
if(map.containsKey(time)) {
map.put(time, map.get(time)+1);
}else {
map.put(time, 1L);
}
cleanUp(time);
hits++;
}

public Long getHits(long time) { // time in seconds
cleanUp(time);
return hits;
}

public void cleanUp(long time) {
while(time - earliestTime >= SLOTS) {
if(map.containsKey(earliestTime)) {
hits -= map.get(earliestTime);
map.remove(earliestTime);
}
earliestTime = earliestTime + 1;
}
}``````

• @andyreadsall , problem could be solved with maps, beacause we have only 300 entries (not so much)

• C++ implementation using std::deque

``````#include<deque>
#include<iostream>
#include<chrono>
#include<string>

using namespace std;

class HitCounter {
private:
typedef std::chrono::time_point<std::chrono::system_clock> hittime_t;
struct _HitBucket {
hittime_t timestamp;
long hits = 0;
_HitBucket() { timestamp = std::chrono::system_clock::now(); }
};
typedef struct _HitBucket hitbkt_t;
deque<hitbkt_t> mBuckets;
chrono::duration<unsigned> mDepth;
long hits = 0;
public:
HitCounter(const unsigned size, const string name=""): mDepth{size} {};

long getHits(void) { return hits; }

void hit(void) {
hittime_t now = std::chrono::system_clock::now();

if(mBuckets.empty() or mBuckets.front().timestamp != now) {
mBuckets.push_front(hitbkt_t());
}
mBuckets.front().hits++;
hits ++;
while(now - mBuckets.back().timestamp > mDepth) {
hits -= mBuckets.back().hits;
mBuckets.pop_back();
}
}
};
int main() {
HitCounter hc10(10);
HitCounter hc20(20);

for(int i=0; i<40; i++) {
for(int h=0; h<i; h++) {
hc10.hit();
hc20.hit();
}
cout << i << " hc10 " << hc10.getHits() << " ";
cout << i << " hc20 " << hc20.getHits() << endl;
}
}

``````

• Using a dictionary that holds counts in each second for 300 seconds (keys).

``````import time

class HitCounter(object):
def __init__(self, size):
self.size = size
self.hit_counts = {}
self.count = 0

def _prune_hit_counts(self):
t = time.time()
t_cutoff = t - self.size
for t_hit in self.hit_counts.keys():
if t_hit < t_cutoff:
self.count -= self.hit_counts[t_hit]
self.hit_counts[t_hit] = 0

def log_hit(self):
t = time.time()
if t in self.hit_counts:
self.hit_counts[t] += 1
else:
self.hit_counts[t] = 1
self.count += 1
self._prune_hit_counts()

def get_hit(self):
t = time.time()
self._prune_hit_counts()

return self.count

# driver
HIT = 10
WAIT = 5
hc = HitCounter(HIT)

print('Hitting once a second for {} seconds...'.format(HIT))
for _ in range(HIT):
hc.log_hit()
print(hc.get_hit())
time.sleep(1)
for _ in range(WAIT):
print('Waiting...')
time.sleep(1)

print(hc.get_hit())     # HIT - WAIT - 1
time.sleep(1)
print(hc.get_hit())     # HIT - WAIT - 2
print('End')
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.