Design hit counter with range queries

Problem

Design and implement a HitCounter class that keeps track of requests (or hits). It should support the following operations:

record(timestamp): records a hit that happened at timestamp
total(): returns the total number of hits recorded
range(lower, upper): returns the number of hits that occurred between timestamps lower and upper (inclusive)

Follow-up: What if our system has limited memory?

Examples

Example 1

1
2
3
4
5
6
7
8
9


// Example 1:
HitCounter hitCounter = new HitCounter();
hitCounter.record(1);
hitCounter.record(2);
hitCounter.record(3);
hitCounter.record(4);
hitCounter.record(5);
System.out.println(hitCounter.total()); // Output: 5
System.out.println(hitCounter.range(2, 4)); // Output: 3

Solution

Method 1 - Use list or deque

To efficiently record and track hits, we can use a data structure that allows for quick insertion and range queries. A sequential data structure like a list or deque would help in maintaining the hits while keeping the operations efficient.

Approach

Data Structure: Use a list (or deque) to maintain the timestamps of hits.
Record Operation: Append the timestamp to the list.
Total Operation: Return the length of the list.
Range Operation: Count the number of timestamps that fall within the given range using binary search or iteration.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


class HitCounter {
    private List<Integer> timestamps;

    public HitCounter() {
        timestamps = new ArrayList<>();
    }

    public void record(int timestamp) {
        timestamps.add(timestamp);
    }

    public int total() {
        return timestamps.size();
    }

    public int range(int lower, int upper) {
        int ans = 0;
        for (int time : timestamps) {
            if (time >= lower && time <= upper) {
                ans++;
            }
        }
        return ans;
    }
}

// Example usage
class Main {
    public static void main(String[] args) {
        HitCounter hitCounter = new HitCounter();
        hitCounter.record(1);
        hitCounter.record(2);
        hitCounter.record(3);
        hitCounter.record(4);
        hitCounter.record(5);
        System.out.println(hitCounter.total());  // Output: 5
        System.out.println(hitCounter.range(2, 4));  // Output: 3
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class HitCounter:
    def __init__(self):
        self.timestamps: List[int] = []

    def record(self, timestamp: int) -> None:
        self.timestamps.append(timestamp)

    def total(self) -> int:
        return len(self.timestamps)

    def range(self, lower: int, upper: int) -> int:
        return sum(1 for timestamp in self.timestamps if lower <= timestamp <= upper)

# Example usage
if __name__ == "__main__":
    hit_counter = HitCounter()
    hit_counter.record(1)
    hit_counter.record(2)
    hit_counter.record(3)
    hit_counter.record(4)
    hit_counter.record(5)
    print(hit_counter.total())  # Output: 5
    print(hit_counter.range(2, 4))  # Output: 3

Complexity

⏰ Time complexity:
- record(timestamp): O(1) as it’s a simple append operation.
- total(): O(1) as it returns the length of the list.
- range(lower, upper): O(n) where n is the number of hits, as it involves iterating over a subset of hits.
🧺 Space complexity: O(n) where n is the number of hits stored.

Problem#

Examples#

Example 1#

Similar Problem#

Solution#

Method 1 - Use list or deque#

Approach#

Code#

Complexity#