Loading page…
Practice problem · medium
A maps app reads the speed of a road sensor every minute. A traffic alert fires when two readings are almost the same and were taken close together in time, which can mean a stuck sensor.
You get the readings in time order, a window of minutes, and a tolerance. Decide whether two readings within the window differ by at most the tolerance.
Write has_close_pair(readings, window, tol).
readings[i] is the speed read at minute i.i < j with j - i <= window and abs(readings[i] - readings[j]) <= tol.true if such a pair exists, and false otherwise.Input: readings = [10, 25, 12], window = 2, tol = 3
Output: trueThe trace uses buckets of width tol + 1, which is 4 here. A bucket holds at most one recent reading. For each reading it checks its own bucket and the two neighbours.
| i | reading | Bucket | Recent buckets | Close value found? |
|---|---|---|---|---|
| 0 | 10 | 2 | (none) | no |
| 1 | 25 | 6 | 2: 10 | no |
| 2 | 12 | 3 | 2: 10, 6: 25 | yes: 10 is in bucket 2 and |
The pair is at positions 0 and 2. They are 2 minutes apart, which is within the window, and 2 is within the tolerance 3. The output is true.
Input: readings = [1, 2, 3, 1], window = 2, tol = 0
Output: falseThe two 1s are 3 minutes apart, which is more than the window of 2, and no other pair is within the tolerance 0. The output is false.
Input: readings = [7, 7], window = 1, tol = 0
Output: trueThe two 7s are 1 minute apart and differ by 0, so the output is true.
0 ≤ readings.length ≤ 100,000 (minutes of readings)0 ≤ readings[i] ≤ 1,000,000 (speed readings)1 ≤ window ≤ 100,000 (minutes)0 ≤ tol ≤ 1,000,000 (tolerance)Checking every pair of positions costs about n × n / 2 steps, far over budget. Checking only the last window readings for each reading costs n × window, which is also 10^10 when both are 100,000. Buckets answer "is there a close value among the recent ones?" in a constant number of lookups.
has_close_pair · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.