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

// 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

Similar Problem

Design Hit Counter

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

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

Code

Java
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
    }
}
Python
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.