Number of Recent Calls — Solution in Python, Java & C++
Number of Recent Calls solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on queue.
Number of Recent Calls is an easy coding problem on queue, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Queue
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A service receives requests and wants to know how busy it has been lately. Write the class RecentCounter:
RecentCounter()starts with no requests.int ping(int t)records a new request at timet(in milliseconds) and returns how many requests — this one included — happened in the inclusive window[t - 3000, t].
Every call to ping uses a strictly larger t than the call before it.
The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.
Example 1
Input: ["RecentCounter","ping","ping","ping","ping"]
[[],[1],[100],[3001],[3002]]
Output: [null,1,2,3,3]
Explanation: At t = 3001 the window is [1, 3001], which still holds the request at 1. At t = 3002 the window is [2, 3002], so the request at 1 has dropped out: 100, 3001 and 3002 remain.
Example 2
Input: ["RecentCounter","ping","ping","ping","ping","ping"]
[[],[500],[3500],[3501],[9000],[9001]]
Output: [null,1,2,2,1,2]
Explanation: A request exactly 3000 ms old (500 seen from 3500) is still counted. By t = 9000 every earlier request is too old.
Constraints
1 <= t <= 10^9Each call to ping uses a strictly larger t than the previous callAt most 10^4 calls are made to ping
Hints for Number of Recent Calls
Hint 1
Because the times only grow, a request that is too old for one call is too old for every later call.
Hint 2
Keep the requests in arrival order and throw away old ones from the front.
Hint 3
Use a queue: push
t, then pop from the front while the front is< t - 3000; the queue's size is the answer.
How to solve Number of Recent Calls
Keep the requests still inside the window in a queue. Times arrive in increasing order, so the oldest request is always at the front, and once it falls out of the window it never comes back.
Approach
ping(t): pushtonto the back of the queue.- While the front of the queue is smaller than
t - 3000, pop it. - Return the queue's size.
Why it works
The queue is sorted because t strictly increases. Every element popped is older than t - 3000 and so outside every future window too (later windows start even later), while every element kept is at least t - 3000 and at most t — exactly the requests in the window.
Complexity
- Time —
amortized O(1) per ping — each request is pushed once and popped at most once - Space —
O(w), where w is the most requests inside one 3000 ms window
Pitfalls
- The window is inclusive at both ends: a request at exactly
t - 3000counts. - Shifting from the front of a plain array is O(n) in some languages; a head index (or a real deque) keeps it O(1).
Reference solution
Python
from collections import deque
class RecentCounter:
def __init__(self):
self.q = deque()
def ping(self, t: int) -> int:
self.q.append(t)
while self.q[0] < t - 3000:
self.q.popleft()
return len(self.q)Java
class RecentCounter {
private Deque<Integer> q = new ArrayDeque<>();
public RecentCounter() {
}
public int ping(int t) {
q.offer(t);
while (q.peek() < t - 3000) q.poll();
return q.size();
}
}C++
class RecentCounter {
queue<int> q;
public:
RecentCounter() {}
int ping(int t) {
q.push(t);
while (q.front() < t - 3000) q.pop();
return (int)q.size();
}
};JavaScript
var RecentCounter = function() {
this.q = [];
this.head = 0; // index of the oldest request still in the window
};
RecentCounter.prototype.ping = function(t) {
this.q.push(t);
while (this.q[this.head] < t - 3000) this.head++;
return this.q.length - this.head;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 27 queue problems · the whole catalogue
Learn the technique: Queues and Deques