Problem Description

The "Design Hit Counter" problem asks you to implement a class that can record and count hits received in the past 5 minutes (300 seconds). Specifically, you need to:

• Implement two methods: hit(timestamp) and getHits(timestamp).
• hit(timestamp) records a hit that happened at the given timestamp (in seconds, strictly increasing).
• getHits(timestamp) returns the number of hits received in the past 5 minutes (i.e., past 300 seconds) from the given timestamp.
• Each call to hit and getHits will have timestamps in increasing order (monotonic).
• You may assume the system will not be called with timestamps that are earlier than the current time.

The challenge is to design this class efficiently so that both methods work quickly, even if there are many hits per second.

Thought Process

At first, you might think of storing every single hit as an individual timestamp. When getHits is called, you could count how many timestamps are within the last 300 seconds. This brute-force approach works for small numbers of hits but becomes inefficient and memory-intensive with many hits per second.

To optimize, we can observe that:

• We only care about hits in the last 300 seconds.
• Timestamps are strictly increasing, so we can use a queue or a circular buffer to efficiently discard old hits.
• If multiple hits occur at the same timestamp, we can aggregate them to save space.

The goal is to maintain a data structure that allows us to efficiently add new hits and remove expired ones, so both hit and getHits are fast.

Solution Approach

We can use a queue (or deque) to store hit records, each record being a pair of (timestamp, count). Here's how the algorithm works:

1. Recording a Hit (hit(timestamp)):
   • If the latest timestamp in the queue matches timestamp, increment its count.
   • Otherwise, append a new record (timestamp, 1) to the queue.
2. Getting Hits (getHits(timestamp)):
   • Remove records from the front of the queue if they are older than timestamp - 299.
   • Sum the counts of all remaining records to get the total hits in the past 5 minutes.

This approach is efficient because:

• We only store up to 300 records (one per second), even if there are many hits in a second.
• Both hit and getHits run in O(1) amortized time per operation.
• We never keep outdated data, so memory usage is controlled.

In some languages, you could also use a fixed-size array of 300 slots, each holding the timestamp and count for that second, overwriting as time moves forward.

Example Walkthrough

Let's walk through a sample sequence of operations:

• hit(1) → queue: [(1, 1)]
• hit(2) → queue: [(1, 1), (2, 1)]
• hit(300) → queue: [(1, 1), (2, 1), (300, 1)]
• getHits(300):
  • Remove records with timestamp < 300 - 299 = 1. None to remove.
  • Sum counts: 1 + 1 + 1 = 3
• getHits(301):
  • Remove records with timestamp < 301 - 299 = 2. Remove (1, 1).
  • Sum counts: 1 + 1 = 2

This shows how old hits are efficiently discarded and only relevant hits are counted.

Time and Space Complexity

Brute-Force Approach:

• Time Complexity: O(k), where k is the number of hits in the past 5 minutes (could be very large).
• Space Complexity: O(k), since we store every single hit.

Optimized Approach (Queue or Circular Buffer):

• Time Complexity: O(1) amortized for both hit and getHits (since we only process at most 300 records per operation).
• Space Complexity: O(300) = O(1), since we store at most one record per second in the last 5 minutes.

Thus, the optimized approach is both time and space efficient.

Summary

The "Design Hit Counter" problem teaches us how to efficiently track and count events within a sliding window of time. By aggregating hits per timestamp and removing outdated records as time advances, we ensure both fast operations and low memory usage. The solution is elegant because it leverages the monotonic property of timestamps and uses simple data structures to maintain only relevant data, making it suitable for real-time analytics and similar use-cases.

Code Implementation

from collections import deque

class HitCounter:
    def __init__(self):
        self.hits = deque()  # Each element: (timestamp, count)
        self.total = 0

    def hit(self, timestamp: int) -> None:
        if self.hits and self.hits[-1][0] == timestamp:
            ts, cnt = self.hits.pop()
            self.hits.append((ts, cnt + 1))
        else:
            self.hits.append((timestamp, 1))
        self.total += 1

    def getHits(self, timestamp: int) -> int:
        while self.hits and self.hits[0][0] <= timestamp - 300:
            ts, cnt = self.hits.popleft()
            self.total -= cnt
        return self.total
      

#include <queue>
using namespace std;

class HitCounter {
public:
    queue<pair<int, int>> hits;
    int total = 0;

    HitCounter() {}

    void hit(int timestamp) {
        if (!hits.empty() && hits.back().first == timestamp) {
            hits.back().second += 1;
        } else {
            hits.push({timestamp, 1});
        }
        total += 1;
    }

    int getHits(int timestamp) {
        while (!hits.empty() && hits.front().first <= timestamp - 300) {
            total -= hits.front().second;
            hits.pop();
        }
        return total;
    }
};
      

import java.util.*;

public class HitCounter {
    private Deque<int[]> hits;
    private int total;

    public HitCounter() {
        hits = new ArrayDeque<>();
        total = 0;
    }

    public void hit(int timestamp) {
        if (!hits.isEmpty() && hits.peekLast()[0] == timestamp) {
            hits.peekLast()[1]++;
        } else {
            hits.addLast(new int[]{timestamp, 1});
        }
        total++;
    }

    public int getHits(int timestamp) {
        while (!hits.isEmpty() && hits.peekFirst()[0] <= timestamp - 300) {
            total -= hits.peekFirst()[1];
            hits.pollFirst();
        }
        return total;
    }
}
      

class HitCounter {
    constructor() {
        this.hits = [];
        this.total = 0;
    }

    hit(timestamp) {
        if (this.hits.length > 0 && this.hits[this.hits.length - 1][0] === timestamp) {
            this.hits[this.hits.length - 1][1] += 1;
        } else {
            this.hits.push([timestamp, 1]);
        }
        this.total += 1;
    }

    getHits(timestamp) {
        while (this.hits.length > 0 && this.hits[0][0] <= timestamp - 300) {
            this.total -= this.hits[0][1];
            this.hits.shift();
        }
        return this.total;
    }
}