Loadingone moment…
Sign in to run and submit your work
Reading is open to everyone. Running code and saving drafts need an account so your work is yours and comes back on your next visit.
or
CODE WORKSPACE
A dashboard shows the highest CPU reading over the last k minutes, updated every minute. For a list of per-minute readings, it needs the highest reading in every window of k minutes in a row.
Write rolling_max(values, k). values is a list of numbers, and k is the window size. Return a list with the largest value of each window of k consecutive values, from the first window to the last.
Function to write
rolling_max(values: list[float], k: int) -> list[float]A list with the largest value of each window of k consecutive values, in order.
How to approach it
Keep a deque of indexes whose values are in falling order. Drop smaller values from the back when a bigger one arrives, and drop the front when it is too old.
Sample cases
+ 3 held back until you submit
a short series
Six windows of three. The maximums are 3, 3, 5, 5, 6, 7.
Input
Argument 1
[
1,
3,
-1,
-3,
5,
3,
6,
7
]Argument 2
3Returns
[
3,
3,
5,
5,
6,
7
]falling values
The largest in each window is always the first one, which then leaves the window.
Input
Argument 1
[
9,
7,
5,
3,
1
]Argument 2
2Returns
[
9,
7,
5,
3
]window of one
Every window holds one value, so the answer is the list itself.
Input
Argument 1
[
4,
2,
8
]Argument 2
1Returns
[
4,
2,
8
]empty list
No values means no windows.
Input
Argument 1
[] (empty list)
Argument 2
3Returns
[] (empty list)
Constraints
values[0:k], the last is values[-k:]. There are len(values) - k + 1 windows.k <= 0, if k is larger than the list, or if the list is empty.max on every window is O(n * k).Worked example
Take [1, 3, -1, -3, 5, 3, 6, 7] and k = 3. The windows are [1, 3, -1], [3, -1, -3], [-1, -3, 5], [-3, 5, 3], [5, 3, 6] and [3, 6, 7]. Their maximums are 3, 3, 5, 5, 6, 7. With a deque: when 3 arrives, the smaller 1 behind it can never be the maximum again, so it is removed. The front of the deque is always the maximum. Items at the front are dropped when they are too old to be in the window.
The trap: a range that stops at len(values) - k leaves out the last window, so the answer ends with 6 and never reports 7.
What this tests
The monotonic deque, the idea behind 'Sliding Window Maximum'. The deque holds indexes whose values are in falling order. New values remove smaller values from the back, and old indexes leave from the front. Each index goes in once and out once, so the total cost is O(n). Data engineers use it for rolling maximums and minimums over metric series.
rolling_max(values: list[float], k: int) -> list[float]Submit for review to find out what your query gets right, what it gets wrong, and how it compares with the best working query for this exercise.
This scenario runs a full workspace — editor, canvas and results side by side. It needs a laptop or desktop to be usable. Open this page on a bigger screen to start building.