Coding

Stacks & Queues Coding Questions

Stacks and queues model LIFO and FIFO access and are essential for parsing, DFS/BFS, and monotonic sequence problems. These patterns appear constantly across all top company interviews.

Practice with AI Feedback — Free AI Mock Interview

Sample Questions & Strong Answers

Valid Parentheses — check if string of brackets is balanced.

Stack: push open brackets. On closing bracket: if stack is empty or top doesn't match, return false. Pop on match. At end, return stack.isEmpty(). Time O(n), Space O(n).

💡

Pro tip: Use a map for bracket pairs to keep matching logic clean. This is the canonical stack question — know it perfectly. Amazon, Meta, Google, Microsoft, Apple.

Min Stack — stack that supports push, pop, top, and getMin in O(1).

Use two stacks: main stack and min stack. On push: push to main; push to min stack only if new value <= current min. On pop: if popped value equals min stack top, pop min stack too. getMin returns min stack top. Time O(1) all operations.

💡

Pro tip: Alternatively, store (value, currentMin) pairs in a single stack. Both approaches are O(1) and acceptable. Amazon, Google, Microsoft.

Daily Temperatures — days until a warmer temperature.

Monotonic stack: iterate forward, storing indices of unresolved days. When current temp > stack top's temp: pop and set result[poppedIndex] = currentIndex − poppedIndex. Stack holds indices in decreasing temperature order. Time O(n), Space O(n).

💡

Pro tip: The monotonic stack pattern (next greater element) appears in many disguised forms. The stack always holds indices, not values. Amazon, Google, Meta.

Largest Rectangle in Histogram.

Monotonic stack (increasing): push indices while bars are increasing. When a shorter bar is found: pop and compute area = height[popped] × (current − stack.top() − 1). Handle remaining stack after loop. Time O(n), Space O(n).

💡

Pro tip: Append a 0 sentinel at the end to flush the remaining stack. Width calculation uses the new stack top as left boundary. Amazon, Google — hard.

Sliding Window Maximum — maximum of each window of size k.

Monotonic deque (decreasing): maintain indices of useful elements (greater than recent). Remove from front if outside window, remove from back while back ≤ current (they'll never be max). Deque front is always current window's max. Time O(n), Space O(k).

💡

Pro tip: The deque holds indices (not values) so window expiration can be checked. Each element is added/removed at most once → O(n) total. Amazon, Google — hard.

Evaluate Reverse Polish Notation (RPN).

Stack: push numbers. On operator: pop two operands, apply operator, push result. Return stack top. Edge case: integer division truncates toward zero (Math.trunc in JS, int() in Python). Time O(n), Space O(n).

💡

Pro tip: Handle division truncation toward zero carefully — languages differ: Python // floors, Java/JS truncates. Amazon.

Implement Queue Using Two Stacks.

Two stacks: inbox and outbox. Enqueue: push to inbox. Dequeue: if outbox empty, transfer all inbox to outbox (reversing order). Pop from outbox. Each element is moved at most once → amortized O(1) per operation.

💡

Pro tip: Amortized O(1) is the key insight — worst case is O(n) but averaged over all operations it's O(1). Amazon, Meta.

Next Greater Element I — find next greater number for each element of nums1 in nums2.

Monotonic stack on nums2: compute next greater for each element, store in a map. Then look up each nums1 element in the map. Time O(n+m), Space O(n).

💡

Pro tip: Precompute next-greater for all of nums2 first, then O(1) lookup for nums1. This decouples the two arrays cleanly. Amazon, Google, Meta.

Decode String — expand encoded string like '3[a2[bc]]' = 'abcbcabcbcabcbc'.

Stack of (currentString, repeatCount) pairs. On '[': push current state, reset. On ']': pop, repeat current string repeatCount times, append to popped string. On digit: build repeatCount. On letter: append to currentString. Time O(n × maxK), Space O(n).

💡

Pro tip: Handling nested brackets is the hard part — the stack naturally handles depth. Google, Amazon, Meta — medium.

Basic Calculator — evaluate arithmetic expression with +, −, parentheses.

Stack of (sign, running sum) pairs. Track current number and sign (+1/−1). On '(': push (sign, result), reset. On ')': pop and combine. On digit: build number. On +/−: add current number to result with sign. Time O(n), Space O(n).

💡

Pro tip: Hard variant includes *, / — requires separate precedence handling. For +/− only: a sign stack is sufficient. Google, Amazon — hard.

Expert tips

Monotonic stack (increasing or decreasing) solves next-greater, previous-smaller, and histogram-area problems.

When you need O(1) access to both ends of a sequence, use a deque — it underlies sliding window maximum.

Two-stack queue achieves amortized O(1) dequeue — know why this works (amortized analysis).

Stack size in parentheses/bracket problems equals current nesting depth — useful for reasoning about space.

Stacks & Queues Coding Questions FAQ

A monotonic stack maintains elements in a strictly increasing or decreasing order. Use it for: next greater/smaller element, previous greater/smaller element, largest rectangle in histogram, trapping rain water, and sliding window maximum (with deque). The pattern: pop elements that violate the monotonic property when inserting a new element.

Recursion uses the call stack implicitly; an explicit stack simulates it iteratively. Use explicit stack when: recursion depth might cause stack overflow (deep trees/graphs), you need to process results as you backtrack (rather than on return), or you want O(1) space overhead per frame. Recursion is cleaner for algorithms with natural recursive structure (tree traversal, backtracking).

Sliding window maximum/minimum, palindrome checking, BFS with priority (0-1 BFS), and implementing LRU cache (as doubly linked list). Deque allows O(1) push/pop at both ends. In Python: collections.deque. In Java: ArrayDeque. In JavaScript: simulate with array (pop/shift both O(n) — not ideal for large n).

Accumulate digits: currentNum = currentNum × 10 + (char − '0'). Process the accumulated number when you hit a non-digit (operator, bracket, end of string). This handles multi-digit numbers naturally without parsing.

Practice Stacks & Queues Coding Questions with real-time AI.

Stop reading sample answers and start practicing. Get personalized feedback on structure, delivery, and depth — every time.

Start Free Practice AI Mock Interview

Free plan available · No credit card needed · Cancel anytime