Design Hit Counter

Problem Statement: Design a hit counter that keeps track of the number of hits in the past 5 minutes. The hit counter receives a timestamp (in seconds) for each hit, and it should support the following operations:

  • hit(timestamp): Record a hit at the given timestamp.
  • getHits(timestamp): Get the number of hits in the past 5 minutes, including the current timestamp.

1. Clarify the problem:

  • Can the timestamps be negative or zero?
  • Can the timestamps be in any order, or are they guaranteed to be in increasing order?

2. Analyze the problem:

  • Input: Timestamps (positive integers)
  • Output: Number of hits in the past 5 minutes (integer)
  • Constraints:
    • The timestamps can be any positive integer.
    • The timestamps may not be in increasing order.

3. Design an algorithm:

  • We can use a circular buffer to store the hit timestamps for the past 5 minutes.
  • Initialize an array of size 300 (5 minutes) with all elements set to zero to represent the hit counter.
  • To record a hit at a given timestamp:
    • Calculate the index in the circular buffer using the formula index = timestamp % 300.
    • Increment the value at the calculated index by one.
  • To get the number of hits in the past 5 minutes:
    • Initialize a variable totalHits to zero.
    • Iterate over the circular buffer and add up all the values.
  • Since the circular buffer represents the last 5 minutes, we need to account for timestamps that are older than 5 minutes.
    • To do this, we can keep track of the latest timestamp seen and reset all the buffer elements if the current timestamp is more than 300 seconds (5 minutes) greater than the latest timestamp seen.

4. Explain your approach:

  • We will use a circular buffer of size 300 to store the hit counter.
  • To record a hit, we will calculate the index in the circular buffer based on the timestamp and increment the value at that index by one.
  • To get the number of hits in the past 5 minutes, we will iterate over the circular buffer and sum up all the values.
  • We will handle the case where the current timestamp is more than 5 minutes greater than the latest timestamp seen by resetting all the buffer elements.
  • The circular buffer allows us to efficiently keep track of the hit counter for the past 5 minutes.

5. Write clean and readable code:

python
class HitCounter:
    def __init__(self):
        self.counter = [0] * 300  # Circular buffer
        self.latestTimestamp = 0

    def hit(self, timestamp):
        index = timestamp % 300
        if timestamp > self.latestTimestamp + 300:
            self.reset()
        self.counter[index] += 1
        self.latestTimestamp = max(self.latestTimestamp, timestamp)

    def getHits(self, timestamp):
        if timestamp > self.latestTimestamp + 300:
            return 0
        totalHits = sum(self.counter)
        for i in range((timestamp + 1) % 300, self.latestTimestamp % 300 + 1):
            totalHits -= self.counter[i]
        return totalHits

    def reset(self):
        self.counter = [0] * 300

6. Test your code: I will test the code with the following test cases:

  • Test case 1: Hit counter with multiple hits within the past 5 minutes.
  • Test case 2: Hit counter with hits older than 5 minutes.
  • Test case 3: Hit counter with hits exactly 5 minutes ago.
  • Test case 4: Hit counter with hits at the same timestamp.
  • Test case 5: Hit counter with a single hit.
  • Test case 6: Hit counter with no hits.
python
# Test case 1
hitCounter = HitCounter()
hitCounter.hit(1)
hitCounter.hit(2)
hitCounter.hit(3)
print(hitCounter.getHits(4))  # Expected output: 3

# Test case 2
hitCounter = HitCounter()
hitCounter.hit(1)
hitCounter.hit(2)
hitCounter.hit(300)
print(hitCounter.getHits(301))  # Expected output: 2

# Test case 3
hitCounter = HitCounter()
hitCounter.hit(1)
hitCounter.hit(2)
hitCounter.hit(300)
print(hitCounter.getHits(305))  # Expected output: 0

# Test case 4
hitCounter = HitCounter()
hitCounter.hit(1)
hitCounter.hit(1)
print(hitCounter.getHits(1))  # Expected output: 2

# Test case 5
hitCounter = HitCounter()
hitCounter.hit(1)
print(hitCounter.getHits(1))  # Expected output: 1

# Test case 6
hitCounter = HitCounter()
print(hitCounter.getHits(1))  # Expected output: 0

7. Optimize if necessary: The given solution has a time complexity of O(1) for both the hit and getHits operations since we are directly accessing the elements in the circular buffer.

The space complexity of the solution is O(1) since we are using a fixed-size circular buffer of size 300.

No further optimization is required for this problem as the solution already provides the required functionality efficiently.

 

8. Handle error cases: In the given solution, there are no explicit error cases or exceptions handled. However, we can discuss potential error cases and how to handle them gracefully:

  • Invalid timestamps: The solution assumes that the input timestamps are positive integers. If the input timestamps can be negative or zero, we can add a check at the beginning of the hit and getHits methods to validate the input and raise an exception or return an error message if the timestamp is invalid.

9. Discuss complexity analysis:

  • Time complexity:

    • The hit operation has a time complexity of O(1) since it involves calculating the index in the circular buffer and updating the value at that index.
    • The getHits operation has a time complexity of O(1) as well. It involves iterating over the circular buffer once and summing up all the values, excluding the ones that fall outside the 5-minute window.

  • Space complexity:

    • The space complexity is O(1) since we are using a fixed-size circular buffer of size 300 to store the hit counter. The space occupied by the circular buffer does not depend on the input size.

  • Best-case scenario:

    • The best-case scenario is when there are no hits or when all the hits fall within the 5-minute window. In this case, both the hit and getHits operations have a constant time complexity of O(1).

  • Worst-case scenario:

    • The worst-case scenario is when there are a large number of hits, and the circular buffer needs to be reset frequently. In this case, the time complexity of the hit operation remains O(1) since calculating the index and updating the value are constant-time operations. However, the getHits operation may take longer since it involves iterating over the entire circular buffer.

  • Average-case scenario:

    • In the average case, the time complexity of both the hit and getHits operations remains constant at O(1), assuming a uniform distribution of hits across the 5-minute window.

  • Trade-offs:

    • The chosen solution uses a fixed-size circular buffer to keep track of the hit counter. This allows for constant-time operations and efficient memory usage. However, a trade-off is that the solution only supports tracking hits within a 5-minute window. If there is a need to track hits over a longer duration, the circular buffer size would need to be increased, which would consume more memory. Additionally, the solution assumes that the hit timestamps are provided in increasing order or random order. If the timestamps are not provided in order, additional logic can be added to handle the out-of-order timestamps efficiently.
Next Post Previous Post