Design a stack with max removal
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Design a stack-like data structure for integers that supports the following operations efficiently:
- `push(x)`: insert `x` onto the stack.
- `pop()`: remove and return the top element.
- `top()`: return the top element without removing it.
- `peekMax()`: return the maximum value currently in the stack.
- `popMax()`: remove and return the maximum value currently in the stack. If the maximum value appears multiple times, remove the one closest to the top.
Implement the data structure and analyze the time complexity of each operation.
Quick Answer: This question evaluates data-structure design and algorithmic complexity analysis by requiring a stack-like structure that supports standard stack operations plus efficient maximum retrieval and targeted removal, assessing practical implementation skills and time-complexity reasoning at a practical application level.
Simulate push, pop, top, peekMax, and popMax. popMax removes the maximum closest to the top.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([['push',5],['push',1],['push',5],['top'],['popMax'],['top'],['peekMax'],['pop']],)
Expected Output: [None, None, None, 5, 5, 1, 5, 1]
Explanation: Classic max stack behavior.
Input: ([['pop'],['push',2],['peekMax']],)
Expected Output: [None, None, 2]
Explanation: Empty pop.
Hints
- Model object-style prompts as operation streams when needed.
- Handle empty and boundary cases before the main logic.