Leetcode 362. Design Hit Counter
Asked at:
Uber
Apple
DESCRIPTION
Design a hit counter that records timestamps of incoming hits and efficiently queries the number of hits within the past 5 minutes (300 seconds) using a sliding window. The system must handle high-frequency hit(timestamp) and getHits(timestamp) operations by maintaining only relevant data and discarding expired entries. For example, if hits arrive at timestamps [1, 100, 200, 300, 301] and we query at timestamp = 301, only hits at [1, 100, 200, 300, 301] count (all within 300 seconds).
Input:
hit(1) hit(2) hit(3) getHits(4) getHits(300) getHits(301)
Output:
null null null 3 3 2
Explanation: At timestamp = 4, all 3 hits are within 300 seconds. At timestamp = 300, hits at [1, 2, 3] are still valid. At timestamp = 301, hit at timestamp = 1 expires (301 - 1 = 300 seconds exactly is the boundary), leaving 2 hits.
Constraints:
- Timestamps are in seconds and arrive in non-decreasing order
- The sliding window is 300 seconds (5 minutes)
- Must support high-frequency operations efficiently
- 1 <= timestamp <= 2 * 10^9
Understanding the Problem
The core challenge is maintaining a dynamic sliding window that automatically discards expired hits while supporting fast queries. A naive approach storing all timestamps wastes memory and requires scanning the entire history on each query. The key insight is that we only need hits from the past 300 seconds, so we can use a queue or circular buffer to maintain a rolling window. When querying, we remove expired entries from the front and count remaining elements.
Building Intuition
A naive approach stores all timestamps in a list and scans from the beginning on each query to count valid hits, resulting in O(n) query time where n is total hits ever recorded. A better approach uses a queue (deque) to store timestamps and removes expired entries during queries, keeping only the sliding window in memory. For example, with hits at [1, 100, 200, 300] and query at 301, we pop 1 from the front (expired) and count the remaining 3 elements in O(k) time where k is hits in the window.
Real-world systems like rate limiters, analytics dashboards, and monitoring tools need to track recent events efficiently without unbounded memory growth. A sliding window approach ensures constant memory usage proportional to the window size, not total event count. This pattern is fundamental for building scalable, high-throughput services.
Common Pitfalls
Implementation
Queue-Based Sliding Window
Use a deque to store timestamps in chronological order, leveraging the fact that timestamps arrive in non-decreasing order. On each hit(timestamp), append the timestamp to the deque and remove expired entries from the front. On getHits(timestamp), clean up expired entries and return the deque's length. For example, with hits [1, 100, 200] and query at 301, we remove 1 (since 301 - 1 = 300, which is not within the past 300 seconds) and return 2.
from collections import dequeclass HitCounter:def __init__(self):self.hits = deque()def hit(self, timestamp: int) -> None:self.hits.append(timestamp)def getHits(self, timestamp: int) -> int:while self.hits and self.hits[0] <= timestamp - 300:self.hits.popleft()return len(self.hits)
Optimized Circular Buffer Approach
For scenarios with extremely high frequency hits, use a fixed-size circular buffer with bucketing to reduce memory overhead. Divide the 300-second window into buckets (e.g., 300 buckets of 1 second each) and store hit counts per bucket. On query, sum counts from valid buckets and reset expired ones. For example, with 1-second buckets, a hit at timestamp = 150 increments bucket[150 % 300], and querying at 450 sums buckets [150-449] after clearing buckets [0-149]. This approach uses O(300) space regardless of hit count.
class HitCounterCircular:def __init__(self):self.buckets = [0] * 300self.times = [0] * 300def hit(self, timestamp: int) -> None:idx = timestamp % 300if self.times[idx] != timestamp:self.buckets[idx] = 0self.times[idx] = timestampself.buckets[idx] += 1def getHits(self, timestamp: int) -> int:total = 0for i in range(300):if timestamp - self.times[i] < 300:total += self.buckets[i]return total
Complete Integration
Combine both approaches into a unified HitCounter class that selects the appropriate strategy based on use case. The queue-based approach (Section 1) is ideal for moderate traffic with precise timestamp tracking, while the circular buffer approach (Section 2) excels under extreme load where approximate counts suffice. Provide a factory method or configuration flag to switch between implementations. For example, instantiate HitCounter(strategy='queue') for exact counting or HitCounter(strategy='bucket', bucket_size=1) for high-throughput scenarios.
class HitCounter:def __init__(self, strategy='queue', bucket_size=1):self.strategy = strategyif strategy == 'queue':self.impl = HitCounterQueue()elif strategy == 'bucket':self.impl = HitCounterCircular()else:raise ValueError(f"Unknown strategy: {strategy}")def hit(self, timestamp: int) -> None:self.impl.hit(timestamp)def getHits(self, timestamp: int) -> int:return self.impl.getHits(timestamp)class HitCounterQueue:def __init__(self):self.hits = deque()def hit(self, timestamp: int) -> None:self.hits.append(timestamp)def getHits(self, timestamp: int) -> int:while self.hits and self.hits[0] <= timestamp - 300:self.hits.popleft()return len(self.hits)
What We've Learned
- Pattern: Use a deque for sliding windows with chronological data to achieve `O(1)` removal from both ends
- Optimization: Bucketing trades precision for memory efficiency in high-frequency scenarios, reducing space from `O(n)` to `O(window_size)`
- Use Case: Essential for rate limiting, real-time analytics, and monitoring systems that track recent events without unbounded growth
Problems to Practice
medium
This problem practices maintaining a dynamic sliding window while tracking elements and removing expired ones, similar to how the Hit Counter discards hits outside the 5-minute window. Both require efficient addition and removal of elements from the window.
medium
While using a different data structure, this problem shares the concept of efficiently processing time-series data and maintaining relevant historical information. The monotonic stack pattern can be an alternative approach for certain time-window problems requiring efficient lookups.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Late June, 2026
Uber
Senior
Late June, 2026
Uber
Senior
Circular buffer + fake clock + discussion around concurrency
Early June, 2026
Apple
Mid-level
Hello Interview Premium
Your account is free and you can post anonymously if you choose.