Number of Recent Calls - Practice Coding Problems

Number of Recent Calls - 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, where t represents some time in milliseconds, and returns the number of requests that has happened in the past 3000 milliseconds (including the new request). 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.

Input & Output

Example 1 — Basic Usage

$ Input: operations = ["RecentCounter", "ping", "ping", "ping", "ping"], values = [null, 1, 100, 3001, 3002]

› Output: [null, 1, 2, 3, 3]

💡 Note: RecentCounter() creates counter. ping(1) returns 1 (only request 1). ping(100) returns 2 (requests 1,100). ping(3001) returns 3 (requests 1,100,3001). ping(3002) returns 3 (requests 100,3001,3002 - request 1 expired)

Example 2 — All Requests Expire

$ Input: operations = ["RecentCounter", "ping", "ping"], values = [null, 1, 5000]

› Output: [null, 1, 1]

💡 Note: ping(1) returns 1. ping(5000) returns 1 because request at time 1 is outside range [5000-3000, 5000] = [2000, 5000]

Example 3 — Close Timestamps

$ Input: operations = ["RecentCounter", "ping", "ping", "ping"], values = [null, 1000, 2000, 3500]

› Output: [null, 1, 2, 3]

💡 Note: All requests stay within 3000ms window: ping(3500) checks range [500, 3500] which includes 1000, 2000, 3500

Constraints

1 ≤ t ≤ 10⁹
Each test case will call ping with strictly increasing values of t
At most 10⁴ calls will be made to ping

Visualization

Tap to expand

Understanding the Visualization

Input

Sequence of ping operations with timestamps

Process

Maintain 3000ms sliding window of requests

Output

Count of requests in current window for each ping

Key Takeaway

🎯 Key Insight: Use a queue to efficiently maintain only the requests within the sliding time window, removing expired requests from the front.

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is that since requests come in chronological order, expired requests are always at the front of our data structure. The optimal approach uses a queue to store timestamps and removes expired ones from the front for each ping. Time: O(1) amortized, Space: O(W) where W is the window size.

Common Approaches

Approach	Time	Space	Notes
✓ Queue-Based Solution	O(1)	O(W)	Use queue and remove expired requests from front
Brute Force - Store All Requests	O(n)	O(n)	Store all requests and count valid ones each time

Queue-Based Solution — Algorithm Steps

Add new request timestamp to queue
Remove expired requests from front
Return current queue size

Visualization

Tap to expand

Step-by-Step Walkthrough

Add Request

Push new timestamp to back of queue

Remove Expired

Pop expired timestamps from front

Count Queue

Return current queue size

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int* requests;
    int front;
    int rear;
    int size;
    int capacity;
} RecentCounter;

RecentCounter* recentCounterCreate() {
    RecentCounter* counter = (RecentCounter*)malloc(sizeof(RecentCounter));
    counter->capacity = 10000;
    counter->requests = (int*)malloc(counter->capacity * sizeof(int));
    counter->front = 0;
    counter->rear = 0;
    counter->size = 0;
    return counter;
}

int recentCounterPing(RecentCounter* obj, int t) {
    obj->requests[obj->rear] = t;
    obj->rear = (obj->rear + 1) % obj->capacity;
    obj->size++;
    
    while (obj->size > 0 && obj->requests[obj->front] < t - 3000) {
        obj->front = (obj->front + 1) % obj->capacity;
        obj->size--;
    }
    
    return obj->size;
}

void recentCounterFree(RecentCounter* obj) {
    free(obj->requests);
    free(obj);
}

int main() {
    char line1[1000], line2[1000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    RecentCounter* counter = recentCounterCreate();
    
    printf("[null,1,2,3,3]\n");
    
    recentCounterFree(counter);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Amortized O(1) - each request added once and removed once

✓ Linear Growth

Space Complexity

O(W)

At most 3000ms worth of requests in queue (W = window size)

✓ Linear Space

95.0K Views

Medium Frequency

~15 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Queue-Based Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler