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 monitor keeps a stack of recent latency readings. It must be able to push a new reading, remove the latest reading, and look at the latest reading. It must also tell the smallest reading now on the stack. Looking through the whole stack for the smallest each time is too slow.
Write run_min_stack(operations). operations is a list of ["push", value], ["pop"], ["top"] and ["min"] lists. Run them in order. Return a list with one result for each pop, top and min, in order.
Function to write
run_min_stack(operations: list[list]) -> listA list with one result for each pop, top and min operation, in order; None when the stack is empty.
How to approach it
Keep a second stack with the same height as the first. Each level of it stores the smallest value at or below that level of the first stack.
Sample cases
+ 2 held back until you submit
the minimum comes back after a pop
With 5, 2, 8 on the stack the minimum is 2. After 8 and 2 are popped, only 5 is left, so the minimum is 5 again.
Input
Argument 1
[
[
'push',
5
],
[
'push',
2
],
[
'push',
8
],
[
'min'
],
[
'pop'
],
[
'pop'
],
[
'min'
],
[
'top'
]
]Returns
[
2,
8,
2,
5,
5
]equal minimums
Two copies of the smallest value. After one is popped the other still counts, so the minimum is still 3.
Input
Argument 1
[
[
'push',
3
],
[
'push',
3
],
[
'pop'
],
[
'min'
]
]Returns
[
3,
3
]negative values
Minimums follow the stack as values come and go, including negative values.
Input
Argument 1
[
[
'push',
-1
],
[
'push',
4
],
[
'min'
],
[
'push',
-7
],
[
'min'
],
[
'pop'
],
[
'min'
]
]Returns
[
-1,
-7,
-7,
-1
]nothing to do
No operations give no results.
Input
Argument 1
[] (empty list)
Returns
[] (empty list)
Constraints
push adds a value on top and adds nothing to the results.pop removes the top value and adds it to the results.top adds the top value to the results, and removes nothing.min adds the smallest value now on the stack to the results.pop, top and min each add None.min() on the whole stack.Worked example
Take push 5, push 2, push 8, min, pop, pop, min, top. Keep a second list that stores the smallest value at each level. After 5 it is [5], after 2 it is [5, 2], and after 8 it is [5, 2, 2]. min reads the last entry, which is 2. pop returns 8 and removes one entry from the second list. pop returns 2 and removes another: the second list is [5]. min reads 5. top is 5. The results are [2, 8, 2, 5, 5].
The trap: one smallest variable that is never reset still says 2 after the 2 has been popped.
What this tests
A min stack, the idea behind 'Min Stack'. The method is to store, with each item, the minimum that was true when it was pushed. Popping an item also pops its minimum, so the old minimum comes back by itself. Data engineers use the same idea for running minimums and maximums over a window that can shrink.
run_min_stack(operations: list[list]) -> listSubmit 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.