Stack with Middle Operations
Updated
Problem statement
Design a stack that also keeps track of its middle value. Process the strings in operations from first to last. Each one is:
push x: put the integerxon top of the stack.pop: remove the top value and return it.middle: return the middle value without removing it.deleteMiddle: remove the middle value and return it. The other values keep their order.
If the stack holds n values, numbered 1 to n from the bottom, the middle is value number (n + 1) / 2, rounded down. So when n is even, the middle is the lower of the two centre values.
Return the values given back by pop, middle, and deleteMiddle, in the order of the operations. push gives back nothing.
Follow-up: using a linked list, can you make every operation run in O(1) time?
Function
processStack(operations: String[]) → int[]Examples
Example 1
operations = ["push 1","push 2","push 3","push 4","push 5","middle","deleteMiddle","middle","pop","middle"]return = [3,3,2,5,2]After five pushes the stack is 1, 2, 3, 4, 5 from bottom to top, and the middle is the 3rd value, 3. deleteMiddle removes and returns 3, leaving 1, 2, 4, 5. With 4 values the middle is the 2nd from the bottom, 2. pop removes the top, 5, leaving 1, 2, 4, whose middle is the 2nd value, 2.
Example 2
operations = ["push 7","middle","push -3","middle","deleteMiddle","pop"]return = [7,7,7,-3]With only 7 on the stack, the middle is 7. After pushing -3 there are two values; the middle is the lower one, 7. deleteMiddle removes 7, so only -3 is left, and pop returns it.
Constraints
1 <= operations.length <= 5000- Each operation is
push x,pop,middle, ordeleteMiddle, with exactly one space beforexandxwritten as a plain decimal integer. -10^9 <= x <= 10^9pop,middle, anddeleteMiddleare only called when the stack is not empty.
More Microsoft Onsite Interview questions
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Coin ChangeONSITE INTERVIEW · Seen Oct 2026
- Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
- Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
- Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Min StackCapital One · PHONE SCREEN · ONSITE INTERVIEWCapital One interview questions
- Max StackLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Max StackZipline · ONSITE INTERVIEW
- Max StackBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- LRU CacheLotusFlare · ONSITE INTERVIEW
- LRU Cache for Query ResultsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- KV Store with Nested TransactionsApplied Intuition · PHONE SCREEN · ONSITE INTERVIEWApplied Intuition interview questions
- LRU CacheJP Morgan Chase · ONSITE INTERVIEWJP Morgan Chase interview questions
- Min StackDP World · ONSITE INTERVIEW
- LRU Cache OperationsHevo Data · ONSITE INTERVIEW