Katkat
Back

Replay Ops on a Freezer-Probe Stack That Tracks Its Minimum in O(1)

SnowflakeSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Replay a sequence of push/pop/peek/min-read operations on a stack of freezer temperature readings and return what each read produces, where reading the current minimum must be as fast as pushing or popping. Tests pairing a stack with running-minimum bookkeeping that stays correct through duplicate minimums and repeated pops.

A cold-storage unit logs temperature probe readings as a stack: the most recent reading is pushed on top, and operators can pop the most recent one off, peek at it, or ask for the coldest reading currently anywhere in the stack. All four operations must run in O(1) time — a facility pushes and pops readings constantly, and scanning the whole stack to answer "what's the coldest right now" on every query would be far too slow.

To make this testable as a single function, replay a list of operations against an initially empty stack and collect whatever the read operations produce.

Function Signature

def replay_probe_stack(ops: list[str], values: list[int]) -> list[int]:

Rules

  • ops[i] is one of "push", "pop", "peek", "coldest".
  • For "push", values[i] is the reading to push. For the other three operations, values[i] is 0 and should be ignored.
  • "pop" removes the most recently pushed reading and produces no output.
  • "peek" outputs the most recently pushed reading without removing it. "coldest" outputs the smallest reading currently in the stack, also without removing anything.
  • The stack may hold the same reading more than once (two different probes can report identical temperatures); each push is tracked as its own entry.
  • Return the outputs of "peek" and "coldest", in the order those operations occur. If neither ever occurs, return an empty list.
  • Every operation must be O(1); the grading includes sequences long enough that scanning the stack on every "coldest" call will time out.

Constraints

  • 1 <= len(ops) == len(values) <= 10^5
  • For "push", -2^31 <= values[i] <= 2^31 - 1.
  • "pop", "peek", and "coldest" are only issued when the stack is currently non-empty.

Example

Input:  ops    = ["push", "push", "push", "coldest", "pop", "peek", "coldest"]
        values = [-7,     3,      -9,     0,          0,     0,      0]
Output: [-9, 3, -7]

After the three pushes the stack (bottom to top) is [-7, 3, -9] and the coldest reading is -9. Popping removes -9; the new top is 3, so "peek" outputs 3, and with -9 gone the coldest remaining reading is -7.

Hints

Hint 1

Think about what you'd need to know instantly after every pop in order to answer 'coldest' without looking past the new top of the stack.

Hint 2

Store, alongside each pushed value, what the minimum of the stack *would be* if that value were the top — computed once, at push time.

Hint 3

Popping an element removes exactly its own stored minimum from consideration; the minimum for what remains was already computed and sitting one level down.

Hint 4

Two probes can report the same coldest value; make sure popping one copy doesn't lose track of the other still being in the stack.

Follow-up questions

  • How would you extend this to also answer 'warmest reading currently in the stack' in O(1), without doubling your memory usage if you can avoid it?
  • If the stack needed to support a 'replay the last N pops as pushes' undo feature, how would that interact with your running-minimum bookkeeping?
  • Could you implement this with O(1) *extra* space (beyond the values themselves), trading away O(1) time for push or pop, and when would that trade-off make sense?
  • How would you adapt this design to a queue instead of a stack, where you need the current minimum but removals happen from the opposite end from insertions?