FastPrepStack with Middle Operations
Problems/Stack with Middle Operations

Stack with Middle Operations

Microsoft logoMicrosoft● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: One question in a review of Microsoft SDE intern interviews was a linked-list stack that can also tell you its middle value.

The report does not list the operations, say what the middle is when the count is even, or give any limits. Here the stack supports push, pop, middle and deleteMiddle. The middle of an even count is the lower of the two centre values, and reads or removals only happen on a non-empty stack. The calls come as a list of strings. Using a linked list so that each call runs in O(1) time is a follow-up and is not tested.

Our version is about 75% the same as the reported question.

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 integer x on 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, or deleteMiddle, with exactly one space before x and x written as a plain decimal integer.
  • -10^9 <= x <= 10^9
  • pop, middle, and deleteMiddle are 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

Interview reports that mention this question

  • Microsoft SWE Intern, Mid 2025: 42 Experiences (Part 4 of 6)
  • Microsoft SWE Intern Interviews: 244 Experiences (Part 1 of 6)

Microsoft interview experiences

  • Microsoft Explore and Student SWE: 12 Experiences (Part 6 of 6)
  • Microsoft SWE Intern, Early 2025: 41 Experiences (Part 5 of 6)
  • Microsoft SWE Intern, Late 2025: 47 Experiences (Part 3 of 6)
  • Microsoft SWE Intern, Early 2026: 54 Experiences (Part 2 of 6)
All Microsoft interview questionsSee Microsoft hiring insights
Saved
class Solution {
    public int[] processStack(String[] operations) {
        // Write your code here.
    }
}
Checking account…