Count Requests Dropped by Multiple Time Windows
Company: Oracle
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Count Requests Dropped by Multiple Time Windows
Implement `count_dropped(timestamps)` for nondecreasing integer seconds. For zero-based request index `i`, drop the request if any of these predicates is true:
- `i >= 3` and `timestamps[i] == timestamps[i - 3]`;
- `i >= 20` and `timestamps[i] - timestamps[i - 20] < 10`;
- `i >= 60` and `timestamps[i] - timestamps[i - 60] < 60`.
Dropped requests remain in the indexed sequence when testing later requests. A difference exactly equal to `10` or `60` is outside that corresponding window. For example, `[1,1,1,1]` drops one request. Twenty-one requests spread as `[0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,10,10]` drop none because the boundary difference is exactly `10`; changing the final two timestamps to produce three requests at `9` makes the last request fail the 10-second predicate.
Constraints: up to `200000` timestamps, each in `[0, 10^12]`. Return only the integer number dropped.
```hint Use positions in the sorted list
For request index `i`, compare it with fixed earlier indices and their timestamp differences; do not remove dropped requests.
```
Quick Answer: Implement `count_dropped(timestamps)` for nondecreasing integer seconds. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Given nondecreasing integer request timestamps, count request indices that satisfy at least one specified rate predicate: the request matches the timestamp three positions earlier; it is less than 10 seconds after the request twenty positions earlier; or it is less than 60 seconds after the request sixty positions earlier. Dropped requests remain in the indexed sequence, and a request matching multiple predicates is counted once. Differences exactly 10 or 60 do not trigger those windows.
Constraints
- 0 <= len(timestamps) <= 200000, and timestamps is nondecreasing.
- Every timestamp is an integer from 0 through 10^12.
- Window differences use strict comparisons: exactly 10 or 60 is outside that predicate, and each request contributes at most one to the result.
Examples
Input: ([],)
Expected Output: 0
Explanation: No request can be dropped from an empty sequence.
Input: ([5],)
Expected Output: 0
Explanation: A singleton cannot trigger any window.
Hints
- Test sequences just below and exactly on the 10-second and 60-second boundaries.
- Include one request that satisfies more than one predicate and confirm it counts once.
- Use a sequence where earlier dropped requests must remain present for later index comparisons.