Number of Recent Calls

Share

Design RecentCounter class. ping(t) adds a request at time t and returns the number of requests in the past 3000ms [t-3000, t].

Example 1
ping(1)→1, ping(100)→2, ping(3001)→3, ping(3002)→3

Solution Approach

Use a Queue. Add t to queue. Remove elements older than t-3000. Return queue size.

  • Queue q.
  • ping(t): q.offer(t); while q.front < t-3000: q.poll().
  • Return q.size().
Java
import java.util.*;

class RecentCounter {
    Queue<Integer> q = new LinkedList<>();
    public int ping(int t) {
        q.offer(t);
        while (q.peek() < t - 3000) q.poll();
        return q.size();
    }
}
  • Time Complexity: O(1) amortized
  • Space Complexity: O(W) where W is window size