Quick Overview

Count how many requests a gateway drops when it enforces three limits at once: 3 per second, 20 per 10 seconds and 60 per 60 seconds. Arrival times are sorted, and dropped requests still count toward later limits. The problem tests sliding-window reasoning, exact window boundaries and improving on a naive scan.

Count requests dropped by stacked 1-, 10- and 60-second rate limits

Company: Oracle

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

A gateway enforces three rate limits at once: at most 3 requests in any one second, at most 20 requests in any 10-second span, and at most 60 requests in any 60-second span. Given the arrival times of the requests in sorted order, return how many requests are dropped. A dropped request still counts toward the limits that later requests are checked against. Be ready to explain a straightforward approach first and then a faster one, with its time and space complexity. ### Function Signature ```python def count_dropped(timestamps: list[int]) -> int: ``` ### Rules - `timestamps[i]` is the arrival time of request `i`, in whole seconds. Requests are checked one at a time, in list order. - For request `i` arriving at time `t`, count the requests `j <= i` (request `i` itself included, and dropped requests included) whose arrival time lies in each window: - the one-second window: exactly `t`, limit 3; - the 10-second window: from `t - 9` to `t` inclusive, limit 20; - the 60-second window: from `t - 59` to `t` inclusive, limit 60. - Request `i` is dropped if any of the three counts exceeds its limit. A request that breaks several limits is still one dropped request. - Return the total number of dropped requests. ### Constraints - `1 <= len(timestamps) <= 10^5` - `1 <= timestamps[i] <= 10^9` - `timestamps` is sorted in non-decreasing order; equal values are allowed. ### Examples **Example 1** ```text Input: timestamps = [1, 1, 1, 1, 2] Output: 1 ``` The fourth request at second 1 makes that second's count 4, which exceeds 3. The request at second 2 breaks no limit. **Example 2** ```text Input: timestamps = [1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6] Output: 4 ``` The fourth, fifth and sixth requests at second 1 break the one-second limit. Seconds 2 to 6 have three requests each. The last request, at second 6, has 21 requests in its 10-second window (seconds -3 to 6), counting the three dropped ones, so it is dropped as well. If dropped requests did not count, it would have been accepted. **Example 3** ```text Input: timestamps = [1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 10, 11] Output: 0 ``` The request at second 10 has exactly 20 requests in its window (seconds 1 to 10). The request at second 11 has a window of seconds 2 to 11, which no longer contains the request at second 1, so it also sees exactly 20. No limit is exceeded.

Overview: Count how many requests a gateway drops when it enforces three limits at once: 3 per second, 20 per 10 seconds and 60 per 60 seconds. Arrival times are sorted, and dropped requests still count toward later limits. The problem tests sliding-window reasoning, exact window boundaries and improving on a naive scan.

Read the full Oracle Software Engineer interview experience this question came from

A gateway enforces three rate limits at once: at most 3 requests in any one second, at most 20 requests in any 10-second span, and at most 60 requests in any 60-second span. You are given the arrival times of the requests, in sorted order. Return how many requests are dropped. A dropped request still counts toward the limits that later requests are checked against. Implement `count_dropped(timestamps)`. ### Rules - `timestamps[i]` is the arrival time of request `i`, in whole seconds. Requests are checked one at a time, in list order. - For request `i` arriving at time `t`, count the requests `j <= i` (request `i` itself included, and dropped requests included) whose arrival time lies in each window: - the one-second window: exactly `t`, limit 3; - the 10-second window: from `t - 9` to `t` inclusive, limit 20; - the 60-second window: from `t - 59` to `t` inclusive, limit 60. - Request `i` is dropped if any of the three counts exceeds its limit. A request that breaks several limits is still one dropped request. - Return the total number of dropped requests, an integer from 0 to `len(timestamps)`. Requests that appear later in the list never count toward an earlier request, even when they share its timestamp. No timestamp or result exceeds 2^31 - 1, so 32-bit integers suffice in every language. ### Example 1 ```text Input: timestamps = [1, 1, 1, 1, 2] Output: 1 ``` The fourth request at second 1 makes that second's count 4, which exceeds 3. The request at second 2 breaks no limit. ### Example 2 ```text Input: timestamps = [1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6] Output: 4 ``` The fourth, fifth and sixth requests at second 1 break the one-second limit. Seconds 2 to 6 have three requests each. The last request, at second 6, has 21 requests in its 10-second window (seconds -3 to 6), counting the three dropped ones, so it is dropped as well. If dropped requests did not count, it would have been accepted. ### Constraints - `1 <= len(timestamps) <= 10^5` - `1 <= timestamps[i] <= 10^9` - `timestamps` is sorted in non-decreasing order; equal values are allowed.

Constraints

  • 1 <= len(timestamps) <= 10^5
  • 1 <= timestamps[i] <= 10^9
  • timestamps is sorted in non-decreasing order; equal values are allowed.

Examples

Input: ([1, 1, 1, 1, 2],)

Expected Output: 1

Explanation: Source Example 1 (length 5): the fourth request at second 1 is the only one over the one-second limit.

Input: ([1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6],)

Expected Output: 4

Explanation: Source Example 2 (length 21): three drops at second 1, and the last request at second 6 sees 21 requests in its 10-second window only because the dropped ones still count.

Hints

  1. Start from the rules directly: for a single request, how would you count the requests at or before it that fall in each of the three windows? Then look for work that repeats from one request to the next.
  2. Dropped requests still count toward later windows, so whether one request is dropped never changes the counts any other request sees.
  3. The list is sorted, so the requests inside any window that ends at time t sit next to each other in the list.

Loading coding console...

Show the approach

Approach

Because dropped requests still count, the three window counts for request i depend only on the timestamps, never on earlier drop decisions. A straightforward approach scans back from i over the earlier requests for each window, which is O(n^2) in the worst case (or O(n log n) with a binary search for each window's left edge). The faster approach keeps one left pointer per window. For a window of width w (1, 10 or 60 seconds), the requests j <= i inside it are exactly positions p..i, where p is the first index whose timestamp is at least t - w + 1; this holds because the list is sorted. As i increases, t - w + 1 never decreases, so each pointer only moves forward and moves at most n times in total, giving O(n) time with O(1) extra space. The count is i - p + 1; request i is dropped when any count exceeds its limit (3, 20 or 60), and it adds exactly one to the answer however many limits it breaks. Edge cases: a pointer never passes i because timestamps[i] = t >= t - w + 1; for small t the left edge t - w + 1 can be zero or negative, which simply keeps every earlier request in the window; equal timestamps later in the list are not counted for request i because the count stops at i; an empty list (outside the constraints) returns 0.

Time complexity:
O(n)
Space complexity:
O(1)