Loading page…
Practice problem · medium
A monitoring system records the latency of a service in milliseconds. A latency pattern is interesting when two readings differ by a fixed gap, such as 20 ms.
You get the readings of one hour and a gap d. You count the different pairs of values that are exactly d apart. A pair of values is counted once, however often each value appears.
Write count_pairs_apart(readings, d).
readings[i] is the i-th latency reading.a and b with b - a == d. Both values must appear in readings, and they must be at different positions.Input: readings = [3, 1, 4, 1, 5], d = 2
Output: 2The trace counts how often each value appears, then checks each distinct value v for the value v + 2.
| Distinct value | Partner (v + 2) | In the table? | Pairs so far |
|---|---|---|---|
| 3 | 5 | yes | 1 |
| 1 | 3 | yes | 2 |
| 4 | 6 | no | 2 |
| 5 | 7 | no | 2 |
The pairs are (1, 3) and (3, 5), so the output is 2. The second 1 in readings does not create a new pair, because pairs of values are counted once.
Input: readings = [1, 2, 3, 4, 5], d = 1
Output: 4The pairs are (1, 2), (2, 3), (3, 4) and (4, 5), so the output is 4.
Input: readings = [1, 1, 1, 3, 3], d = 0
Output: 2With d = 0, a value pairs with itself, and it needs at least two copies. The values 1 and 3 qualify, so the output is 2.
1 ≤ readings.length ≤ 100,000 (readings in an hour)0 ≤ readings[i] ≤ 500,000,000 (latency readings)0 ≤ d ≤ 500,000,000 (the gap)Checking every two positions costs about n × n / 2, about 5 × 10^9 at n = 100,000. A table of counts lets you ask "is v + d present?" in one step. The values and d are at most 5 × 10^8, so v + d is at most 10^9 and fits in a 32-bit int.
count_pairs_apart · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.