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.