Min Stack With O(1) Min | Dataford Interview Questions

Lyft Dispatch needs a stack-like structure for processing prioritized driver events. Implement a function that processes push, pop, and get_min operations while ensuring that each operation runs in constant time.

Use an auxiliary stack to track the minimum value currently present. Duplicate minimum values must be handled correctly.

Formal Specification

Implement min_stack_operations(operations), where operations is a list of operations:

['push', value] adds an integer to the top of the stack and produces no output.
['pop'] removes and returns the top value.
['get_min'] returns the smallest value currently in the stack.

Return a list containing the results of every pop and get_min operation, in execution order. Inputs will not call pop or get_min when the stack is empty.

Constraints

1 <= len(operations) <= 10^5
-10^9 <= value <= 10^9
Every operation is valid for the current stack state
Each stack operation must run in O(1) time

Function Signature

def min_stack_operations(operations):

Your question is Min Stack With O(1) Min. 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