Prompt and context
Implement a stack with push, pop, top, and getMin. Every operation must be O(1), and empty-stack behavior must be explicit. The question fits coding, backend, and library roles. The key is maintaining the minimum for every stack depth, not memorizing an API.
What the interviewer is testing
The invariant
The auxiliary structure at depth d stores the minimum of the first d values. The main and auxiliary stacks remain the same length.
Duplicate minima
When a new value equals the current minimum, it must still be recorded. Otherwise popping one copy loses the correct minimum.
Errors and boundaries
pop, top, and getMin on an empty stack need a consistent contract: exception, option, or error code. A silent sentinel is unsafe.
Complexity
Every operation touches only the top, so time is O(1) and extra space is O(n). A scan during getMin does not satisfy the requirement.
Questions to clarify first
- What should an empty operation return: exception, option, or error code?
- Can values be negative, repeated, or near integer limits?
- Is a generic comparator required, or only integers?
- Should the API return a minimum index or occurrence count?
- Is thread safety or a lock-free implementation required?
- Should tests cover individual calls or random operation sequences?
A 30-second answer
“I would keep two equal-length stacks: values and mins. The top of mins stores the minimum of all values currently present. On push, I push min(x, current minimum); on pop, I pop both; top and getMin read the relevant top. Every operation is O(1), with O(n) extra space. I record duplicate minima, define an empty-stack error contract, and check random sequences against a slower reference list.”
Step-by-step deep answer
Step 1: State the invariant
Let S be the value stack and M the auxiliary stack. For every depth d, M[d] equals the minimum of S[0..d]. Their lengths are always equal.
Step 2: Design push
If M is non-empty, push min(x, M.top()) onto M; otherwise push x. Then push x onto S. The new auxiliary top is the prefix minimum.
Step 3: Design pop and queries
Pop removes one item from both stacks. top reads S.top(), and getMin reads M.top(). No scan is needed.
Step 4: Preserve duplicates
After pushing 2, 1, 1, M is 2, 1, 1. Popping once must still return 1. Recording only strictly smaller values breaks the invariant.
Step 5: Define errors and types
An empty stack can throw EmptyStackError or return a typed Result. A generic implementation should accept a total-order comparator and define equality consistently.
Step 6: Prove and test complexity
All four operations are O(1), with O(n) auxiliary space. A random test can maintain a normal list as an oracle and compare top, minimum, size, and errors after every operation.
~~~python class MinStack: def push(self, value): ... def pop(self): ... def top(self): ... def get_min(self): ... ~~~
Model answer
“I would maintain values and mins. mins[i] is the minimum of values[0..i], so the stacks have equal length. push stores the value and its new prefix minimum; an empty mins stack stores the value directly. pop removes from both, while top and getMin read the corresponding top.
Duplicate minima must be stored. For 2, 1, 1, mins is 2, 1, 1; otherwise one pop would incorrectly return 2. Empty operations use an explicit error contract. Time is O(1) per operation and extra space is O(n). I would test empty, negative, duplicate, alternating, and random sequences against a list-based oracle.”
Common mistakes
- Scanning the value stack during getMin, making it O(n).
- Recording only strictly smaller values and losing duplicate minima.
- Popping only the main stack and desynchronizing the structures.
- Keeping one global minimum that cannot be restored after pop.
- Returning zero for an empty stack and confusing it with valid input.
- Ignoring negative values or integer limits.
- Calling an amortized bound strict O(1) without justification.
- Claiming generic-object support without defining a comparator.
Follow-up questions
Follow-up 1: Can you use one stack?
Yes. Store a pair of value and prefix minimum in each entry. The invariant is unchanged and space remains O(n).
Follow-up 2: How would you add getMax?
Maintain a maximum-prefix stack too, or store value, min, and max in each entry. Time remains O(1) per operation and total space O(n).
Follow-up 3: How would you return the minimum count?
Store min and count in each auxiliary entry. Equal values increment count, and pop restores the previous entry. Define duplicate and rollback semantics explicitly.
Follow-up 4: How would you make it thread-safe?
Protect both stacks with one mutex around each logical operation. Separate locks could expose an inconsistent intermediate state. Lock-free designs require an atomic composite state and memory-reclamation discussion.
Follow-up 5: How do you prove correctness?
Use induction. The empty stack satisfies the invariant; push computes the new prefix minimum; pop restores the previous record. Therefore getMin always returns the minimum of the current value stack.