Design Hit Counter

Design Hit Counter

1. What is this problem about?

The Design Hit Counter interview question asks you to build a system that counts hits (events) received in the past 5 minutes (300 seconds). You need to implement hit(timestamp) and getHits(timestamp). This Design Hit Counter coding problem is a time-series aggregation task that requires efficiently discarding old data as time moves forward.

2. Why is this asked in interviews?

Reddit and Apple use this question to test your mastery of Data Stream interview patterns and Queue interview patterns. It evaluates how you handle data that "expires" and whether you can optimize for memory by only storing the necessary window of time. It's a classic systems-design scenario.

3. Algorithmic pattern used

There are two main ways to solve this:

• Queue-based: Store each hit's timestamp in a Queue. For getHits, peek at the front and remove all timestamps older than currentTime - 300. The size of the queue is the answer.
• Circular Array (Fixed Space): Since we only care about the last 300 seconds, use two arrays of size 300: times[] and hits[].
  • index = timestamp % 300.
  • If times[index] matches the timestamp, increment hits[index].
  • If it doesn't, reset times[index] to the new timestamp and set hits[index] to 1.
  • getHits sums the hits[] array for all indices where times[index] is within the window.

4. Example explanation

1. hit(1), hit(2), hit(3): Hits: [1, 2, 3].
2. getHits(4): $4-300 = -296$. All hits are after -296. Returns 3.
3. hit(301): Hit added at 301.
4. getHits(301): $301-300 = 1$. The hit at timestamp 1 is exactly 300 seconds old? Usually, the interval is (t-300, t]. So hit at 1 is removed.
5. Returns 3 (for hits at 2, 3, and 301).

5. Common mistakes candidates make

• Storing everything: Using a simple list and keeping all hits forever, which eventually leads to out-of-memory errors.
• Inefficient Query: Iterating through the entire list of hits for every getHits call instead of using a sliding window or a queue.
• Concurrency: Failing to mention how the counter would handle multiple hits arriving at the exact same millisecond.

6. Interview preparation tip

The Circular Array approach is generally preferred because it uses $O(1)$ space (300 cells) regardless of how many millions of hits occur. This makes it extremely memory-efficient for high-traffic systems.