FastPrepStack with Constant-Time Middle Queries
Problems/Stack with Constant-Time Middle Queries

Stack with Constant-Time Middle Queries

Amazon logoAmazon● MediumFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in an Amazon SDE2 interview list as a stack supporting push, pop, middle, and top in constant time. The source does not define a callable input shape, even-size middle choice, empty-stack results, or bounds; this practice version uses a finite batch of string operations, returns one string per non-push operation, chooses the lower middle at even sizes, returns EMPTY on an empty stack, and permits at most 100,000 operations. Problem match confidence: approximately 86%.

Process a sequence of stack operations. Each operation is ["push", value], ["pop"], ["top"], or ["middle"]. Values are signed decimal integers encoded as strings.

Return one string for every non-push operation. For an empty stack, return EMPTY. For an even-sized stack, middle returns the lower middle element, the one closer to the bottom. Every operation must run in constant time; preallocated array storage is allowed.

Function

processMiddleStack(operations: String[][]) → String[]

Examples

Example 1

operations = [["push","1"],["push","2"],["push","3"],["middle"],["top"],["pop"],["middle"]]return = ["2","3","3","1"]

The lower middle of three values is 2; after popping 3, the lower middle of [1,2] is 1.

Example 2

operations = [["top"],["middle"],["pop"]]return = ["EMPTY","EMPTY","EMPTY"]

All three queries use the empty sentinel.

Example 3

operations = [["push","-4"],["middle"],["pop"]]return = ["-4","-4"]

A one-element stack has the same top and middle.

Constraints

  • 1 ≤ operations.length ≤ 100000.
  • Every operation has one of the four documented forms.
  • Push values are integers in [-10^9, 10^9].
  • The output contains one entry for every non-push operation.

More Amazon problems

  • Count Adjacent Symbol Pairs for BPEONSITE INTERVIEW · Seen Nov 2026
  • First Non-Repeating CharacterOA · ONSITE INTERVIEW · Seen Nov 2026
  • Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
See Amazon hiring insights
Saved
class Solution {
    public String[] processMiddleStack(String[][] operations) {
        // write your code here
    }
}
Checking account…