Your question is Real-Time Moving Median. Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
Google Pixel sensor services receive a continuous sequence of integer readings. For every complete sliding window of window_size consecutive readings, return its median as soon as the window is available.
Use two heaps to support insertion and deletion efficiently. If a window contains an even number of readings, define its median as the average of the two middle values. Return medians in the same order that the windows appear. Do not return a value until the first complete window has been received.
Implement moving_median(readings, window_size).
readings, a list of integers, and window_size, a positive integer.window_size. Integer medians should remain integers; even-sized windows may produce floating-point values.def moving_median(readings, window_size):