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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Recent Calls

Difficulty: Easy

Problem Description

You have a RecentCounter class which counts the number of recent requests within a certain time frame. Implement the RecentCounter class with methods to initialize a counter and add new requests, returning the number of requests that have happened in the past 3000 milliseconds.

Key Insights

  • We need to maintain a record of requests and efficiently count how many of those requests fall within the last 3000 milliseconds from a given time t.
  • Since the value of t is guaranteed to be strictly increasing, we can utilize a queue to store the timestamps of the requests.
  • By removing timestamps that are outside the range [t - 3000, t], we can keep the queue size manageable and ensure efficient counting.

Space and Time Complexity

Time Complexity: O(1) for each ping call on average, since we add to the queue and remove from the front in constant time. Space Complexity: O(n), where n is the number of requests in the last 3000 milliseconds.

Solution

To solve the problem, we can leverage a queue data structure (or a list) to hold the timestamps of all requests. When a new request comes in via the ping method:

  1. We push the new timestamp onto the queue.
  2. We then remove timestamps from the front of the queue that are older than t - 3000.
  3. The size of the queue at this point will give us the number of requests that occurred within the last 3000 milliseconds.

Code Solutions

class RecentCounter:
    def __init__(self):
        self.requests = []

    def ping(self, t: int) -> int:
        self.requests.append(t)  # Add the new request timestamp
        # Remove timestamps that are older than t - 3000
        while self.requests[0] < t - 3000:
            self.requests.pop(0)
        return len(self.requests)  # Return the count of recent requests
← Back to All Questions