We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Design Hit Counter

Number: 362

Difficulty: Medium

Paid? Yes

Companies: Databricks, Uber, Bloomberg, Roblox, Amazon, Apple, Yandex, Walmart Labs, Affirm, Coupang, Microsoft, Google, Reddit, Cloudflare, Snowflake, Atlassian, Meta, MongoDB, Dropbox

Problem Description

Design a hit counter that counts the number of hits received in the past 5 minutes (i.e., the past 300 seconds). The system should support two operations: hit(timestamp) to record a hit at a given timestamp (in seconds), and getHits(timestamp) to retrieve the number of hits in the past 300 seconds from the given timestamp. You may assume that timestamps are provided in a non-decreasing order.

Key Insights

  • Use a sliding window of 300 seconds to count hits.
  • Since timestamps are monotonically increasing, outdated hits can be removed from the front.
  • A queue (or circular array) is an efficient data structure to maintain and remove expired hit records.
  • Grouping consecutive hits at the same timestamp can optimize space.

Space and Time Complexity

Time Complexity: O(1) per hit and getHits operation on average, since each hit is enqueued and later dequeued only once.
Space Complexity: O(W) where W is the window size (300 seconds) in the worst case.

Solution

The solution uses a queue (or deque) data structure where each element stores a (timestamp, count) pair. When a hit is recorded, if the last element of the queue shares the same timestamp, then its count is incremented; otherwise, a new element is added. When getHits(timestamp) is called, the algorithm removes elements from the front of the queue whose timestamp is out of the 300-second window relative to the current timestamp, and then sums the counts of the remaining elements to return the result. This ensures that only relevant hits within the past 5 minutes are counted. The design scales well when hit frequency is high because hits at the same timestamp are grouped together instead of inserting individual records.

Code Solutions

# Python implementation of HitCounter

from collections import deque

class HitCounter:
    def __init__(self):
        # Initialize the deque to store (timestamp, count) pairs.
        self.hits_queue = deque()

    def hit(self, timestamp: int) -> None:
        # If the last recorded hit is at the same timestamp, increment its count.
        if self.hits_queue and self.hits_queue[-1][0] == timestamp:
            self.hits_queue[-1][1] += 1
        else:
            # Append new (timestamp, count) pair.
            self.hits_queue.append([timestamp, 1])

    def getHits(self, timestamp: int) -> int:
        # Remove outdated hits from the front of the queue.
        while self.hits_queue and self.hits_queue[0][0] <= timestamp - 300:
            self.hits_queue.popleft()
        # Sum counts of the remaining hit entries.
        return sum(count for _, count in self.hits_queue)
← Back to All Questions