Design Hit Counter with Variable Time Windows

Problem Statement

Design an in-memory hit counter that can calculate the average load (QPS - queries per second) over a specified time window. The system should efficiently handle variable time windows, from seconds to minutes.

Examples

1. HitCounter hitCounter = new HitCounter(300);
2. hitCounter.hit(1); // hit at timestamp 1.
3. hitCounter.hit(1); // hit at timestamp 2.
4. hitCounter.hit(2); // hit at timestamp 3.
5. System.out.println(hitCounter.get(4)); // return 3.
6. hitCounter.hit(3); // hit at timestamp 4.
7. System.out.println(hitCounter.get(6)); // return 4.
8. hitCounter.hit(1); // hit at timestamp 8.
9. hitCounter.hit(1); // hit at timestamp 9.
10. System.out.println(hitCounter.get(10)); // return 3.

Constraints

• All input numbers come in as integers.
• The range of the counter's return values is between 0 and the maximum possible 32-bit signed integer.

Hints

• Use a sliding window approach to keep track of hits within the specified time window.
• Use a data structure like a queue or a list to store timestamps of hits.
• Implement a mechanism to remove outdated hits from the window.

Solution

`java import java.util.LinkedList; import java.util.Queue;

class HitCounter { private Queue<Integer> hits; private int windowSize;

public HitCounter(int windowSize) {
    this.hits = new LinkedList<>();
    this.windowSize = windowSize;
}

public void hit(int timestamp) {
    // Remove outdated hits
    while (!hits.isEmpty() && hits.peek() < timestamp - windowSize) {
        hits.poll();
    }
    // Add the current hit
    hits.offer(timestamp);
}

public int get(int timestamp) {
    // Remove outdated hits
    while (!hits.isEmpty() && hits.peek() < timestamp - windowSize) {
        hits.poll();
    }
    // Calculate the number of hits within the window
    return hits.size();
}

} `

This solution uses a queue to store timestamps of hits. When a new hit is added, it removes any hits that are outside the current window. When calculating the number of hits within the window, it also removes outdated hits. This ensures that the queue always contains hits within the current window, allowing for efficient calculation of the average load.