Number of Recent Calls

This question is asked by Google. Create a class CallCounter that tracks the number of calls a client has made within the last 3 seconds. Your class should contain one method, ping(int t) that receives the current timestamp (in milliseconds) of a new call being made and returns the number of calls made within the last 3 seconds.

Note: You may assume that the time associated with each subsequent call to ping is strictly increasing.

Example(s)

Example 1:

Input: ping(1), ping(300), ping(3000), ping(3002), ping(7000)
Output: 1, 2, 3, 3, 1
Explanation: 
- ping(1) → return 1 (1 call within the last 3 seconds)
- ping(300) → return 2 (2 calls within the last 3 seconds)
- ping(3000) → return 3 (3 calls within the last 3 seconds)
- ping(3002) → return 3 (3 calls within the last 3 seconds)
- ping(7000) → return 1 (1 call within the last 3 seconds)

Solution

JavaScript Solution

class CallCounter {
  constructor() {
    this.calls = [];
  }
  
  ping(t) {
    this.calls.push(t);
    while (this.calls.length && this.calls[0] < t - 3000) {
      this.calls.shift();
    }
    return this.calls.length;
  }
}

Python Solution

from collections import deque

class CallCounter:
    def __init__(self):
        self.calls = deque()
    
    def ping(self, t: int) -> int:
        self.calls.append(t)
        while self.calls and self.calls[0] < t - 3000:
            self.calls.popleft()
        return len(self.calls)

Complexity

• Time Complexity: O(1) amortized per ping - Each timestamp is added and removed at most once
• Space Complexity: O(w) - Where w is the maximum number of calls in any 3-second window

Interactive Code Runner

Test the Solution

JavaScript Solution

JavaScript CallCounter Solution

class CallCounter {
constructor() {
  this.calls = [];
}

ping(t) {
  this.calls.push(t);
  while (this.calls.length && this.calls[0] < t - 3000) {
    this.calls.shift();
  }
  return this.calls.length;
}
}

// Test the sequence from the example
const counter = new CallCounter();
console.log(counter.ping(1));    // 1
console.log(counter.ping(300));  // 2
console.log(counter.ping(3000)); // 3
console.log(counter.ping(3002)); // 3
console.log(counter.ping(7000)); // 1

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python CallCounter Solution

from collections import deque

class CallCounter:
  def __init__(self):
      self.calls = deque()
  
  def ping(self, t: int) -> int:
      self.calls.append(t)
      while self.calls and self.calls[0] < t - 3000:
          self.calls.popleft()
      return len(self.calls)

# Test the sequence from the example
counter = CallCounter()
print(counter.ping(1))    # 1
print(counter.ping(300))  # 2
print(counter.ping(3000)) # 3
print(counter.ping(3002)) # 3
print(counter.ping(7000)) # 1

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Takeaways

• Queue data structure is ideal for maintaining a sliding window of timestamps
• Amortized O(1) operations by ensuring each element is processed only twice (enqueue and dequeue)
• Strictly increasing timestamps allow simple append and popleft operations
• Window size is implicitly managed by the time difference, not a fixed count
• Edge cases include calls exactly 3000 ms apart or multiple calls at the same time (though assumed strictly increasing)