Problem 232405 · hard · Level 02 Linear Data Structures

The Heart-Rate Alarm

quartiles · interquartile range · outliers · sliding window · sorted lists

A fitness watch records one heart-rate reading per second. It raises an alarm when a reading is unusual compared with the previous w readings:

  • For reading i (with i >= w), take the window readings[i-w:i], sort it into s, and compute its quartiles with this rule: the p-th percentile is at position pos = p / 100 * (w - 1); with k the whole part of pos and f = pos - k, it is s[k] + f * (s[k+1] - s[k]) (or s[k] when k is the last index). Q1 uses p = 25 and Q3 uses p = 75.
  • With iqr = Q3 - Q1, reading i raises an alarm when it is strictly below Q1 - 1.5 * iqr or strictly above Q3 + 1.5 * iqr.
  • Readings with i < w never raise an alarm. Alarmed readings stay in the data and take part in later windows like any other reading.

Write iqr_alarms(readings, w) that returns the list of indices that raise an alarm, in increasing order. The recordings are long and the windows wide: sorting every window from scratch is too slow.

The setup provides heart_log(n, seed), which returns n readings of a slowly wandering heart rate with occasional sensor spikes.

Examples

Input:  readings = [70, 72, 71, 69, 70, 95, 71, 70, 40, 72], w = 5
Output: [5, 8]
Explanation: for i = 5 the window 70 72 71 69 70 sorts to 69 70 70 71 72, so Q1 = 70
(position 1), Q3 = 71 (position 3), iqr = 1 and the fences are 68.5 and 72.5: 95 raises
an alarm. For i = 8 the window 69 70 95 71 70 again gives fences 68.5 and 72.5, and 40
is below. For i = 9 the window 70 95 71 70 40 gives the same fences, and 72 is inside.

Constraints

  • 1 <= w <= 3000, 0 <= len(readings) <= 6 * 10**4
  • readings are whole numbers from 20 to 250

Goals

  • Apply the 1.5 × IQR rule to each new reading against the recent past
  • Keep a sliding window in sorted order instead of sorting it again for every reading
  • Compute quartiles with a stated interpolation rule
Starting Python…