Scale Engineer

Number of Recent Calls

Easy
#0887Time: O(N) per `ping` call, where N is the total number of pings made so far. This is because we have to iterate through the entire list of previous requests for every new ping.Space: O(N), where N is the total number of pings. The list stores every timestamp ever received, so its size grows linearly with the number of calls.3 companies
Patterns
DesignData Stream
Data structures
Queue
Companies
RobloxDatabricksAffirm

Prompt

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.

 

Example 1:

Input
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
Output
[null, 1, 2, 3, 3]

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

 

Constraints:

  • 1 <= t <= 109
  • Each test case will call ping with strictly increasing values of t.
  • At most 104 calls will be made to ping.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves storing all the timestamps of the requests in a list. For each new ping, we add the new timestamp to the list and then iterate through the entire list to count how many timestamps fall within the required time window [t - 3000, t].

Algorithm

  • Initialize an empty list, requests, in the constructor.
  • In the ping(t) method:
    1. Add the new timestamp t to the requests list.
    2. Calculate the lower bound of the time window: lowerBound = t - 3000.
    3. Initialize a counter count to 0.
    4. Iterate through each timestamp in the requests list.
    5. If timestamp >= lowerBound, increment count.
    6. Return count.

Walkthrough

We use a dynamic array (like ArrayList in Java) to keep a record of all timestamps received so far. When the ping(t) method is called, we first add the new timestamp t to the end of the list. Then, we iterate through every timestamp stored in the list, checking if it is greater than or equal to t - 3000. We count how many such timestamps exist and return the total count.

import java.util.ArrayList;import java.util.List; class RecentCounter {    private List<Integer> requests;     public RecentCounter() {        this.requests = new ArrayList<>();    }     public int ping(int t) {        this.requests.add(t);        int lowerBound = t - 3000;        int count = 0;        // Iterate through all past requests        for (int timestamp : this.requests) {            if (timestamp >= lowerBound) {                count++;            }        }        return count;    }}

Complexity

Time

O(N) per `ping` call, where N is the total number of pings made so far. This is because we have to iterate through the entire list of previous requests for every new ping.

Space

O(N), where N is the total number of pings. The list stores every timestamp ever received, so its size grows linearly with the number of calls.

Trade-offs

Pros

  • Very simple and straightforward to implement.

  • Easy to understand the logic.

Cons

  • Inefficient time complexity, as it re-scans old timestamps that are no longer relevant.

  • Inefficient space complexity, as it never discards old timestamps, leading to ever-increasing memory usage.

Solutions

public class RecentCounter { private Queue < int > q = new Queue < int >(); public RecentCounter () { } public int Ping ( int t ) { q . Enqueue ( t ); while ( q . Peek () < t - 3000 ) { q . Dequeue (); } return q . Count ; } } /** * Your RecentCounter object will be instantiated and called as such: * RecentCounter obj = new RecentCounter(); * int param_1 = obj.Ping(t); */

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem