Number of Recent Calls

Easy
2041.

Number of Recent Calls

Number of Recent Calls is an easy coding problem on queue, asked in Amazon and Google interviews.

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 time t (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^9
  • Each call to ping uses a strictly larger t than the previous call
  • At most 10^4 calls are made to ping
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 */
var RecentCounter = function() {
    
};

/**
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function(t) {
    
};

Sign in to run your own test cases

Sign in

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 time t (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^9
  • Each call to ping uses a strictly larger t than the previous call
  • At most 10^4 calls are made to ping

Hints for Number of Recent Calls

  1. Hint 1

    Because the times only grow, a request that is too old for one call is too old for every later call.

  2. Hint 2

    Keep the requests in arrival order and throw away old ones from the front.

  3. 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

  1. ping(t): push t onto the back of the queue.
  2. While the front of the queue is smaller than t - 3000, pop it.
  3. 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 - 3000 counts.
  • 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