933. Number of Recent Calls
Model: qwen2.5-coder:14b
Topics: Queue
FAANG asked: 0
Acceptance rate: 72.4%
Problem Breakdown
The problem requires implementing a class RecentCounter that counts the number of requests within the last 3000 milliseconds. The class has two methods:
__init__(): Initializes the counter with zero recent requests.ping(int t): Adds a new request at timetand returns the number of requests in the range[t - 3000, t].
Inputs:
t: An integer representing the current time in milliseconds.
Outputs:
- The number of requests within the last 3000 milliseconds.
Implicit Constraints:
- Each call to
pinguses a strictly larger value oftthan the previous call. - At most 10,000 calls will be made to
ping.
Intuition
A brute-force approach would involve storing all timestamps and checking each one for every new request. This is inefficient because it requires iterating over all stored timestamps for each ping, resulting in a time complexity of O(n) per call.
The key insight is to use a queue (FIFO structure) to keep track of the timestamps of recent requests. By maintaining only the timestamps within the last 3000 milliseconds, we can efficiently count the number of valid requests without needing to iterate over all stored timestamps.
Approach
- Data Structure Choice: Use a queue to store the timestamps of the requests.
- Initialization: Initialize an empty queue in the constructor.
- Adding Requests:
- For each new request, add its timestamp to the queue.
- Remove timestamps from the front of the queue that are older than
t - 3000milliseconds.
- Counting Valid Requests: The size of the queue after removing outdated timestamps gives the number of valid requests.
Complexity Analysis
- Time Complexity: O(1) amortized time per call to
ping. Although we remove elements from the front of the queue, each element is added and removed at most once. - Space Complexity: O(W), where W is the maximum number of pings within any 3000 milliseconds window. In this case, it’s bounded by the constraint of at most 10,000 calls.
Solution
from collections import deque
class RecentCounter:
def __init__(self):
self.queue = deque() # Initialize an empty queue to store timestamps
def ping(self, t: int) -> int:
self.queue.append(t) # Add the new request timestamp to the queue
# Remove timestamps that are older than t - 3000 milliseconds
while self.queue and self.queue[0] < t - 3000:
self.queue.popleft()
return len(self.queue) # Return the number of valid requests in the last 3000 milliseconds
# Example usage:
# recentCounter = RecentCounter()
# print(recentCounter.ping(1)) # Output: 1
# print(recentCounter.ping(100)) # Output: 2
# print(recentCounter.ping(3001)) # Output: 3
# print(recentCounter.ping(3002)) # Output: 3
Edge Cases Handled
- Single Request: If only one request is made, the queue will contain only that request.
- Multiple Requests Within 3000ms: The queue will grow to include all requests within the last 3000 milliseconds.
- Requests Exactly at 3000ms Interval: The queue will maintain exactly three timestamps if requests are made at intervals of 1000 milliseconds.
- Large Number of Requests: The solution efficiently handles up to 10,000 calls by maintaining only relevant timestamps.