Free lesson · DSA Mastery - Interview Prep, End to End

Number of Recent Calls

Medium5 min readdsaqueues

Number of Recent Calls

Number of Recent Calls is the most direct possible queue application - FIFO in its purest form. You build a counter that, on each ping(t), reports how many pings have happened in the inclusive window [t - 3000, t]. Since timestamps arrive in increasing order, every new ping goes on the back of a queue, and any timestamp older than t - 3000 is expired from the front. The answer is simply the queue's size. We present this standard queue approach; the streaming, monotonically-increasing nature of the input makes the queue the one clean design.

The insight: a queue naturally holds a sliding time window of events. New events enter at the back; events that age out of the window leave from the front. Because pings arrive in order, once a timestamp is too old it stays too old - so a single front-expiry loop per call keeps the queue holding exactly the in-window pings.

The Problem

You have a RecentCounter class which counts the number of recent requests within a certain time frame.

Implement the RecentCounter class:

• RecentCounter() Initializes the counter with zero recent requests.
• int ping(int t) Adds a new request at time t (in milliseconds), and returns the number of requests that have happened in the past 3000 milliseconds (inclusive). Specifically, return the number of requests that have happened in the inclusive range [t - 3000, t].

It is guaranteed that every call to ping uses a strictly larger value of t than the previous call.

Example:

RecentCounter counter = new RecentCounter();
counter.ping(1);     // requests = [1], in range [-2999,1], return 1
counter.ping(100);   // requests = [1,100], in range [-2900,100], return 2
counter.ping(3001);  // requests = [1,100,3001], in range [1,3001], return 3
counter.ping(3002);  // requests = [100,3001,3002], in range [2,3002], 1 expired, return 3

Constraints:

• 1 <= t <= 10^9
• Each call to ping uses a strictly larger t than the previous.
• At most 10^4 calls to ping.

Approaches Overview

A queue holds timestamps still inside the window. Each ping(t) enqueues t, then dequeues from the front while the front is < t - 3000. The window size w is the number of in-range pings. Because each timestamp is enqueued once and dequeued at most once, the work is amortized O(1) per call.

Approach 1: Queue of Timestamps - Standard

The Idea

Maintain a queue of timestamps. On ping(t):

• Enqueue t at the back.
• While the front timestamp is less than t - 3000, dequeue it - it has fallen out of the window.
• Return the queue's size (the count of pings in [t - 3000, t]).

Since timestamps strictly increase, anything expired now will never re-enter the window, so a single front-expiry pass suffices.

Logic Flowchart

graph TD
    A["ping(t)"] --> B["queue.offer(t)"]
    B --> C{"front < t - 3000?"}
    C -->|Yes| D["queue.poll() (expire old)"]
    D --> C
    C -->|No| E["return queue.size()"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the queue approach. Each ping enqueues the new timestamp at the back, then dequeues from the front while the oldest timestamp is older than t minus three thousand. The queue size, the number of in-window pings, is returned.

Code

class RecentCounter {
    private final Queue<Integer> queue = new ArrayDeque<>();

    public int ping(int t) {
        queue.offer(t);                              // new request at the back
        while (queue.peek() < t - 3000) {
            queue.poll();                            // expire requests outside the window
        }
        return queue.size();                         // count in [t-3000, t]
    }
}

// Usage:
// ping(1)->1, ping(100)->2, ping(3001)->3, ping(3002)->3

This Java class keeps a queue of timestamps. Each ping enqueues the new time, then polls from the front while the oldest time is below t minus three thousand. The remaining queue size is the number of recent requests.

Step-by-Step Walkthrough

A frame-by-frame trace of the example calls:

graph LR
    F0["ping(1)<br/>[1] size 1"]
    F1["ping(100)<br/>[1,100] size 2"]
    F2["ping(3001)<br/>[1,100,3001] front 1>=1<br/>size 3"]
    F3["ping(3002)<br/>offer → [1,100,3001,3002]<br/>1 < 2: expire → [100,3001,3002]"]
    F4["size 3"]
    F0 --> F1 --> F2 --> F3 --> F4

    style F0 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F4 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough runs pings at one, one hundred, three thousand one, and three thousand two. The first three stay in range, giving sizes one, two, three. At three thousand two, the window starts at two, so timestamp one expires from the front, leaving size three.

Result (returns per call): 1, 2, 3, 3.

Complexity

Time: amortized O(1) per ping - each timestamp is enqueued once and dequeued at most once. Space: O(w) - the number of timestamps within any 3000 ms window.

Complexity Comparison

One clean design. The streaming, strictly-increasing input is exactly what a queue handles best: the window is a contiguous run of recent timestamps, so old ones leave the front and new ones join the back.

Variations & Follow-ups

Why is each ping amortized O(1) despite the inner loop?

Every timestamp is enqueued exactly once and dequeued at most once over the object's lifetime. So across n pings, total enqueues + dequeues ≤ 2n, making the average per-call cost O(1) even though one call might expire several old timestamps.

Why does a single front-expiry pass suffice?

Timestamps arrive strictly increasing, so the queue is always sorted. A timestamp that's too old for the current window will be even more out of range for every future window - it never comes back. So expiring from the front once per call keeps the queue exactly aligned with the window.

Could you use a counter instead of storing every timestamp?

Not straightforwardly - you need to know when each old request expires, which requires remembering individual timestamps. Unlike a pure count, the window's left edge moves continuously, so you must retain the timestamps to know which ones to drop.

What about edge cases?

• First ping: Queue has one element; returns 1.
• All pings within 3000 ms: Nothing expires; size grows each call.
• Large gaps between pings: A single ping may expire many old timestamps at once.
• Exact boundary (front == t - 3000): In range (inclusive), so not expired - note the strict < in the expiry check.

Common Interview Pitfalls

• Using <= for expiry. The window is inclusive of t - 3000, so expire only when strictly less; <= would wrongly drop a boundary ping.
• Recomputing the count by scanning. The answer is just queue.size() - no need to count.
• Using a stack. This is FIFO (oldest expires first), not LIFO.
• Not expiring before returning. Expire stale timestamps first, then read the size.

Why This Problem Matters

Number of Recent Calls is the gentlest sliding-window-via-queue problem: a queue holds a contiguous run of recent events, new ones join the back, expired ones leave the front. This "queue as a moving window of time" pattern underpins rate limiters, moving statistics, and event-stream processing - and it's the conceptual seed of the monotonic queue, where the same expire-from-front idea gains a sorted-order twist.

The next topic, Time Needed to Buy Tickets, is a queue simulation: people line up to buy tickets, each buying one at a time and rejoining the back if they still want more. You simulate the rotation to compute how long a specific person waits - a direct, satisfying use of enqueue-at-back, serve-from-front.

Back to DSA Mastery - Interview Prep, End to End