Number of Recent Calls

Easy

Databricks

4 views

Topics:

ArraysStacksBinary SearchSliding Windows

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 <= 10⁹
Each test case will call ping with strictly increasing values of t.
At most 10⁴ calls will be made to ping.

Try coding it in LeetCode

Number of Recent Calls

Easy

Databricks

4 views

Topics:

ArraysStacksBinary SearchSliding Windows

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 <= 10⁹
Each test case will call ping with strictly increasing values of t.
At most 10⁴ calls will be made to ping.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range for the timestamp `t`? Can I assume `t` will always be a non-negative integer?
If there are no calls within the range `[t-3000, t]`, should the `ping` method return 0?
Can multiple calls have the same timestamp `t`? If so, how should they be handled?
Is the input stream of calls guaranteed to be in ascending order of timestamp `t`?
Are there any memory constraints I should be aware of for storing the recent calls?

Brute Force Solution

Approach

This problem wants us to count recent calls. A straightforward approach is to keep a record of every call we receive and then, when asked, check each one to see if it falls within the specified time window.

Here's how the algorithm would work step-by-step:

Whenever we get a new call, write down the time it came in.
When asked to count recent calls, go through the entire list of recorded call times.
For each recorded call time, check if it's within the time window we're interested in. The time window is defined as any call that came in during the last 3000 units of time.
Keep a running total of all the calls that fall within that window.
After checking all the recorded times, report the total number of calls that were recent.

Code Implementation

class RecentCounter:

    def __init__(self):
        self.call_times = []

    def ping(self, time):
        # Record the current call time.
        self.call_times.append(time)

        recent_calls_count = 0

        # Iterate through all recorded call times.
        for call_time in self.call_times:
            # Check if the call is within the last 3000 units of time.
            if time - call_time <= 3000:
                recent_calls_count += 1

        return recent_calls_count

Big(O) Analysis

Time Complexity

O(n) – The add operation takes O(1) time as we simply append the new call time to the list. The ping operation iterates through the entire list of recorded call times. In the worst case, we might have 'n' call times stored. Therefore, the ping operation takes O(n) time where n is the number of calls made. The overall time complexity is dominated by the ping operation, resulting in O(n).

Space Complexity

O(N) – The provided solution stores every call that it receives. This means that, in the worst case, if we receive N calls, we will have to store N timestamps. This collection of timestamps represents the auxiliary space used, growing linearly with the number of calls. Therefore, the space complexity is O(N), where N is the number of calls received.

Optimal Solution

Approach

We need to keep track of recent calls within a specific timeframe. The optimal approach uses a data structure that efficiently adds new calls and removes old ones outside the timeframe, allowing us to quickly count the calls within the window.

Here's how the algorithm would work step-by-step:

Choose a data structure that automatically maintains order and allows efficient removal of elements from one end.
Whenever a new call arrives, add its timestamp to the end of the data structure.
While the first (oldest) timestamp in the data structure is outside the allowed timeframe (too old), remove it.
The number of timestamps remaining in the data structure represents the number of recent calls within the timeframe, so return that count.

Code Implementation

class RecentCounter:

    def __init__(self):
        self.call_timestamps = []

    def ping(self, time):
        # Add the new call timestamp to the list.
        self.call_timestamps.append(time)

        # Remove outdated timestamps from the beginning of the list.
        while self.call_timestamps and self.call_timestamps[0] < time - 3000:

            self.call_timestamps.pop(0)

        # The number of remaining timestamps is the count within the window.
        return len(self.call_timestamps)

Big(O) Analysis

Time Complexity

O(1) – Adding an element to the queue takes O(1) time. Removing elements from the front of the queue also takes O(1) time. The while loop iterates a maximum of k times, where k is the number of elements that need to be removed because they fall outside the 3000ms time window. However, in the problem statement the number of calls made to 'ping' are constrained, so the number of removals is bounded, independent of input size n. Therefore, each ping operation is performed in constant time, and the overall time complexity is O(1).

Space Complexity

O(W) – The primary auxiliary space is used by the data structure, likely a queue or list, used to store the timestamps of recent calls. In the worst-case scenario, where all calls within the last timeframe are stored, the size of this data structure grows linearly with the maximum number of calls within the allowed timeframe (the window size). Therefore, if we denote the maximum number of calls within the timeframe as W, the space complexity is O(W), because the list or queue will store up to W timestamps.

Edge Cases

Case	How to Handle
First call with a large timestamp (e.g., close to Integer.MAX_VALUE)	The implementation should correctly handle large timestamps without causing integer overflow issues when subtracting 3000.
Multiple calls with the exact same timestamp.	The queue will store duplicate timestamps, which is valid and doesn't affect the count.
Timestamps arriving in strictly increasing order.	This is the standard case and the queue will efficiently track the recent calls.
Timestamps arriving out of order (though this is unlikely in a real call stream).	The problem statement implies that the timestamps are in increasing order, so we don't need to handle cases where t < previous timestamp; however, if required, additional logic would be needed to maintain the order.
A very large number of calls over a long period, potentially causing memory issues if the queue grows unboundedly.	The queue will only ever contain calls within the past 3000ms, so it's inherently bounded and should not cause memory overflow.
Calling ping with a negative timestamp. The problem statement specifies that timestamps are milliseconds so they can't be negative.	It is invalid input, potentially throw an IllegalArgumentException or return 0, documenting the expected behavior.
Calling ping repeatedly with timestamps that are all very close together (e.g., all within a 1ms window).	The queue will fill up quickly and require frequent removals, but the algorithm should still function correctly.
Initial calls all fall outside of subsequent query windows (t-3000, t).	The queue will initially contain calls that are irrelevant to later queries, but they will be correctly removed when they fall outside the 3000ms window.