Count Requests Dropped by Multiple Time Windows

Quick Overview

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

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.

|Home/Coding & Algorithms/Oracle
Oracle logo
Oracle
Jul 26, 2026, 12:00 AM
mediumSoftware EngineerOnsiteCoding & Algorithms
0
0

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.

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...