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.
# 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.
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.