progress

~/problems / Arrays & hashing / Python toolkit

Moving average of the last k readings

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

easy ~15 min

A sensor sends one reading at a time, and the dashboard shows the average of the last k readings, smoothing out the noise.

Write moving_averages(readings: list[int], k: int) -> list[float] that returns, after each reading, the average of the last k readings, or of all readings so far while fewer than k have arrived.

moving_averages([10, 20, 30, 40], 3)    # [10.0, 15.0, 20.0, 30.0]
moving_averages([5, -1, 4], 1)          # [5.0, -1.0, 4.0]
moving_averages([], 4)                  # []

(The last value is (20 + 30 + 40) / 3: the 10 has left the window.)

  • 1 <= k <= 10^5 and 0 <= len(readings) <= 2 * 10^5; readings are integers in [-10^6, 10^6].
  • Answers within 10^-6 of the exact average are accepted.

⭐ Bonus: re-summing the window after every reading is O(n·k) and still passes; a speed test with 200,000 readings and k = 50,000 earns a star in O(n).

Show hint

collections.deque(maxlen=k) holds the window and drops its oldest reading by itself when a new one arrives. Keep a running total next to it: when the deque is full, subtract window[0] (the reading about to be dropped) before you append.

Topic: Python toolkit. Counter, deque, heapq, bisect, itertools: the standard library to know cold, and its traps.

0:00
Ctrl ' run · Ctrl ↵ submit
esc