algoadvance

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 an empty request list.
• 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 have happened in the past 3000 milliseconds (including the current request). Specifically, return the number of ping calls that have been made from t - 3000 to t (inclusive).

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

Example:

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:

• The number of calls to ping will be at most 10^4.
• Each call to ping will have a strictly larger value of t than before.
• 1 <= t <= 10^9.

Clarifying Questions

1. Can we use any data structures to optimize the solution, such as queues or deques?
2. Is there a guaranteed order in which t values are provided?

Code

from collections import deque

class RecentCounter:

    def __init__(self):
        self.requests = deque()

    def ping(self, t: int) -> int:
        self.requests.append(t)
        while self.requests[0] < t - 3000:
            self.requests.popleft()
        return len(self.requests)


# Example Usage
# recentCounter = RecentCounter()
# print(recentCounter.ping(1))     # Output: 1
# print(recentCounter.ping(100))   # Output: 2
# print(recentCounter.ping(3001))  # Output: 3
# print(recentCounter.ping(3002))  # Output: 3

Strategy

1. Initialization: We use a queue (deque) to store the timestamps of the requests.
2. Adding Requests: Each new request is appended to the deque.
3. Removing Outdated Requests: For each ping, we check the deque and remove requests that are older than t - 3000.
4. Return Count: The length of the deque after the above operations gives the number of requests in the past 3000 milliseconds, including the current request.

Time Complexity

• Initialization: O(1)
• Each ping Call:
  • Adding a request to the deque: O(1)
  • Removing outdated requests from the deque: O(1) amortized over multiple calls

Hence, the time complexity for each ping call is O(1). The total time complexity, considering multiple pings, remains O(n), where n is the number of requests, thanks to efficient deque operations.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?