Skip to content
Tech Interview Prep
Technical interview guide

Stacks

LIFO ordering for tracking nested structure: matching parentheses, undo history, and monotonic sequences.

Read
42 min
Practice MCQs
25
Interview Q&A
25
Edition
v6
Editorial status
Reviewed

Scope: Language-neutral, with container costs and recursion limits cited from CPython 3.14, the C++ standard containers, and java.util as of Java 21.

Curated: · Written: · Reviewed:

25 questions

MCQ-18A drawing app keeps an undo stack of strokes and a redo stack. A user draws strokes A, B, C, D in order, presses undo three times, draws stroke E, then presses redo once. Which strokes are on the canvas?
MCQ-25A service ingests a stream of events. `open(id)` records an id as open; `close(id)` is valid only if `id` is the most recently opened id still open, and the service must reject the first `close` that violates this. A first implementation tracked open ids in a FIFO queue and rejected the valid stream `open(1), open(2), close(2), open(3), close(3), close(1)` at `close(2)`. Which structure should the service use instead?
MCQ-1A calculator service evaluates postfix (reverse-Polish) expressions with a single stack. Numbers are pushed as they arrive; each operator pops the top two values, applies itself with the second-popped value on the left, and pushes the result. The service is handed the token stream `5 1 2 + 4 * + 3 -`. What value does it return?
MCQ-17A design doc specifies a stack that supports push, pop and getMin, all in O(1) worst case, and notes that the stack may hold duplicate values. Which description of the implementation is correct?
MCQ-16A service implements a FIFO queue with two stacks. `push(v)` appends `v` to `inbox`. `pop()` runs `while inbox: outbox.append(inbox.pop())` and then returns `outbox.pop()`: the transfer runs on every pop, with no check on whether `outbox` is already non-empty. The service processes this call sequence: `push(1)`, `push(2)`, `push(3)`, `pop()`, `push(4)`, `pop()`, `pop()`, `pop()`. What does it return, in order?
MCQ-3A log-ingest service validates bracket nesting in each line with a fixed-size stack array: each opener is pushed, each closer pops and must match the top, and a push onto a full array aborts the line. The team must size the array so that the line `(([{}]))()` never aborts. What is the smallest capacity that works?
MCQ-4A nightly job validates bracket sequences in 1.2M config snippets with a stack-based checker. The checker must return True or False for every snippet and never raise; any exception aborts the whole run. Last night the run aborted with `IndexError: pop from empty list` on a snippet containing `") ("` (a closer with nothing on the stack). The loop is: ```python for ch in s: if ch in '([{': stack.append(ch) else: if stack.pop() != pairs[ch]: return False return not stack ``` Which change makes the checker meet its contract?
MCQ-7A compiler's expression front end converts infix to postfix with a stack before code generation. Its operator table gives `+` and `-` precedence 1 and `*` and `/` precedence 2, all four left-associative; `(` is pushed on sight, a `)` pops operators until the matching `(` is discarded, and operands are emitted as they are read. The front end is handed the infix string `a + b * (c - d) - e`. Which postfix string does it emit?
MCQ-11An expression evaluator uses shunting-yard with PREC = {"+":1, "-":1, "*":2, "/":2, "^":3} and pops the operator stack while the top's precedence is >= the incoming operator's. It returns 64 for `2 ^ 3 ^ 2`, but the spec requires 512; it returns 1 for `8 / 4 / 2`, which is correct. Which change fixes `^` while keeping `/` correct?
MCQ-15A service walks a parse tree to emit tokens in preorder. For the current input the tree is: ``` 1 / \ 2 3 / \ \ 4 5 6 ``` and the walk is: ```python stack = [root] out = [] while stack: node = stack.pop() out.append(node.val) if node.left: stack.append(node.left) if node.right: stack.append(node.right) ``` What sequence does `out` hold?
MCQ-19A DFS enumerates every simple path from node 0 to node 3 in this graph, using a shared `visited` set and a `path` list: ```python adj = {0: [1, 2], 1: [2, 3], 2: [3], 3: []} def dfs(u): path.append(u) visited.add(u) if u == 3: results.append(list(path)) else: for v in adj[u]: if v not in visited: dfs(v) path.pop() # visited.discard(u) is missing ``` Neighbours are iterated in the order listed. What does `results` contain?
MCQ-20A candidate writes a `shortest_path` function that uses a stack instead of a queue: ```python def shortest_path(start, goal, adj): stack, visited, parent = [start], {start}, {start: None} while stack: node = stack.pop() if node == goal: path = [] while node is not None: path.append(node) node = parent[node] return path[::-1] for nb in adj[node]: if nb not in visited: visited.add(nb) parent[nb] = node stack.append(nb) ``` Run on this graph, with `adj` listing each node's neighbours in the order shown: ``` S: A, B A: S, G B: S, C C: B, D D: C, G G: A, D ``` The call is `shortest_path('S', 'G', adj)`. What does it return, and what does that show about the stack?
MCQ-2You're computing the next greater element for `nums = [3, 1, 4, 1, 5]` with a monotonic stack. The code's documented invariant is: bottom to top, the stack holds the indices whose next greater element has not yet been found, and their values are strictly decreasing. The loop has just finished processing index 3 (value 1). What does the stack hold?
MCQ-24A next-greater-element pass uses a monotonic stack: ```python for x in arr: while stack and stack[-1] < x: stack.pop() stack.append(x) ``` With `arr = [3, 1, 4, 1, 5, 9, 2, 6]` and `stack` starting empty, how many times does `stack.pop()` execute in total?
MCQ-5A teammate's next-greater pass over `[2, 1, 2, 4, 3]` returns `[2, 2, 4, -1, -1]`; the correct output for that input is `[4, 2, 4, -1, -1]`. The pass pushes indices and pops while `a[stack[-1]] < a[i]`. Which single change to the pass produces exactly the teammate's output?
MCQ-6In the Largest Rectangle in Histogram algorithm the monotonic stack stores bar indices rather than bar heights. Which statement explains why?
MCQ-8Largest-rectangle-in-histogram is coded with a stack of indices whose bar heights increase: pop while the stack top's height is >= the current height, and measure each popped bar as height * (i - stack.top() - 1), or height * i when that pop emptied the stack. On heights = [1, 2, 3, 4, 5] the routine returns 0, although the correct result is 9. The candidate's fix is to append a single 0 to the end of heights and change nothing else. Which statement describes what that appended 0 does?
MCQ-9A pricing service rebuilds the next-greater-element table for all indices of an N = 2,000,000 quote array on each tick, on a single core, and during a sell-off the exchange delivers the quotes in strictly descending order. The nested-loop version meets the median tick budget but misses it on that descending input, and the budget has to hold there too. Which property of the monotonic-stack pass keeps the descending tick inside budget?
MCQ-10A recursive-descent parser recurses once per nesting level. On a deeply nested input it throws `RangeError: Maximum call stack size exceeded` at a consistent depth of about 11,000 frames. Raising `--max-old-space-size` from 2 GB to 8 GB leaves that depth unchanged; raising `--stack-size` from 984 KB to 4 MB moves the crash to about 45,000 frames. The recursion is fully synchronous, and the error is caught by a surrounding `try/catch`, after which the process keeps running. Which mechanism produces the error?
MCQ-13A Python service walks a 300,000-node tree with a recursive function. With the default `sys.setrecursionlimit` it raises `RecursionError` at about 1,000 frames; after the team sets `sys.setrecursionlimit(1_000_000)` the process dies with a hard crash instead. Which statement explains why raising the limit did not let the walk finish?
MCQ-12A JVM service accepts user-supplied trees and walks them recursively. On a 200,000-node input the walk dies with a StackOverflowError; on 1,000-node inputs it passes. The team debates converting to an explicit stack versus raising -Xss. Which claim about the call stack decides the argument?
MCQ-14A candidate rewrites a recursive list-sum `def total(xs): return 0 if not xs else xs[0] + total(xs[1:])` as `def total(xs, acc=0): return acc if not xs else total(xs[1:], acc + xs[0])` and claims the rewrite removes the stack growth on any runtime, because the recursive call is now the last thing the function does. Which statement decides whether the rewrite actually bounds stack depth?
MCQ-22A comment-thread endpoint accepts JSON bodies up to the 1 MB cap the load balancer enforces. The parser is hand-written and recurses once per nesting level: profiling shows 256 bytes of stack per level, and each worker thread runs with a 2 MB stack. An attacker posts a body of 400,000 '[' followed by 400,000 ']', about 800 KB and comfortably inside the cap. What happens on that single request?
MCQ-23A C++ JSON API decodes untrusted input with a recursive-descent parser. Each recursion level costs about 512 bytes of stack, and the handler chain above the parser has already used roughly 256 KiB when decoding starts. The service runs 2,000 worker threads, each created with a 1 MiB stack, on a box with 8 GiB of RAM. A customer contract requires accepting documents nested up to 5,000 levels, but a deeply nested payload makes a worker take SIGSEGV and the whole process dies. Which change fixes this?
MCQ-21A motor controller pushes pending setpoints onto a stack inside an interrupt handler that must return within 2 µs on every invocation. The stack depth is unbounded and grows with incoming traffic. Benchmarks on the target: an array-backed stack with doubling growth pushes in 8 ns on average but copies all 65536 live pointers in ~30 µs when it resizes; a linked stack pushes in 40 ns on average and 60 ns worst case when its nodes come from a preallocated pool. Which implementation meets the per-push deadline?