Design Hit Counter — LeetCode 362 Python Solution

The problem

Design a hit counter which counts the number of hits received in the past 5 minutes (i.e., the past 300 seconds). Your system should accept a timestamp parameter (in seconds granularity), and you may assume that calls are being made to the system in chronological order (i.e., timestamp is monotonically increasing).

Example

Input

["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]

Output

[null, null, null, null, 3, null, 4, 3]

Explanation

HitCounter hitCounter = new HitCounter();

Python solution

class HitCounter:

    def __init__(self):
        self.ts = []

    def hit(self, timestamp: int) -> None:
        self.ts.append(timestamp)

    def getHits(self, timestamp: int) -> int:
        return len(self.ts) - bisect_left(self.ts, timestamp - 300 + 1)


# Your HitCounter object will be instantiated and called as such:
# obj = HitCounter()
# obj.hit(timestamp)
# param_2 = obj.getHits(timestamp)

Complexity

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 362. Design Hit Counter is filed here because LeetCode tags it Queue, which is the vocabulary this hub collects.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems