algoadvance

Leetcode 933. Number of Recent Calls

Problem Statement

1. Number of Recent Calls

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

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

Clarifying Questions

1. Can the time t be negative?
   • No, time t will always be non-negative.
2. What is the maximum value of t?
   • The constraints do not mention a maximum, but since it’s related to milliseconds, you can assume it’s always increasing and manageable within typical computational limits.
3. Can we assume consecutive calls to ping will use increasing values of t?
   • Yes, as per the problem statement.

Strategy

To handle the pings efficiently:

1. Utilize a queue to store the pings.
2. When a new ping is received:
   • Enqueue the current t.
   • Dequeue all elements from the front of the queue that are outside the [t-3000, t] time window.
   • The size of the queue represents the number of pings in the last 3000 milliseconds.
3. Return the size of the queue.

Let’s implement this strategy in Java.

Code

import java.util.LinkedList;
import java.util.Queue;

class RecentCounter {
    private Queue<Integer> queue;

    public RecentCounter() {
        this.queue = new LinkedList<>();
    }

    public int ping(int t) {
        this.queue.offer(t);
        while (this.queue.peek() < t - 3000) {
            this.queue.poll();
        }
        return this.queue.size();
    }
}

// Example usage
public class Main {
    public static void main(String[] args) {
        RecentCounter recentCounter = new RecentCounter();
        System.out.println(recentCounter.ping(1));    // returns 1
        System.out.println(recentCounter.ping(100));  // returns 2
        System.out.println(recentCounter.ping(3001)); // returns 3
        System.out.println(recentCounter.ping(3002)); // returns 3
    }
}

Time Complexity

• Each ping operation involves adding one element to the queue and potentially removing all elements less than t-3000.
• In the worst case, if there are n elements in the queue, all of them might be dequeued when a new ping arrives, but since each element is added and removed exactly once, the average time complexity per operation is effectively O(1).
• Therefore, the amortized time complexity for the ping function is O(1).

This ensures efficient handling of pings within the required time window.

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?