Implement a Maximum-Tracking Stack
Company: Zipline
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Design a stack-like data structure that supports the following operations efficiently:
- `push(x)`: Push integer `x` onto the stack.
- `pop()`: Remove and return the element at the top of the stack.
- `top()`: Return the element at the top of the stack without removing it.
- `peekMax()`: Return the maximum value currently in the stack without removing it.
- `popMax()`: Remove and return the maximum value currently in the stack. If the maximum value appears multiple times, remove the occurrence closest to the top of the stack.
Assume `pop`, `top`, `peekMax`, and `popMax` are only called when the stack is non-empty.
Provide an optimal implementation and analyze the time complexity of each operation.
Quick Answer: This question evaluates competency in data structure design and algorithmic analysis, focusing on stack operations augmented with maximum-tracking and correctness when multiple maximal elements and ordering constraints are present.