Min Stack
Updated
Problem statement
Build a stack that can also tell you its smallest value. The stack starts empty, and you get the calls in order as the list of strings operations:
push xputs the integerxon top. It gives no output.popremoves the top value and outputs it.topoutputs the top value and leaves it in place.getMinoutputs the smallest value in the stack and leaves the stack as it is.
Return an array with one output for each pop, top, and getMin, in the order they ran. If there are only pushes, return an empty array.
Aim for constant time per operation.
Function
processMinStack(operations: String[]) → int[]Examples
Example 1
operations = ["push 5","push 3","push 8","getMin","top","pop","getMin"]return = [3,8,8,3]After the three pushes, the stack is 5, 3, 8 from bottom to top. The smallest value is 3 and the top is 8. The pop removes 8 and outputs it. The smallest value is still 3. The pushes give no output, so the result has four values.
Example 2
operations = ["push 4","push 2","push 2","pop","getMin","pop","getMin"]return = [2,2,2,4]The value 2 is in the stack twice. The first pop removes one copy and outputs 2. The other copy is still there, so the smallest value is still 2. The second pop removes that copy and outputs 2. Only 4 is left, so the smallest value is now 4.
Example 3
operations = ["push -2147483648","push 2147483647","getMin","top","pop","getMin"]return = [-2147483648,2147483647,2147483647,-2147483648]These are the smallest and largest 32-bit values. The smallest value in the stack is -2147483648 and the top is 2147483647. The pop outputs 2147483647, and the smallest value stays the same. The gap between the two values is 2^32 - 1, which does not fit in a 32-bit integer.
Example 4
operations = ["push 1","pop","push 9","getMin"]return = [1,9]The pop outputs 1 and leaves the stack empty. The next push starts fresh, so the smallest value is 9. The old value 1 no longer counts.
Constraints
1 <= operations.length <= 3 * 10^4- Each operation is
push x,pop,top, orgetMin. xis a 32-bit signed integer, from-2^31to2^31 - 1.pop,top, andgetMinonly run when the stack is not empty.
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
Similar questions at other companies
- KV Store with Nested TransactionsApplied Intuition · PHONE SCREEN · ONSITE INTERVIEWApplied Intuition interview questions
- Min StackDP World · ONSITE INTERVIEW
- Code Editor FoldingJane Street · ONSITE INTERVIEWJane Street interview questions
- Undo and Redo Command HistoryNetflix · ONSITE INTERVIEWNetflix interview questions
- Min StackMicrosoft · PHONE SCREEN · ONSITE INTERVIEWMicrosoft interview questions
- Text Document HistoryNotion · PHONE SCREEN · ONSITE INTERVIEWNotion interview questions
- Equity Price History with O(1) StatisticsBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Nested Transaction Key-Value StorexAI · ONSITE INTERVIEWxAI interview questions
- Transactional In-Memory RedisHashiCorp · ONSITE INTERVIEWHashiCorp interview questions
- Key-Value Store with Nested TransactionsRippling · PHONE SCREEN · ONSITE INTERVIEWRippling interview questions