Max in a Stack | Dataford Interview Questions

Max in a Stack

EasyPython

Problem

While processing an Autodesk Fusion command history, design a stack that supports push, pop, and get_max. Every get_max operation must return the largest value currently stored without scanning the stack.

Implement max_stack(operations). Each operation is represented as a list: ['push', value], ['pop'], or ['get_max']. A push changes the stack but produces no output. For every pop, return and remove the top value. For every get_max, return the current maximum without modifying the stack. Return all produced values in operation order.

The input will never attempt pop or get_max on an empty stack. Duplicate values and negative integers are allowed. Do not use Python's max during operation processing.

Formal Specification

Input: operations, a list of operation lists containing strings and, for push, one integer value.
Output: A list of integers produced by pop and get_max operations.

Constraints

1 <= len(operations) <= 10^5
-10^9 <= value <= 10^9
Every pop and get_max operation is valid
Each operation is push, pop, or get_max

Function Signature

def max_stack(operations):

The input will never attempt pop or get_max on an empty stack. Duplicate values and negative integers are allowed. Do not use Python's max during operation processing.

Formal Specification

Input: operations, a list of operation lists containing strings and, for push, one integer value.
Output: A list of integers produced by pop and get_max operations.