Loading page…
Practice problem · easy
A ride-hailing app raises its prices when too many riders ask for rides at once. To decide, it counts the ride requests that arrived in the last 3 seconds.
Each request has a time in milliseconds. The times arrive in increasing order, and no two requests share a time. A busy evening can bring 100,000 requests.
Write count_recent_requests(times).
times is a list of request times in milliseconds, in strictly increasing order.t, count the requests whose time is from t - 3000 to t, both included. The request itself counts.Input: times = [1, 100, 3001, 3002]
Output: [1, 2, 3, 3]| Step | Time t |
Oldest time that still counts | Queue after (front to back) | Count |
|---|---|---|---|---|
| 1 | 1 |
-2999 | 1 |
1 |
| 2 | 100 |
-2900 | 1 100 |
2 |
| 3 | 3001 |
1 | 1 100 3001 |
3 |
| 4 | 3002 |
2 (the 1 leaves) |
100 3001 3002 |
3 |
The request at 3002 looks back to time 2, so the request at time 1 no longer counts.
Input: times = [5000]
Output: [1]One request: it counts itself.
Input: times = [10, 4010, 8010]
Output: [1, 1, 1]The requests are 4,000 milliseconds apart, so each one is alone in its window.
1 ≤ length of times ≤ 10^51 ≤ times[i] ≤ 10^9A plan that counts all earlier requests again for each request costs up to n^2 / 2 steps. For 100,000 closely spaced requests that is 5 × 10^9, which is too slow.
The times are sorted, so a request that is too old for one window is too old for every later window. It can be thrown away for good.
count_recent_requests · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.