Design prefix-sum function and max stack
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Question
LeetCode 303. Range Sum Query – Immutable (design a reusable prefix-sum function) LeetCode 716. Max Stack (similar design question)
https://leetcode.com/problems/range-sum-query-immutable/description/ https://leetcode.com/problems/max-stack/description/
Quick Answer: This question evaluates understanding of prefix-sum precomputation for constant-time range queries and the design of a max-enabled stack, focusing on data structure design, algorithmic complexity, and space-time trade-offs.
Design a function that processes a sequence of operations on a Max Stack. The stack supports the following commands: (1) "push x": push integer x onto the stack; (2) "pop": remove and return the top element; (3) "top": return the top element without removing it; (4) "peekMax": return the current maximum element; (5) "popMax": remove and return the maximum element; if multiple maxima exist, remove the one closest to the top. The function must return a list of integers representing the results of all operations that produce output (pop, top, peekMax, popMax), in order. All inputs are valid; operations that require a non-empty stack will not be called on an empty stack.
Constraints
- 1 <= len(operations) <= 20000
- Operations are one of: "push x", "pop", "top", "peekMax", "popMax"
- -10^9 <= x <= 10^9
- Operations that require a non-empty stack (pop, top, peekMax, popMax) will not be called on an empty stack
Hints
- Maintain a parallel stack that tracks the maximum at each depth.
- For popMax, move elements to a temporary buffer until the maximum is at the top, remove it, then restore the buffered elements.
- When restoring elements from the buffer, use the same push logic so the max-tracking structure stays correct.