algoadvance

Leetcode 933. Number of Recent Calls

Problem Statement

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 no requests.
• int ping(int t) Adds a new request at time t (in milliseconds), where t represents some time in the past. Returns the number of requests 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 the previous call.

Clarifying Questions

1. Can we assume that t is a non-negative integer?
   • Yes, t is guaranteed to be a non-negative integer and always strictly increasing with each call to ping.
2. Is there a maximum value for t?
   • The value of t can go up to 10^9, but each call to ping will have a strictly increasing value of t.

Strategy

The solution revolves around maintaining a list of request times and efficiently counting how many of them fall within the last 3000 milliseconds of a given request time. Here’s a step-by-step approach:

1. Use a queue to store the timestamps of the requests.
2. For each new ping(t), add t to the queue.
3. Remove any timestamps from the queue that are older than t - 3000.
4. The size of the queue at this point will give the number of requests within the last 3000 milliseconds.

The use of a queue ensures that we can efficiently add new request times and remove old ones, keeping the operations approximately O(1) for each call of ping.

Code

#include <queue>

class RecentCounter {
public:
    RecentCounter() {
        
    }
    
    int ping(int t) {
        // Add the new request timestamp `t`
        q.push(t);
        
        // Remove all requests that are older than `t - 3000`
        while (!q.empty() && q.front() < t - 3000) {
            q.pop();
        }
        
        // The size of the queue is the number of recent requests
        return q.size();
    }
    
private:
    std::queue<int> q; // Queue to store the timestamps of the requests
};

Time Complexity

• Initialization (RecentCounter constructor): O(1)
• ping(int t): Each request is added to the queue and outdated requests are removed. Both enqueue and dequeue operations are O(1) amortized. Hence, the complexity of each ping operation is O(1) on average.

This approach ensures efficient management of the list of requests and handles the problem constraints effectively.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?