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.
Simulate push, pop, top, peekMax, and popMax; popMax removes the topmost maximum.
Examples
Input: ((('push', 5), ('push', 1), ('push', 5), ('top',), ('popMax',), ('top',), ('peekMax',), ('pop',), ('top',)),)
Expected Output: [5, 5, 1, 5, 1, 5]
Explanation: Standard MaxStack sequence.
Input: ((('push', 3), ('push', 3), ('popMax',), ('pop',)),)
Expected Output: [3, 3]
Explanation: Topmost maximum tie.