Max Stack in O(1) | Dataford Interview Questions

While building an in-memory component for a HashedIn by Deloitte service, you need a stack that can report its current maximum value efficiently. Implement max_stack so that every push, pop, and max operation runs in constant time.

Formal Specification

The input is a list of operations. Each operation is represented as a list:

["push", value] adds an integer to the stack and produces no output.
["pop"] removes and returns the top value.
["max"] returns the largest value currently in the stack without removing it.

Return a list containing the results of every pop and max operation, in execution order. Inputs will never attempt pop or max on an empty stack.

Constraints

1 <= operations.length <= 10^5
-10^9 <= value <= 10^9
Every operation is valid.
Each push operation contains exactly one integer.
Pop and max operations are only used when the stack is non-empty.

Function Signature

def max_stack(operations):

Your question is Max Stack in O(1). Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem