We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Recent Calls

Number: 969

Difficulty: Easy

Paid? No

Companies: Google, Bloomberg, Amazon, Affirm, Meta, Yandex, Yahoo, Databricks

Problem Description

Design a RecentCounter class that counts the number of recent requests (pings) that occurred within a fixed time window of the last 3000 milliseconds. Every time a new ping is made with time t, the class should return the count of all pings that happened in the inclusive time range [t - 3000, t].

Key Insights

  • Use a queue (or deque) to store the timestamps of the recent pings.
  • Since the ping times are guaranteed to be strictly increasing, the oldest time is always at the front of the queue.
  • For each new ping, remove elements from the front of the queue that fall outside the desired time window.
  • The remaining elements in the queue represent the pings in the time range [t - 3000, t].

Space and Time Complexity

Time Complexity: O(1) amortized per ping, since each timestamp is added and removed at most once. Space Complexity: O(n), where n is the number of pings stored (at most the number of pings within any 3000 ms window).

Solution

The solution uses a queue data structure to efficiently track and manage the timestamps of the ping requests. When a ping is made:

  1. Add the new timestamp to the queue.
  2. Remove all timestamps from the front of the queue that are less than t - 3000.
  3. The size of the queue then gives the count of recent pings.

This approach leverages the fact that the incoming timestamps are strictly increasing. The removal process ensures that no outdated ping remains in the queue, keeping the data structure clean and efficient.

Code Solutions

# Define the RecentCounter class
class RecentCounter:
    def __init__(self):
        # Initialize a list to act as the queue for storing timestamps
        self.queue = []

    def ping(self, t: int) -> int:
        # Append the new timestamp to the queue
        self.queue.append(t)
        # Remove timestamps from the queue that are older than (t - 3000)
        while self.queue[0] < t - 3000:
            self.queue.pop(0)  # Remove the oldest timestamp
        # Return the count of timestamps in the current valid window
        return len(self.queue)

# Example usage:
# recentCounter = RecentCounter()
# print(recentCounter.ping(1))     # returns 1
# print(recentCounter.ping(100))   # returns 2
# print(recentCounter.ping(3001))  # returns 3
# print(recentCounter.ping(3002))  # returns 3
← Back to All Questions