Number of Recent Calls
Asked at Databricks
Problem
Implement a class that tracks incoming requests with timestamps. The ping(t) method returns the number of recent calls in the time range [t-3000, t]. This is a classic sliding window problem using a queue to maintain the window of recent events.
Asked At
| Company | Difficulty | |
|---|---|---|
| Databricks | EASY | View all Databricks questions → |
How to Think About It
Store all ping timestamps in a list or queue
For each new ping, remove all timestamps older than t-3000
Count the remaining timestamps in the window [t-3000, t]
A deque or queue is ideal for efficient removal from the front
The amortized cost per ping is O(1) since each element is added and removed once
Optimal Approach
Maintain a queue of timestamps. On each ping(t), first remove all timestamps from the front that are less than t-3000 (outside the window). Then add t to the queue. The size of the queue is the number of recent calls. Since each timestamp is added once and removed once, the amortized time per ping is O(1).
What Trips People Up in Real Interviews
Clarify that the time range is inclusive on both ends
Explain the sliding window approach removes expired entries on each ping
Mention that a simple list with a pointer also works but queue is cleaner
Discuss that the queue never grows beyond 3000 entries (bounded window)
Note the amortized O(1) complexity since each ping is added and removed exactly once
Solution Code
from collections import deque
class RecentCounter:
def __init__(self):
self.queue = deque()
def ping(self, t: int) -> int:
self.queue.append(t)
while self.queue[0] < t - 3000:
self.queue.popleft()
return len(self.queue)Frequently Asked Questions
What is the Number of Recent Calls problem?
Implement a class that tracks incoming requests with timestamps. The ping(t) method returns the number of recent calls in the time range [t-3000, t]. This is a classic sliding window problem using a queue to maintain the window of recent events.
How do you solve Number of Recent Calls?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Number of Recent Calls?
Number of Recent Calls is asked at Databricks. It is a easy difficulty problem.
What are common mistakes on Number of Recent Calls?
- Clarify that the time range is inclusive on both ends
- Explain the sliding window approach removes expired entries on each ping
- Mention that a simple list with a pointer also works but queue is cleaner
- Discuss that the queue never grows beyond 3000 entries (bounded window)
- Note the amortized O(1) complexity since each ping is added and removed exactly once