Coding questions · Zipline

Implement a Maximum-Tracking Stack

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.

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.

Maximum-Tracking Stack

Simulate push, pop, top, peekMax, and popMax; popMax removes the topmost maximum.

Examples

Example 1

Input: ((('push', 5), ('push', 1), ('push', 5), ('top',), ('popMax',), ('top',), ('peekMax',), ('pop',), ('top',)),)
Output: [5, 5, 1, 5, 1, 5]

Explanation: Standard MaxStack sequence.

Example 2

Input: ((('push', 3), ('push', 3), ('popMax',), ('pop',)),)
Output: [3, 3]

Explanation: Topmost maximum tie.