Algorithmic: Design a hit counter

Designing a hit counter is common interviews questions. I know that Dropbox, Amazon, Datadog, Microsoft use it in their recruitment process.

You will find a question like this one :

Design a hit counter which counts the number of requests received in the past 2 minutes.

At first sight, it seems simple. But it includes a couple of topics like basic data structures design, various optimization, concurrency, and distributed counter.

In this article, we will use java, but you can transpose it to your favorite language.

So what a hit counter should do?
It should increment hits every time we have a new request, and we should get the number of hits during the period.

We will implement 2 methods:

• hit(final long timestamp): increment a new hit.
• getHits(): count the number of hits during the period.

Bellow, there is an example who explains how it should work.

// HitCounter keep the last 2 minutes.
HitCounter counter = new HitCounter();
counter.hit(1); // hit at timestamp 1.
counter.hit(2); // hit at timestamp 2.
counter.hit(3); // hit at timestamp 3…