Brute Force: Queue

class HitCounter:
  
    def __init__(self):
        self.q = collections.deque()

    # tc O(1) sc O(N)
    def hit(self, timestamp: int) -> None:
        self.q.append(timestamp)
        
    # tc O(N) sc O(N)
    def getHits(self, timestamp: int) -> int:
        thr =  timestamp - 300 
        while self.q and self.q[0] <= thr:
            self.q.popleft()
        return len(self.q)

Notice when multiple hits at the same timestamp, we don’t want to repeated the removal opearation in the queue since it’s inefficient. we use a list with size of 2 [timestamp, counter] to record. counter is to record number of hits at timestamp t, and use a total variable to record total hits so far

class HitCounter:
  
    def __init__(self):
        self.q = collections.deque()
        self.total = 0 
    # tc O(1) sc O(N)
    def hit(self, timestamp: int) -> None:
        if not self.q or self.q[-1][0] != timestamp:
            self.q.append([timestamp,1])  # memory can go unbounded 
        else:
            self.q[-1][1] += 1
        self.total += 1 
    
    def getHits(self, timestamp: int) -> int:
        thr =  timestamp - 300 
        while self.q and self.q[0][0] <= thr:
            t,cnt = self.q.popleft()
            self.total -= cnt 
        return self.total

Better for scale solution

class HitCounter:
class HitCounter:
    """
    if we got large stream and the expiered time is fixed, we can create two fixed arrays to store timestamp and cnt within valid time duratin (300s ) 
    """
    def __init__(self):
        self.time = [0] *300 # store timestamp 
        self.cnt  = [0] * 300 # store count at timestamp 
        self.total = 0
    # tc O(1) sc O(300)
    def hit(self, timestamp: int) -> None:
        idx = timestamp % 300
        if self.time[idx] != timestamp:
            self.time[idx] = timestamp 
            self.cnt[idx] = 1 
        else:
            self.cnt[idx] += 1
            
    # tc O(N)  sc O(300)
    def getHits(self, timestamp: int) -> int:
        res = 0
        for i in range(300):
            if timestamp - self.time[i] < 300 :
                res += self.cnt[i]
        return res