Implement a stack supporting max and popMax
Company: LinkedIn
Role: Data Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Design a data structure that behaves like a stack but also supports retrieving and removing the current maximum value.
Implement a class `MaxStack` with the following operations:
- `push(x)`: Push integer `x` onto the stack.
- `pop()`: Remove and return the top element.
- `top()`: Return the top element without removing it.
- `peekMax()`: Return the maximum element currently in the stack without removing it.
- `popMax()`: Remove and return the maximum element currently in the stack. If there are multiple occurrences of the maximum value, remove the one closest to the top of the stack.
All operations should be efficient (better than linear time when possible).
Quick Answer: This question evaluates understanding of data structures and algorithmic complexity, focusing on designing a stack variant that supports efficient retrieval and removal of the current maximum while preserving stack behavior.