Skip to content
Data Structures & Algorithms

Stacks interview questions and answers

46 questions, 38 with code. About 3 h 13 min to read them all.

By TestLab · Updated

Plan for an interview
46 questions

Track what you know and what to revise.

Sign in to track progress

You can open a few full answers without signing in. Sign in to read all

1

What is a Stack data structure?

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle: the element inserted most recently is the first one removed. Stacks support adding and removing elements at one end, commonly called the top.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Operations

A stack typically provides these operations:

  • Push: Insert an element at the top.

  • Pop: Remove and return the top element.

  • Peek: Return the top element without removing it.

  • is_empty: Check whether the stack contains no elements.

  • Size: Return the number of stored elements.

If A, B, and C are pushed in that order, the next element popped is C, followed by B and then A.

An empty stack has no top, so popping or peeking it is invalid. A one-element stack becomes empty after that element is popped. Duplicate and negative values are valid and are stored as separate entries; no ordering requirement is imposed on their values.

Python List Behavior

A Python list can act as a stack by treating its end as the top:

  • append(value) pushes a value.

  • pop() removes and returns the top value.

  • stack[-1] peeks at the top, but only after checking that the list is not empty.

  • len(stack) returns the stack size.

Because pop() and stack[-1] act on the end of the list, they preserve LIFO ordering. Operations such as pop(0) and insert(0, value) should not be used as stack operations because they shift the remaining elements and take O(n) time.

Complexity

For a stack backed by a Python list:

Operation Best Average Worst Reason
Push / append O(1) O(1) O(n) A resize during an append may copy all elements.
Pop O(1) O(1) O(n) A resize during a pop may copy or move elements.
Peek / stack[-1] O(1) O(1) O(1) Accessing the last element does not shift other elements.
is_empty O(1) O(1) O(1) The list length is directly available.
Size / len O(1) O(1) O(1) The list length is directly available.

A sequence of pushes and pops has amortized O(1) time per operation, although an individual operation can take O(n) when the list resizes.

For n stored elements, the stack uses O(n) total space for its own storage and O(1) auxiliary space beyond that storage. These figures count the stack but not any separate input collection; an input that is copied into the stack must be counted separately. In a recursive algorithm, add O(d) space for the recursion stack, where d is the maximum recursion depth.

A linked-list implementation can provide O(1) worst-case push and pop by inserting and removing at the head, while still requiring O(n) total space for its nodes.

Common Uses

Stacks are useful whenever the most recent unfinished item must be handled first:

  • Function calls: The call stack stores active frames, including return information.

  • Undo operations: Each action can be pushed and later popped to reverse it.

  • Expression evaluation: Infix expressions can be converted to postfix using an operator stack; postfix or RPN expressions are evaluated with a value stack.

  • Balanced parentheses: Push opening delimiters and pop them when matching closing delimiters appear.

  • DFS iteration: An explicit stack stores nodes that still need to be visited.

  • Backtracking: The stack records choices so they can be reversed when a path fails.

Common Pitfalls

  • Popping or peeking an empty stack: Check whether the stack is non-empty before these operations.

  • Incorrect ordering: pop() returns the newest element, not the oldest.

  • Using the wrong end: Treat the end of the list as the top; avoid pop(0) and insert(0, value).

  • Ignoring amortized behavior: Individual list resizes can cost O(n), although sequences of operations have amortized O(1) cost per operation.

  • Confusing storage with a queue: A stack is LIFO, while a queue is First In, First Out.

Interview Tips

Interviewers often follow up by asking you to implement valid-parentheses validation, a minimum stack, a function-call simulation, DFS with an explicit stack, or expression evaluation. Be ready to explain why a stack preserves ordering, handle empty-input cases, and state the time and space complexity in Big-O notation.

2

Why Is a Stack a Recursive Data Structure?

A stack is considered a recursive data structure because it can be modeled as either an empty stack or a top element followed by another stack. This is a recursive structural relationship, not a requirement that stack operations or implementations use recursion.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Recursive Definition

A stack S can be described recursively:

  • Base case: S is empty.

  • Recursive case: S contains a top element and a remaining stack S'.

Conceptually:

  • S = empty

  • S = (top, S')

  • S = (top, (top, (top, empty)))

A linked stack reflects this definition directly: each node stores a value and a reference to another node of the same type. The final node points to None, representing the empty stack.

This does not mean that the stack abstract data type must use recursion. It can also be implemented with an array, a Python list, or another container.

Stack Operations and Complexity

For a Python list-backed stack, use append() to push, pop() to remove the top, and stack[-1] to peek after checking that the stack is not empty.

Operation Best time Average time Worst time Additional working space
Push using append() O(1) O(1) amortized O(n) O(1) amortized; O(n) transiently during resizing
Pop using pop() O(1) O(1) amortized O(n) O(1) amortized; O(n) transiently during resizing
Peek using stack[-1] O(1) O(1) O(1) O(1)
  • The amortized cost is O(1) because occasional list resizing is distributed across many operations. A single resizing operation can take O(n) time.

  • A stack containing n elements requires O(n) storage for its elements.

  • If the stack is auxiliary to an input containing m elements, auxiliary space excluding the input is O(n), while total space including the input is O(m + n).

  • A linked stack supports push, pop, and peek in O(1) best, average, and worst-case time. Its nodes require O(n) total storage, with O(1) additional working space per operation.

Connection to Recursive Algorithms

Every recursive function uses an implicit call stack:

  1. A function call pushes an activation record containing information such as parameters, local variables, and the return location.

  2. A recursive call pushes another activation record.

  3. Returning from a call pops that record and restores the previous frame.

Explicit stack operations mirror these three actions. Consequently, recursion can often be rewritten iteratively with an explicit stack, avoiding Python’s recursion-depth limit of approximately 1,000 nested calls.

A traversal whose recursion depth is h uses O(h) recursion-stack space. For an input containing n elements, total memory including the input is O(n + h).

Example Walkthrough

For the RPN expression 3 4 + 2 *:

Token Stack after processing Explanation
3 [3] Push 3
4 [3, 4] Push 4
+ [7] Pop 4 and 3, then push 3 + 4
2 [7, 2] Push 2
* [14] Pop 2 and 7, then push 7 * 2

The result is 14. The right operand is popped first, followed by the left operand, which matters for subtraction and division.

Common Pitfalls

  • Empty stack: Check whether the stack is empty before popping or peeking.

  • Operand order: Pop the right operand before the left operand.

  • Recursion depth: Convert deep recursion to an explicit stack or raise Python’s recursion limit carefully.

  • Mutating input: Keep the stack separate when the original input must remain unchanged.

  • Edge cases: Empty input, malformed expressions, a single element, duplicate values, and negative values should be considered explicitly in an implementation.

  • Concept confusion: A recursive definition describes the structure, but push, pop, and traversal can all be implemented iteratively.

3

What are the Stack operations and their time complexities?

A stack is a LIFO (last-in, first-out) data structure: the most recently added element is the first one removed. Push, pop, and peek can each be O(1) in the worst case with a suitable implementation, while a Python-list-backed stack has amortized O(1) insertion and removal with rare O(n) resizing cases.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Operations

Operation Purpose Best Case Average / Amortized Worst Case Auxiliary Space
push(item) Add an element to the top O(1) O(1) amortized O(n) for a resizing dynamic array; O(1) for a linked-node or fixed-capacity stack Usually O(1); a dynamic-array resize may temporarily use O(n)
pop() Remove and return the top element O(1) O(1) amortized O(n) if a dynamic array must reallocate; otherwise O(1) Usually O(1); reallocation may temporarily use O(n)
peek() or top() Return the top element without removing it O(1) O(1) O(1) O(1)
is_empty() Check whether the stack contains any elements O(1) O(1) O(1) O(1)
size() Return the number of stored elements O(1) O(1) O(1) O(1)

An amortized O(1) operation has O(1) cost on average across a sequence of operations, even though an individual operation may occasionally be more expensive. For Python lists, append() and pop() modify the end of the list and therefore provide amortized O(1) stack operations.

Implementation Differences

  • Linked-node stack: Push and pop allocate or release one node, so they are O(1) in the worst case.

  • Fixed-capacity array stack: Push and pop are O(1) when capacity is available; pushing to a full stack causes overflow.

  • Python list stack: append() and pop() are amortized O(1). Occasional resizing can copy the backing storage and cost O(n).

  • Peeking: After checking that the stack is nonempty, Python lists support stack[-1] in O(1).

Space Complexity

  • Stored stack space: O(n), where n is the number of elements currently stored.

  • Input treatment: A caller-provided input collection is external and excluded; elements inserted into the stack are counted as stored state.

  • Auxiliary space: Normally O(1) per operation. A dynamic-array resize may temporarily allocate an additional O(n) buffer.

  • Recursion stack: If recursion implements stack-like processing with r active calls, the recursion stack requires O® additional space. Basic stack operations do not use recursion.

Example Walkthrough

Starting with an empty stack:

  1. Push 10 → [10]

  2. Push -5 → [10, -5]

  3. Push 10 → [10, -5, 10]

  4. Peek returns 10 without changing the stack.

  5. Pop returns and removes 10 → [10, -5]

Empty-stack pop() and peek() operations should be rejected as underflow errors. One element, duplicate values, and negative values require no special handling. Input sortedness, disconnected graphs, and cycles do not affect the basic stack operations.

Common Uses

  • Function calls: The call stack stores active function frames, parameters, and return information.

  • Undo functionality: Each action can be pushed with the information needed to reverse it.

  • Expression evaluation: Stacks support infix-to-postfix conversion and postfix or RPN evaluation.

  • Balanced parentheses: Opening delimiters are pushed, and closing delimiters must match the top.

  • Iterative DFS: Vertices or neighboring states are pushed and popped explicitly.

  • Backtracking: Partial solutions are pushed, explored, and removed when a branch fails.

Common Pitfalls

  • Check that the stack is nonempty before popping or accessing stack[-1]; otherwise Python raises IndexError.

  • Do not use list.pop(0) or list.insert(0, item) to emulate a stack. Both shift elements and take O(n).

  • Distinguish pop(), which removes the top element, from peek(), which only reads it.

  • Do not describe amortized O(1) as a worst-case guarantee.

  • Common follow-up questions include implementing a stack with two queues, building a minimum stack, validating parentheses, evaluating RPN expressions, and traversing a graph with an explicit stack.

4

When are Stack or Queue better choices than an Array or List?

Use a Stack when the most recently added item must be processed first (LIFO), and use a Queue when the earliest added item must be processed first (FIFO). An Array or List is preferable when elements need random access or frequent updates by index.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Choosing the Structure

Requirement Best structure Typical uses
Last in, first out Stack Function calls, undo history, expression evaluation, balanced parentheses, DFS, backtracking
First in, first out Queue BFS, task scheduling, buffering, request processing, producer-consumer systems
Access by index Array or List Random updates, searching, sorting, maintaining ordered elements
Access only from one end Stack Processing elements in reverse insertion order
Access from both ends Deque Sliding windows, work queues, implementing stacks or queues

Stack and queue are abstract behavior patterns rather than unrelated implementations. A stack or queue can be backed by an array, linked nodes, or a dynamic container. Choosing a stack or queue therefore often expresses the required access pattern more clearly than choosing a general-purpose array or list.

In Python, use a list with append() and pop() as a stack, and collections.deque with append() and popleft() as a queue.

Complexity and Space

Operation Best Average or amortized Worst Reason
Read an array/list element by index O(1) O(1) O(1) Indexing computes the address directly
Push onto a Python-list stack O(1) O(1) amortized O(n) Occasional resizing copies elements
Pop from a Python-list stack O(1) O(1) amortized O(n) Occasional shrinking copies elements
Enqueue with deque.append O(1) O(1) O(1) Uses linked blocks with spare capacity
Dequeue with deque.popleft O(1) O(1) O(1) Removes from the front without shifting
Remove from the front of a list O(n) O(n) O(n) Remaining elements must be shifted

The amortized guarantee means a sequence of k stack operations takes O(k) total time, although an individual operation can occasionally take O(n).

For n stored elements, a stack or queue uses O(n) total space, including the stored elements. This count includes the container and any recursion stack used by the algorithm; even if the original input is excluded, the container can still hold O(n) references. A Python-list resize can temporarily copy O(n) references, so the worst-case auxiliary space of an individual resize is O(n), although the amortized cost per operation is O(1).

In DFS, an explicit stack can require O(n) space in the worst case. Recursive DFS adds O(h) recursion-stack space, where h is the tree height and is at most O(n). A BFS queue can also require O(n) space.

Operational Behavior

For the input [1, -2, 3]:

Step Stack, newest on right Queue, oldest on left
Push or enqueue 1 [1] [1]
Push or enqueue -2 [1, -2] [1, -2]
Push or enqueue 3 [1, -2, 3] [1, -2, 3]
Remove repeatedly 3, -2, 1 1, -2, 3

DFS commonly uses a stack because it explores the newest branch first, while BFS uses a queue to explore nodes level by level. Empty input produces no removals, duplicates remain distinct elements, and negative values require no special handling.

Common Pitfalls

  • Using list.pop(0) for a queue: It shifts every remaining element and costs O(n). Use deque.popleft().

  • Popping an empty stack or queue: Check if stack: or if queue: before calling pop() or popleft().

  • Confusing storage with access pattern: A Python list can implement a stack, but that does not prevent it from also being used as a general list.

  • Ignoring recursion depth: An iterative DFS stack avoids Python’s recursion limit; count its O(n) worst-case space.

  • Forgetting amortized costs: Python-list append and pop are O(1) amortized rather than guaranteed O(1) for every individual operation.

5

How do infix, prefix, and postfix notations represent expressions?

Infix, prefix, and postfix are three ways of writing mathematical or logical expressions. Infix places operators between operands, prefix places them before operands, and postfix places them after operands; prefix and postfix encode grouping directly, so they do not require precedence rules or grouping parentheses.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

Notation Operator position Example of A + B Common name
Infix Between operands A + B Infix notation
Prefix Before operands + A B Polish notation
Postfix After operands A B + Reverse Polish notation, or RPN

For the expression (A + B) * (C - D):

  • Infix: (A + B) * (C - D)

  • Prefix: * + A B - C D

  • Postfix: A B + C D - *

The ordering of operands is preserved in all three forms. For example, A - B becomes - A B in prefix and A B - in postfix. The difference is where the operator appears relative to its operands.

Stack Use Cases

Stacks naturally support the applications associated with these notations:

  • Function calls: A call stack typically stores return information, local state, and activation records.

  • Undo operations: Each action is pushed, and undo pops the most recent action.

  • Expression evaluation: Postfix expressions use an operand stack. Prefix expressions can also be evaluated with an operand stack by scanning them in reverse.

  • Balanced parentheses: Opening parentheses are pushed and removed when their matching closing parentheses are encountered.

  • DFS iteration: Neighboring nodes are pushed onto a stack to perform depth-first traversal.

  • Backtracking: Choices are stored on a stack so the most recent unexplored choice is removed first.

Example and Trace

A common infix-to-postfix conversion uses the shunting-yard algorithm. An operator stack temporarily holds operators and opening parentheses, while an output list collects postfix tokens.

Read token Operator stack, bottom to top Postfix output
( (
A ( A
+ (, + A
B (, + A B
) empty A B +
* * A B +
( *, ( A B +
C *, ( A B + C
- *, (, - A B + C
D *, (, - A B + C D
) * A B + C D -
End empty A B + C D - *

The algorithm uses operator precedence to decide when an operator should move to the output. It also uses associativity: operators with equal precedence are generally treated as left-associative unless parentheses indicate otherwise.

Conversions and Evaluation

  • Infix to postfix: Use the shunting-yard algorithm described above.

  • Postfix to prefix: Process postfix tokens from left to right using a stack. Push operands. For an operator, pop the right operand and then the left operand, then push the combined expression as operator left right.

  • Infix to prefix: First convert infix to postfix, then reconstruct the prefix expression from the postfix form.

  • Postfix evaluation: Scan left to right. Push operands. When an operator appears, pop the right operand and then the left operand, apply the operator, and push the result.

  • Prefix evaluation: Scan right to left. Push operands. When an operator appears, pop the left operand and then the right operand, apply the operator, and push the result.

The reversed pop order for prefix evaluation is essential for subtraction and division. For example, prefix - A B means A - B, not B - A.

Complexity

For a valid expression containing n tokens:

Operation Best case Average case Worst case Auxiliary space
Infix to postfix conversion O(n) O(n) O(n) O(n)
Infix to prefix conversion O(n) O(n) O(n) O(n)
Postfix evaluation O(n) O(n) O(n) O(n)
Prefix evaluation O(n) O(n) O(n) O(n)

Each operator enters and leaves the conversion stack at most once, while each operand value enters and leaves the evaluation stack at most once. The O(n) space bound includes the operator or operand stack and any intermediate output or reconstructed expression. The input expression itself is not counted. These algorithms are iterative, so the recursion stack is O(1).

Common Pitfalls

  • Operand order: Postfix evaluation pops the right operand first; prefix evaluation scanned right to left pops the left operand first.

  • Precedence and associativity: Infix expressions require both rules unless grouping is made explicit.

  • Parentheses: Every opening parenthesis must have a matching closing parenthesis, and vice versa.

  • Empty input: An expression with no tokens is invalid; check before conversion or evaluation.

  • Single operands: A one-token expression is valid and remains unchanged.

  • Duplicates and negative values: Repeated operands and negative values are preserved as ordinary operand values; their presence does not change the conversion procedure.

  • Stack safety: Check that a stack is non-empty before popping or peeking with stack[-1].

6

How do stacks manage function calls in programming languages?

A call stack is a LIFO structure used to track active function calls. When a function calls another function, a new stack frame is added; when that function returns, its frame is removed and execution resumes in the caller.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How the Call Stack Works

Each active function invocation has a stack frame containing the information needed to continue and eventually return from that call.

  1. The caller evaluates the arguments and invokes the callee.

  2. A new frame is conceptually pushed onto the call stack.

  3. The callee becomes the currently executing function.

  4. The callee returns a result or raises an exception.

  5. Its frame is popped, restoring the caller as the active function.

The last-in, first-out behavior naturally handles nested calls. For example:

Event Active call stack, top on right
Call outer() [outer]
outer() calls middle() [outer, middle]
middle() calls inner() [outer, middle, inner]
inner() returns [outer, middle]
middle() returns [outer]
outer() returns []

The logical call stack is distinct from the heap. Physical storage is runtime-specific: a runtime may use a machine stack, heap-allocated frame records, or both. In CPython 3.12, Python frame objects are heap allocated, while nested Python calls also consume the interpreter’s native C stack. Objects referenced by frames may also be heap allocated.

Stack Frame Contents

The exact contents depend on the language and runtime, but a frame commonly contains:

  • Return address: where execution continues after the function finishes.

  • Arguments or references to arguments: according to the language’s calling convention.

  • Local variables: values and references needed by the active invocation.

  • Saved execution state: such as registers, frame pointers, or stack pointers.

  • Temporary values: intermediate results used during expression evaluation.

  • Exception-handling information: used when unwinding the stack during an error.

Separate invocations of the same function receive separate frames. Therefore, recursive calls do not overwrite each other’s local variables.

Recursion and Error Unwinding

Every recursive call adds another frame until the base case is reached. Returning then removes frames in reverse order, allowing each caller to continue its own computation.

An exception similarly causes the runtime to unwind the stack:

  • The current frame is examined for an applicable exception handler.

  • If none exists, the frame is discarded and the search continues in the caller.

  • A matching handler resumes execution in the frame where it was found.

Some languages optimize suitable tail calls so that a frame can be reused instead of growing the stack. Python 3.12 does not generally perform this optimization.

Complexity

Let D be the maximum call depth and S the approximate size of one frame.

Operation Best Average Worst Reason
Push a fixed-size frame O(1) O(1) O(1) Only the top frame changes.
Pop a fixed-size frame O(1) O(1) O(1) Only the top frame is removed.
Manage D calls O(D) O(D) O(D) Assumes each function body performs O(1) other work.
  • Time: The total is O(D) for stack management alone. Include the actual work performed by each call if it is nonconstant.

  • Auxiliary space: O(D) frames, or approximately O(D × S) bytes. This includes the recursion stack but excludes the original input.

  • Python list stacks: append() and pop() are O(1) amortized. An individual operation can take O(n) during an occasional list reallocation, so the best case is O(1), average case is O(1) amortized, and worst case is O(n).

Code Example

The following iterative simulation uses a Python list as a LIFO stack. It avoids Python’s recursion limit while showing the order of nested calls and returns.

def trace_call_stack(depth: int) -> list[str]:
    """Trace nested calls and returns using an explicit LIFO stack."""
    if depth < 0:
        raise ValueError("depth must be non-negative")

    work_stack: list[int] = [depth]
    trace: list[str] = []

    while work_stack:
        item = work_stack.pop()

        if item > 0:
            trace.append(f"call {item}")

            # The return happens after the nested call completes.
            work_stack.append(-item)
            work_stack.append(item - 1)
        elif item < 0:
            trace.append(f"return {-item}")

    return trace


example = trace_call_stack(3)
# Expected: ["call 3", "call 2", "call 1",
#             "return 1", "return 2", "return 3"]

Common Pitfalls and Interview Tips

  • Stack overflow: Deep recursion can exhaust the runtime’s stack. Python’s default recursion limit is approximately 1,000.

  • Empty case: A depth of 0 produces an empty trace, representing no nested call.

  • Single call: A depth of 1 produces one call followed by one return.

  • Invalid depth: Negative values are rejected because they do not represent nested calls.

  • Complexity mistakes: Include the recursion stack in auxiliary space, but state explicitly whether the original input is counted.

  • Common follow-up: Explain why recursion uses O(D) space, identify what a stack frame contains, or discuss how tail-call optimization can reduce stack growth.

7

Where are stacks naturally suited over other data structures?

Stacks are naturally suited to problems involving nesting, reversal, or completing the most recent unfinished operation first. Their defining behavior is last-in, first-out (LIFO): the newest item is removed before older items.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Why LIFO Fits

A stack exposes a small, focused set of operations:

  • Push: add an item to the top.

  • Pop: remove the most recently added item.

  • Peek: inspect the top item without removing it.

This access pattern is preferable when only the latest item matters or when operations must unwind in reverse order. A queue is better when the oldest pending item should be processed first, while a general-purpose list provides random access but exposes more operations than the problem requires.

For example, balanced delimiters depend on nesting. With ([]{}), the stack changes as follows:

Character Stack afterward
( (
[ ([
] (
{ ({
} (
) empty

The empty final stack shows that every opening delimiter was closed in the correct order.

Natural Stack Uses

  • Function calls: the call stack tracks active function frames, including local state and return information.

  • Undo and redo: an undo stack stores reversible actions, while a separate redo stack stores actions that can be reapplied.

  • Expression evaluation: infix-to-postfix conversion and postfix or RPN evaluation use stacks for operators and operands.

  • Balanced delimiters: parentheses, brackets, and braces must be matched in reverse order of opening.

  • Depth-first search: an explicit stack replaces recursive traversal and naturally follows the most recently discovered branch.

  • Backtracking: search paths are pushed and popped as alternatives are explored.

  • Monotonic stacks: these solve problems such as the next greater element. Each element is pushed once and popped at most once, giving O(n) total time.

Complexity

For a stack containing m items:

  • Abstract-stack push, pop, and peek: O(1) time under the standard stack contract.

  • Python list push and pop: O(1) amortized time using append() and pop(). An occasional list resize can make one individual operation O(n), although a sequence of m operations still totals O(m) amortized time.

  • Peek with stack[-1]: O(1) time after checking that the stack is nonempty.

  • Storage space: O(m) for m stored items; the input itself is not counted.

For delimiter validation of a string of length n:

  • Best case: O(1) time when the input is empty or fails immediately.

  • Average case: O(n) time because characters are generally processed once.

  • Worst case: O(n) time.

  • Auxiliary space: O(d), where d is the maximum nesting depth; this is O(n) in the worst case. The input string itself is not counted.

A next-greater-element monotonic-stack algorithm takes O(n) best, average, and worst-case time because every element is pushed and popped at most once, with O(n) auxiliary space.

Common Pitfalls

  • Define what happens when pop() or peek() is called on an empty stack; many implementations raise an error.

  • Match delimiter types as well as counts. The input ([)] is invalid even though its opening and closing counts are balanced.

  • After scanning a delimiter string, ensure no opening delimiters remain.

  • Empty input, single-element stacks, duplicate values, and negative values are valid cases to consider. Sorted order and graph connectivity or cycles affect only algorithms layered on top of the stack, not the stack operations themselves.

8

What is the difference between array-based and linked list stacks?

Array-based and linked list stacks differ in memory layout, operation costs, and overhead. Array-based stacks use contiguous storage and usually have better locality, while linked-list stacks use per-element nodes and avoid requiring one contiguous allocation.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Array-based stack: Uses a contiguous backing array, such as a Python list, with the top at the end. append() pushes an element, pop() removes the top, and stack[-1] peeks after checking that the stack is non-empty.

  • Linked-list stack: Uses nodes connected by next references, with the top at the head. A push creates and links a new node; a pop removes the current head and advances the head to its successor.

Key Differences

Factor Array-based stack Linked-list stack
Memory layout Contiguous backing storage Nodes are usually stored separately
Per-element overhead Low, but the array can retain unused capacity Each node stores an element and a next reference
Push O(1) amortized; an individual resize can take O(n) O(1) worst case
Pop O(1) amortized; an individual shrink or resize can take O(n) O(1) worst case
Peek O(1) worst case O(1) worst case
Cache locality Generally stronger Generally weaker because nodes may be scattered
Growth May copy elements into a larger backing array Adds one node without copying existing elements

Time and Space Complexity

  • Array-based push and pop: Best case O(1), amortized O(1) over a sequence of operations, and worst case O(n) for an operation that resizes the backing array. Peek is O(1) in all cases.

  • Linked-list push, pop, and peek: O(1) in the best, average, and worst cases under the standard constant-time pointer and allocation model.

  • Space: Both use O(n) total space for n logical stack elements, with the elements themselves counted. Array capacity beyond the logical elements can also require O(n) space, and some resizing strategies temporarily need O(n) additional space. A linked-list stack uses O(n) space for node references in addition to its elements. Neither iterative implementation uses recursion, so the recursion-stack space is O(1).

When To Use Which

  • Use an array-based stack when locality and low per-element overhead matter, and a contiguous backing allocation is acceptable.

  • Use a linked-list stack when the stack may grow unpredictably and avoiding a contiguous allocation or bulk array resize is more important.

  • Neither implementation is literally unbounded: both are constrained by available memory and allocator behavior.

Edge Cases To Consider

  • Empty stack: Check len(stack) == 0 before peeking or popping; pop() on an empty Python list raises IndexError.

  • One element: Pushing, peeking, and popping must correctly restore the empty state.

  • Duplicates: Each occurrence occupies a separate stack position.

  • Negative numbers: Valid values with no structural effect.

  • Already sorted input: The ordering of the original input is irrelevant; stack operations follow last-in, first-out order.

  • Disconnected graphs or cycles: Not applicable to standalone stacks.

Common Pitfalls

  • Forgetting the empty check: Guard both peek and pop operations.

  • Misusing Python lists: list.pop(0) and list.insert(0, value) are O(n); use append(), pop(), and stack[-1].

  • Ignoring memory overhead: Linked-list nodes consume additional space, while arrays may retain unused capacity.

  • Overstating complexity guarantees: Array-based operations are amortized O(1), not necessarily O(1) for every individual operation.

  • Interview follow-up: “Which would you choose for a call-stack simulation, and why?” Discuss locality, per-element overhead, growth behavior, and whether contiguous allocation is acceptable.

9

How do you implement a dynamically resizing stack in Python?

A dynamic stack is a LIFO collection that automatically expands when elements are added and can contract when space is no longer needed. In Python, a list-backed implementation gets this behavior from append() and pop(), while providing explicit stack operations such as push(), pop(), and peek().

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Design and Operations

  • push(value): Adds an element to the top of the stack.

  • pop(): Removes and returns the top element.

  • peek(): Returns the top element without removing it.

  • is_empty(): Checks whether the stack contains no elements.

  • LIFO ordering: The most recently pushed element is the first one removed.

Stacks are commonly used for:

  • Function-call and expression-evaluation stacks

  • Undo and redo functionality

  • Balanced-parentheses validation

  • Iterative depth-first search

  • Backtracking algorithms

  • Converting infix expressions to postfix or evaluating RPN expressions

How Automatic Resizing Works

Python’s list maintains an internal allocation that is larger than its current length. When append() exhausts that allocation, the list automatically obtains more space and may copy its existing elements to the new allocation.

This happens inside the list implementation, so the stack does not need to expose or manage a fixed capacity. If this class were implemented using a fixed-size array in another language, a common policy would be:

  1. Start with a small capacity.

  2. Double the capacity when the array becomes full.

  3. Copy the existing elements into the new array.

  4. Optionally halve the capacity when the stack becomes less than one-quarter full.

Doubling is useful because the occasional expensive resizing is spread across many operations, making each push amortized O(1).

Complexity

Operation Best Average Worst Reason
push() O(1) O(1) amortized O(n) A single push may trigger list reallocation and copying.
pop() O(1) O(1) amortized O(n) Removing the final element is constant-time, but occasional list shrinking may copy elements.
peek() O(1) O(1) O(1) stack[-1] directly accesses the final element.
is_empty() O(1) O(1) O(1) It checks the list’s length.
__len__() O(1) O(1) O(1) Python stores the list’s size directly.

The stack uses O(n) total space for n stored elements, excluding the external input and with no recursion stack involved. A resizing operation can temporarily require O(n) additional allocator space.

Code Example

from typing import Generic, TypeVar

T = TypeVar("T")


class DynamicStack(Generic[T]):
    """A LIFO stack backed by Python's dynamically sized list."""

    def __init__(self) -> None:
        self._items: list[T] = []

    def push(self, value: T) -> None:
        """Add a value to the top of the stack."""
        self._items.append(value)

    def pop(self) -> T:
        """Remove and return the top value."""
        if not self._items:
            raise IndexError("pop from empty stack")
        return self._items.pop()

    def peek(self) -> T:
        """Return the top value without removing it."""
        if not self._items:
            raise IndexError("peek from empty stack")
        return self._items[-1]

    def is_empty(self) -> bool:
        """Return whether the stack contains no elements."""
        return not self._items

    def __len__(self) -> int:
        return len(self._items)


def main() -> None:
    stack = DynamicStack[int]()
    stack.push(10)
    stack.push(-3)
    stack.push(10)

    print(stack.peek())  # 10
    print(stack.pop())   # 10
    print(len(stack))    # 2


if __name__ == "__main__":
    main()

Common Pitfalls

  • Peeking at an empty stack: Check is_empty() before accessing stack[-1].

  • Confusing FIFO and LIFO: A stack removes the most recently inserted element.

  • Using pop(0): Removing from the beginning of a list is O(n); use pop() or pop(-1) instead.

  • Ignoring amortized costs: An individual push may be O(n) during reallocation, although a sequence of pushes is O(n) in total.

  • Assuming values are copied deeply: The stack stores object references, so mutable objects can still be changed after being pushed.

  • Edge cases: Empty stacks raise IndexError; one-element stacks work normally; duplicates and negative values are valid.

Common interview follow-ups include implementing a stack with a fixed array, adding an O(1) getMin() operation, and making the stack thread-safe.

10

What performance implications does a fixed-size array stack have?

A fixed-size array stack provides predictable, worst-case O(1) push, pop, and peek operations without the resizing cost of a dynamic stack. Its main trade-off is that capacity must be chosen in advance: memory is reserved even when unused, and a push beyond that capacity requires overflow handling.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Performance Characteristics

Operation Best Average Worst Reason
Initialize and pre-fill O© O© O© Initializes c slots; statically allocated storage can have O(1) allocation bookkeeping
push O(1) O(1) O(1) Writes one slot and updates the top index
pop O(1) O(1) O(1) Reads one slot and updates the top index; clearing the slot is optional
peek O(1) O(1) O(1) Reads the slot at the top index
Check full/empty O(1) O(1) O(1) Compares the size with zero or capacity

Here, c is the fixed capacity. These operations are not merely amortized O(1): the backing storage never grows or resizes, so each individual operation is worst-case O(1).

Memory and Scaling Trade-offs

  • Reserved memory: The stack’s backing storage uses O© space regardless of how many elements are currently stored.

  • Input accounting: This space complexity excludes the input and the memory occupied by referenced objects.

  • Recursion stack: The stack implementation is iterative and adds no recursion-stack overhead.

  • Predictable performance: A fixed array avoids the occasional O(n) copying performed by a growing dynamic array.

  • Capacity planning: Underestimating capacity causes overflow; greatly overestimating it wastes memory.

  • Locality: A contiguous array generally provides good cache locality, especially when it stores primitive values.

Approach Push/Pop Time Space Main Risk
Fixed-size array O(1) worst case O(capacity) Overflow
Dynamic array O(1) amortized O(n) for n live elements, plus any spare capacity Occasional O(n) resize
Linked-list stack O(1) O(n) Extra node allocation and weaker locality

Example Walkthrough

For a stack with capacity 3:

Operation Stored Elements Top Size
Initially [] -1 0
push(10) [10] 0 1
push(20) [10, 20] 1 2
peek() [10, 20] 1 2
pop() [10] 0 1
push(30) [10, 30] 1 2

Each operation takes O(1) time because only the top index and a bounded number of array slots are accessed.

Common Pitfalls

  • Underflow: Check for an empty stack before calling pop or peek.

  • Overflow: Decide whether a full stack should reject the push, raise an exception, or follow another explicit policy.

  • Off-by-one errors: Keep size equal to the number of stored elements, so the top index is size - 1.

  • Unused capacity: A capacity of n reserves n slots even if only a few are used.

  • Reference retention: In a language with reference types, clearing a popped slot can release an unwanted reference; leaving it uncleared does not change the fixed array’s slot count.

  • Common follow-up: Interviewers often ask how to add dynamic growth, such as doubling the array when full, while accepting an occasional O(n) resize.

11

How do you design a stack with O(1) minimum retrieval?

A min stack maintains the minimum value alongside every stack operation, allowing the current minimum to be retrieved in constant time. The standard implementation uses a primary stack for values and an auxiliary stack for corresponding minimums.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • push(value) adds the value to the primary stack.

  • The auxiliary stack stores the minimum of all elements currently in the stack.

  • pop() removes the value and its associated minimum.

  • get_min() returns the top of the auxiliary stack.

The auxiliary stack can store a minimum for every element, including duplicates. For example, pushing 5, 3, 3 produces auxiliary values 5, 3, 3, so removing elements keeps the minimum tracking synchronized.

Code Example

class MinStack:
    """A stack that supports retrieving its minimum in O(1) time."""

    def __init__(self) -> None:
        self._values: list[int] = []
        self._minimums: list[int] = []

    def push(self, value: int) -> None:
        """Add a value to the stack."""
        self._values.append(value)

        if not self._minimums or value < self._minimums[-1]:
            self._minimums.append(value)
        else:
            self._minimums.append(self._minimums[-1])

    def pop(self) -> int:
        """Remove and return the top value."""
        if not self._values:
            raise IndexError("pop from an empty MinStack")

        self._minimums.pop()
        return self._values.pop()

    def peek(self) -> int:
        """Return the top value without removing it."""
        if not self._values:
            raise IndexError("peek from an empty MinStack")

        return self._values[-1]

    def get_min(self) -> int:
        """Return the minimum value in O(1) time."""
        if not self._minimums:
            raise IndexError("get_min from an empty MinStack")

        return self._minimums[-1]


stack = MinStack()
stack.push(5)
stack.push(3)
stack.push(3)
stack.push(-2)

print(stack.get_min())  # -2
print(stack.pop())      # -2
print(stack.get_min())  # 3

Example Walkthrough

Operation Primary stack Auxiliary minimum stack Minimum
push(5) [5] [5] 5
push(3) [5, 3] [5, 3] 3
push(3) [5, 3, 3] [5, 3, 3] 3
push(-2) [5, 3, 3, -2] [5, 3, 3, -2] -2
pop() [5, 3, 3] [5, 3, 3] 3

Complexity

Operation Best case Average case Worst case
push O(1) O(1) amortized O(n) during occasional list resizing
pop O(1) O(1) amortized O(n) during occasional list resizing
peek O(1) O(1) O(1)
get_min O(1) O(1) O(1)
  • Time reason: get_min reads only the auxiliary stack’s top. Push and pop perform a constant number of list operations; Python list resizing makes those operations O(1) amortized.

  • Space complexity: O(n) total, counting the primary stack and auxiliary minimum stack. The auxiliary stack can contain up to n values. No recursion stack is used, so the recursion-stack cost is O(1).

Common Pitfalls

  • Empty stack: pop, peek, and get_min should fail explicitly rather than returning an invalid value.

  • Duplicate values: Equal values still receive corresponding entries in the auxiliary stack, so synchronization remains correct.

  • Negative values: The comparison value < current_min handles negative numbers normally.

  • One element: The auxiliary stack contains the same minimum as the primary stack.

  • Input order: Sorted, reverse-sorted, or arbitrary input does not change the complexity.

  • Invariant: Every push and pop must update both stacks together; otherwise get_min may return a stale value.

  • Interview follow-up: A common variation asks for getMin() in O(1), followed by a question about how the solution changes if the stack must also support frequent updates to arbitrary elements.

12

How do you design a thread-safe stack?

A thread-safe stack uses a mutual-exclusion lock to protect every access to its underlying storage. Each operation acquires the same lock, ensuring that concurrent threads cannot corrupt the stack or observe inconsistent intermediate states.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Design Principles

  • Use one lock per stack instance to protect the stack’s elements and related state.

  • Hold the lock for the entire logical operation, especially compound operations such as checking whether the stack is empty and then removing an element.

  • Release the lock automatically with a context manager, including when an exception occurs.

  • Avoid calling user-provided code while holding the lock because it could block other threads or cause deadlocks.

A Python list works as the underlying LIFO structure: append() adds to the top, pop() removes from the top, and stack[-1] reads the top after checking that the stack is not empty.

How It Works

Every public operation follows this pattern:

  1. Acquire the stack’s lock.

  2. Validate and access the underlying list.

  3. Perform the operation while still holding the lock.

  4. Release the lock.

The lock makes each individual operation atomic from the perspective of other threads. Two threads may separately observe a nonempty stack, but only one can remove the top element; the other receives IndexError.

A small sequential trace illustrates the stack behavior:

  1. Start with [].

  2. push(1) produces [1].

  3. push(2) produces [1, 2].

  4. peek() returns 2.

  5. pop() returns 2, leaving [1].

Relevant edge cases include an empty stack, for which pop() and peek() raise IndexError; a single-element stack, which supports all operations normally; and duplicate or negative values, which are stored and returned without special treatment.

Complexity

The following complexities exclude time spent waiting to acquire the lock.

Operation Best Average Worst Reason
push() O(1) O(1) amortized O(n) append() is usually constant-time but may resize the list
pop() O(1) O(1) amortized O(n) Removing the last element is usually constant-time but may shrink the list
peek() O(1) O(1) O(1) Reads the last list element directly
is_empty() O(1) O(1) O(1) Checks the list length
len() O(1) O(1) O(1) A list stores its length
  • Total space complexity: O(n) for the stored elements, plus O(1) metadata and lock state.

  • Auxiliary space per operation: O(1), excluding the elements stored in the stack.

  • The original input is not counted separately; values retained by the stack become part of its stored state.

  • Lock contention can add arbitrary waiting time, which is separate from the data structure’s algorithmic complexity.

Code Example

from threading import Lock
from typing import Generic, TypeVar

ItemT = TypeVar("ItemT")


class ThreadSafeStack(Generic[ItemT]):
    """A LIFO stack protected by a single mutex."""

    def __init__(self) -> None:
        self._items: list[ItemT] = []
        self._lock = Lock()

    def push(self, value: ItemT) -> None:
        """Add a value to the top of the stack."""
        with self._lock:
            self._items.append(value)

    def pop(self) -> ItemT:
        """Remove and return the top value, raising IndexError if empty."""
        with self._lock:
            if not self._items:
                raise IndexError("pop from empty ThreadSafeStack")
            return self._items.pop()

    def peek(self) -> ItemT:
        """Return the top value without removing it."""
        with self._lock:
            if not self._items:
                raise IndexError("peek from empty ThreadSafeStack")
            return self._items[-1]

    def is_empty(self) -> bool:
        """Return whether the stack contains no elements."""
        with self._lock:
            return not self._items

    def __len__(self) -> int:
        """Return the number of elements in the stack."""
        with self._lock:
            return len(self._items)


stack = ThreadSafeStack[int]()
stack.push(1)
stack.push(2)
print(stack.peek())       # 2
print(stack.pop())        # 2
print(len(stack))         # 1
print(stack.is_empty())   # False

For a standard-library alternative, queue.LifoQueue provides a thread-safe stack with blocking behavior. It can also enforce a maximum size, whereas the implementation above is unbounded.

Common Pitfalls

  • Checking and popping in separate calls: if not stack.is_empty(): stack.pop() is not atomic across methods. Use pop() itself and handle IndexError, or perform the check and removal under one lock.

  • Unlocking too early: Releasing the lock between validation and mutation allows another thread to change the stack between those steps.

  • Using different locks for different operations: All operations must protect the same underlying state with the same lock.

  • Holding the lock during slow work: Network calls, logging backends, or callbacks should occur outside the critical section.

  • Ignoring capacity requirements: For a bounded, blocking stack, use a lock with condition variables or queue.LifoQueue(maxsize=...).

  • Interview follow-up: Interviewers commonly ask why a plain list is insufficient, how exceptions affect lock release, and how to implement atomic push, pop, and peek operations.

13

How can I implement a stack with an O(1) find-middle operation?

Implement the stack with a direct middle pointer and maintain it whenever the stack size changes. The implementation below uses a Python list for stack storage and linked node references for constant-time middle navigation; it returns the lower middle element when the stack has an even number of elements.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The list stores nodes in bottom-to-top order, so self._stack[-1] is the top element. Each node also has links to the node above and below it.

  • push() appends a node to the list.

  • pop() removes the last node from the list.

  • _middle points directly to the current middle node.

  • find_middle() reads _middle.value without traversing the stack.

  • The middle pointer is updated using parity:

  • After a push into an even-sized stack, the middle moves one position upward.

  • After a pop from an odd-sized stack, the middle moves one position downward.

In Python specifically, self._stack[(len(self._stack) - 1) // 2] is already O(1) because list indexing is constant time. The middle pointer is what keeps find_middle() constant time when the stack is a linked list with no random access, which is the usual form of this interview question; the node links here show that technique.

Complexity

Operation Best case Average case Worst case Reason
find_middle() O(1) O(1) O(1) Reads the direct _middle reference.
push() O(1) O(1) amortized O(n) Python list append may occasionally resize the list.
pop() O(1) O(1) amortized O(n) Python list shrinking may occasionally reallocate storage.
peek() O(1) O(1) O(1) Reads self._stack[-1] after checking emptiness.

Space complexity is O(n) for the stored stack, with O(1) auxiliary space beyond that storage. The original caller-owned input collection is not counted separately; values copied into the stack are. There is no recursion stack.

Approach find_middle() push() / pop() When to use
Walk a linked stack from the top O(n) O(1) amortized Simple implementation when middle lookups are rare.
Track a middle pointer O(1) O(1) amortized When find_middle() must be constant time.

Walkthrough

The implementation uses the lower middle element, at zero-based index (n - 1) // 2 when the stack is ordered bottom-to-top.

Operation Stack bottom → top Size Middle
Push 10 [10] 1 10
Push 20 [10, 20] 2 10
Push 30 [10, 20, 30] 3 20
Pop 30 [10, 20] 2 10

Code Example

from __future__ import annotations

from dataclasses import dataclass
from typing import Generic, TypeVar

T = TypeVar("T")


@dataclass(slots=True)
class _Node(Generic[T]):
    value: T
    below: _Node[T] | None = None
    above: _Node[T] | None = None


class StackWithFindMiddle(Generic[T]):
    """A stack with constant-time lower-middle lookup."""

    def __init__(self) -> None:
        self._stack: list[_Node[T]] = []
        self._middle: _Node[T] | None = None
        self._size = 0

    def push(self, value: T) -> None:
        """Add a value to the top of the stack."""
        new_node = _Node(value)

        if self._stack:
            old_top = self._stack[-1]
            new_node.below = old_top
            old_top.above = new_node

        self._stack.append(new_node)

        if self._size == 0:
            self._middle = new_node
        elif self._size % 2 == 0:
            if self._middle is None or self._middle.above is None:
                raise RuntimeError("Invalid middle pointer")
            self._middle = self._middle.above

        self._size += 1

    def pop(self) -> T:
        """Remove and return the top value."""
        if not self._stack:
            raise IndexError("pop from empty stack")

        removed = self._stack.pop()
        new_top = self._stack[-1] if self._stack else None

        if new_top is not None:
            new_top.above = None

        removed.below = None
        removed.above = None

        if self._size == 1:
            self._middle = None
        elif self._size % 2 == 1:
            if self._middle is None or self._middle.below is None:
                raise RuntimeError("Invalid middle pointer")
            self._middle = self._middle.below

        self._size -= 1
        return removed.value

    def peek(self) -> T:
        """Return the top value without removing it."""
        if not self._stack:
            raise IndexError("peek from empty stack")
        return self._stack[-1].value

    def find_middle(self) -> T:
        """Return the lower middle value in O(1) time."""
        if self._middle is None:
            raise IndexError("find_middle from empty stack")
        return self._middle.value

    def is_empty(self) -> bool:
        """Return whether the stack contains no elements."""
        return self._size == 0

    def __len__(self) -> int:
        return self._size


example = StackWithFindMiddle[int]()
example.push(10)
example.push(20)
example.push(30)

print(example.find_middle())  # 20
print(example.peek())         # 30
print(example.pop())          # 30
print(example.find_middle())  # 10

Common Pitfalls

  • Empty stack: pop(), peek(), and find_middle() raise IndexError.

  • One element: the single element is both the top and the middle.

  • Even-sized stacks: state the convention clearly; this implementation returns the lower middle.

  • Duplicates and negative values: values are stored as-is; no comparisons or special handling are needed.

  • Already sorted input: ordering does not affect the stack or middle-pointer updates.

  • Common interview follow-up: explain that an array-backed stack already gives O(1) middle access by index, why a linked-list stack needs the middle pointer, and why parity determines which direction the pointer moves.

14

How do you implement a linked list using stacks?

A linked list’s core operations (insert, delete and read at a position, and walking forwards or backwards) can be built from two stacks that meet at a cursor: the left stack holds the elements before the cursor, and the right stack holds the elements after it, with the nearest element on top. Moving the cursor pops from one stack and pushes onto the other, and inserting or deleting at the cursor is O(1), just like a linked list where you already hold a pointer to the node. Reaching an arbitrary index costs O(distance moved), matching a linked list’s O(n) traversal. Text editors use this same idea for their cursor (a gap-buffer-like design).

Read full answer

Applies toPython, Java, C++ and similar languages; a classic data-structure design exercise

Idea

List:        A  B  C | D  E        (cursor between C and D)
left stack:  [A, B, C]   top = C   (element before the cursor)
right stack: [E, D]      top = D   (element after the cursor)
  • Move right: pop from right, push onto left.

  • Move left: pop from left, push onto right.

  • Insert at cursor: push onto left (or right).

  • Delete at cursor: pop from right.

Implementation in Python

class StackLinkedList:
    """List with a cursor, built from two stacks (Python lists used as stacks)."""

    def __init__(self, items=()):
        self.left = []                    # elements before the cursor
        self.right = list(reversed(items))  # elements after the cursor; top = next element

    def __len__(self):
        return len(self.left) + len(self.right)

    def move_to(self, index):
        if not 0 <= index <= len(self):
            raise IndexError("index out of range")
        while len(self.left) > index:     # move cursor left
            self.right.append(self.left.pop())
        while len(self.left) < index:     # move cursor right
            self.left.append(self.right.pop())

    def insert(self, index, value):
        self.move_to(index)
        self.right.append(value)          # new element sits right after the cursor

    def delete(self, index):
        self.move_to(index)
        if not self.right:
            raise IndexError("nothing to delete")
        return self.right.pop()

    def get(self, index):
        self.move_to(index)
        if not self.right:
            raise IndexError("index out of range")
        return self.right[-1]             # peek

    def to_list(self):
        return self.left + self.right[::-1]

ll = StackLinkedList(["A", "B", "D"])
ll.insert(2, "C")          # A B C D
ll.insert(4, "E")          # A B C D E
print(ll.to_list())        # ['A', 'B', 'C', 'D', 'E']
print(ll.delete(0))        # A
print(ll.get(1), ll.to_list())   # C ['B', 'C', 'D', 'E']

Complexity

Operation Cost
Insert or delete at the cursor O(1)
Move cursor by k positions O(k)
Insert, delete or get at index i O(distance from the cursor to i), O(n) worst case
Space O(n)

Sequential work (for example inserting many items next to each other) is cheap because the cursor is already nearby, which is exactly the access pattern of a linked list walked with a pointer.

Comparison With a Real Linked List

Aspect Two-stack list Singly linked list
Insert/delete at a known position O(1) at the cursor O(1) given the previous node
Random access O(distance) O(n)
Move backwards O(1) per step Not possible (singly linked)
Memory Contiguous arrays, good cache locality One node per element with a pointer

Variant: Using a Single Stack of Nodes

Another reading of the question is “store linked-list nodes and traverse them with a stack”, for example printing a singly linked list in reverse: push every node while walking forwards, then pop to visit them backwards in O(n) time and O(n) extra space.

Interview Tip

Explain the two-stack cursor design, show that insert and delete at the cursor are O(1) while moving costs O(distance), and connect it to text-editor cursors. Mention the reverse-traversal use of a single stack as well, in case that is what the interviewer meant.

15

Implement a Doubly Linked List with stack semantics at minimal complexity

A doubly linked list with stack semantics is implemented most efficiently using nodes containing both previous and following references. The stack top is maintained at the tail, giving constant-time push, pop, and peek, while also supporting constant-time insertion or removal when a node reference is already known.

Read full answer

Applies toPython 3.12

Design

  • Node: Stores a value, a previous pointer, and a following pointer.

  • Head and tail: Track both ends for traversal and efficient updates.

  • Stack top: The tail behaves as the top of a LIFO stack.

  • Owner identifier: Prevents an active node from one list being inserted into or removed from another list.

  • Reverse traversal: Uses a Python list as a stack with append() and pop().

Two plain LIFO stacks cannot provide arbitrary-position doubly linked-list updates in constant time. Linked nodes are therefore necessary; the stack interface is implemented on top of those links.

Complexity

Operation Best Average Worst Auxiliary Space
push, prepend O(1) O(1) O(1) O(1)
pop, peek O(1) O(1) O(1) O(1)
insert_after, insert_before O(1) O(1) O(1) O(1)
remove(node) O(1) O(1) O(1) O(1)
Find a node by value or index O(n) O(n) O(n) O(1)
Forward iteration O(n) O(n) O(n) O(1)
Reverse iteration O(n) amortized O(n) amortized O(n) amortized O(n)

Pointer updates are constant-time because each node directly references its neighbors. The list itself occupies O(n) storage. Auxiliary-space figures exclude that storage, and no recursion stack is used.

Stack Use Cases

The LIFO interface is useful for:

  • Undo history: Each action is pushed and later popped in reverse order.

  • Expression evaluation: Infix-to-postfix conversion and RPN evaluation use stack semantics.

  • Balanced parentheses: Opening delimiters are pushed and matched by popping.

  • DFS and backtracking: Pending states can be stored in a stack.

  • Function calls: The call stack tracks active function frames.

Code Example

from __future__ import annotations

from collections.abc import Iterator
from dataclasses import dataclass
from itertools import count
from typing import Generic, TypeVar

T = TypeVar("T")


@dataclass(slots=True)
class DoublyNode(Generic[T]):
    """A node containing its value and links to adjacent nodes."""

    value: T
    previous: DoublyNode[T] | None = None
    following: DoublyNode[T] | None = None
    owner_id: int = 0


class DoublyLinkedList(Generic[T]):
    """A doubly linked list whose tail also acts as the stack top."""

    _owner_ids = count()

    def __init__(self) -> None:
        self._head: DoublyNode[T] | None = None
        self._tail: DoublyNode[T] | None = None
        self._size = 0
        self._owner_id = next(self._owner_ids)

    def __len__(self) -> int:
        return self._size

    def push(self, value: T) -> None:
        """Push a value onto the stack by appending it to the tail."""
        node = DoublyNode(value, owner_id=self._owner_id)

        if self._tail is None:
            self._head = self._tail = node
        else:
            node.previous = self._tail
            self._tail.following = node
            self._tail = node

        self._size += 1

    def pop(self) -> T:
        """Remove and return the value at the stack top."""
        if self._tail is None:
            raise IndexError("pop from an empty doubly linked list")

        return self.remove(self._tail)

    def peek(self) -> T:
        """Return the stack-top value without removing it."""
        if self._tail is None:
            raise IndexError("peek from an empty doubly linked list")

        return self._tail.value

    def prepend(self, value: T) -> None:
        """Insert a value at the head of the list."""
        node = DoublyNode(value, owner_id=self._owner_id)

        if self._head is None:
            self._head = self._tail = node
        else:
            node.following = self._head
            self._head.previous = node
            self._head = node

        self._size += 1

    def insert_after(
        self, reference: DoublyNode[T], value: T
    ) -> DoublyNode[T]:
        """Insert a node immediately after an active reference node."""
        if reference.owner_id != self._owner_id:
            raise ValueError("node does not belong to this list")

        node = DoublyNode(value, owner_id=self._owner_id)
        following = reference.following

        node.previous = reference
        node.following = following
        reference.following = node

        if following is None:
            self._tail = node
        else:
            following.previous = node

        self._size += 1
        return node

    def remove(self, node: DoublyNode[T]) -> T:
        """Remove an active node and return its value."""
        if node.owner_id != self._owner_id:
            raise ValueError("node does not belong to this list")

        previous = node.previous
        following = node.following

        if previous is None:
            self._head = following
        else:
            previous.following = following

        if following is None:
            self._tail = previous
        else:
            following.previous = previous

        node.previous = None
        node.following = None
        node.owner_id = -1
        self._size -= 1
        return node.value

    def nodes(self) -> Iterator[DoublyNode[T]]:
        """Yield node references from head to tail."""
        current = self._head
        while current is not None:
            yield current
            current = current.following

    def __iter__(self) -> Iterator[T]:
        current = self._head
        while current is not None:
            yield current.value
            current = current.following

    def __reversed__(self) -> Iterator[T]:
        stack: list[T] = []
        for value in self:
            stack.append(value)

        while stack:
            yield stack.pop()


def demo() -> None:
    """Demonstrate stack operations on a doubly linked list."""
    items: DoublyLinkedList[int] = DoublyLinkedList()
    items.push(10)
    items.push(20)
    items.prepend(5)

    print(list(items))
    print(items.peek())
    print(items.pop())
    print(list(reversed(items)))


demo()
# Expected output:
# [5, 10, 20]
# 20
# 20
# [10, 5]

Edge Cases

  • Empty list: pop() and peek() raise IndexError.

  • One element: It is correctly both the head and tail.

  • Duplicates and negative values: Stored normally because identity comes from node references, not values.

  • Sorted or unsorted input: Ordering does not affect operation complexity.

  • Removed node reuse: Its links are cleared and its owner identifier is invalidated.

Common Pitfalls

  • Updating only one neighboring pointer breaks forward or backward traversal.

  • Forgetting to update head or tail when removing an endpoint.

  • Confusing constant-time node removal with finding a node: locating a node by value or index still takes O(n).

  • Assuming two stacks can replace linked nodes for arbitrary-position updates.

  • Forgetting that reverse iteration consumes O(n) auxiliary space for its stack.

16

How can a queue be implemented using two stacks?

A queue follows FIFO order: the first element inserted is the first one removed. Using two stacks, one stack accepts new elements while the other serves elements for removal; when the serving stack is empty, all elements are transferred between the stacks.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Incoming stack: enqueue pushes new elements onto this stack.

  • Outgoing stack: dequeue and peek remove or inspect the top element.

  • When the outgoing stack is empty, move every element from the incoming stack to it.

  • Transferring the elements reverses their order, so the oldest element becomes the top of the outgoing stack.

For example, after enqueueing 10, 20, and 30:

  1. incoming contains [10, 20, 30].

  2. The first dequeue transfers elements to outgoing, producing [30, 20, 10].

  3. Popping outgoing returns 10, preserving FIFO order.

  4. The next dequeue returns 20 without another transfer.

Each element is transferred at most once, which gives amortized constant-time queue operations.

Complexity

Operation Best Average Worst
enqueue O(1) O(1) amortized O(n) during a list resize
dequeue O(1) O(1) amortized O(n) when transferring all elements
peek O(1) O(1) amortized O(n) when transferring all elements
is_empty O(1) O(1) O(1)
  • Time: A sequence of m enqueues and d dequeues takes O(m + d) total time because each element is pushed, transferred, and popped only a constant number of times.

  • Space: O(n) auxiliary space for the two stacks, where n is the number of queued elements. There is no recursion stack. The queue’s stored elements are the data structure’s actual contents; if they are counted as input storage, total space is still O(n).

Code Example

class QueueUsingTwoStacks:
    """Implement a FIFO queue using two Python lists as stacks."""

    def __init__(self) -> None:
        self.incoming: list[int] = []
        self.outgoing: list[int] = []

    def enqueue(self, value: int) -> None:
        """Add a value to the back of the queue."""
        self.incoming.append(value)

    def dequeue(self) -> int:
        """Remove and return the value at the front of the queue."""
        if not self.outgoing:
            while self.incoming:
                self.outgoing.append(self.incoming.pop())

        if not self.outgoing:
            raise IndexError("dequeue from empty queue")

        return self.outgoing.pop()

    def peek(self) -> int:
        """Return the value at the front without removing it."""
        if not self.outgoing:
            while self.incoming:
                self.outgoing.append(self.incoming.pop())

        if not self.outgoing:
            raise IndexError("peek from empty queue")

        return self.outgoing[-1]

    def is_empty(self) -> bool:
        """Return whether the queue contains no elements."""
        return not self.incoming and not self.outgoing


queue = QueueUsingTwoStacks()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)

print(queue.dequeue())  # 10
print(queue.peek())     # 20
print(queue.dequeue())  # 20
print(queue.is_empty()) # False

Edge Cases

  • Empty queue: dequeue and peek raise IndexError rather than returning an invalid value.

  • One element: The first operation transfers and returns that element correctly.

  • Duplicate values: Duplicates are treated as separate elements and preserve their insertion order.

  • Negative values: Negative integers work normally because ordering depends on stack operations, not value comparisons.

  • Repeated dequeues: Once the outgoing stack is populated, subsequent removals do not transfer elements again.

  • Interleaved operations: New elements always enter the incoming stack and cannot overtake elements already in the outgoing stack.

Common Pitfalls

  • Do not transfer elements if the outgoing stack is already nonempty; doing so would break FIFO order.

  • Check for emptiness before accessing outgoing[-1].

  • Do not use list.pop(0) or list.insert(0, value); both are O(n). The implementation uses append and pop, which are O(1) amortized for this purpose.

  • A single dequeue can take O(n), but the cost is amortized across a sequence of operations.

  • Interviewers may ask why two stacks are needed, how the reversal works, or how the implementation would change for a generic element type.

17

How do you implement a queue using only one stack?

You can implement a queue with one explicit stack by using recursion for dequeue: pop the top element; if the stack is now empty, that element is the oldest one, so return it; otherwise recursively dequeue from the rest and push the popped element back on the way out. Enqueue is a simple push (O(1)), and dequeue is O(n) because it walks the whole stack. The call stack acts as the hidden second stack, so strictly speaking it uses one data structure you manage plus O(n) recursion depth.

Read full answer

Applies toPython, Java, C++ and similar languages; a common stacks-and-queues interview problem

Algorithm

  • Enqueue(x): stack.append(x).

  • Dequeue():

  • If the stack is empty, raise an error.

  • Pop the top item x.

  • If the stack is now empty, x was at the bottom (oldest), so return it.

  • Otherwise, result = dequeue() recursively, then push x back and return result.

Implementation in Python

class OneStackQueue:
    def __init__(self):
        self.stack = []

    def enqueue(self, x):
        self.stack.append(x)              # O(1)

    def dequeue(self):
        if not self.stack:
            raise IndexError("dequeue from empty queue")
        top = self.stack.pop()
        if not self.stack:                # top was the bottom element: the oldest
            return top
        front = self.dequeue()            # recurse; the call stack holds popped items
        self.stack.append(top)            # restore the order on the way back
        return front

    def is_empty(self):
        return not self.stack

q = OneStackQueue()
for x in (1, 2, 3):
    q.enqueue(x)
print(q.dequeue(), q.dequeue())   # 1 2
q.enqueue(4)
print(q.dequeue(), q.dequeue())   # 3 4

Trace for Stack [1, 2, 3] (top is 3)

dequeue(): pop 3 -> stack [1, 2], recurse
  dequeue(): pop 2 -> stack [1], recurse
    dequeue(): pop 1 -> stack [] -> return 1
  push 2 back -> [2]
push 3 back -> [2, 3]
result: 1

Complexity

Operation Time Extra space
Enqueue O(1) O(1)
Dequeue O(n) O(n) recursion depth

Comparison With the Two-Stack Queue

Approach Enqueue Dequeue Notes
One stack plus recursion O(1) O(n) every time Hidden second stack (call stack); recursion depth limit
Two stacks (in-stack and out-stack) O(1) O(1) amortised Preferred in practice
class TwoStackQueue:
    def __init__(self):
        self.inbox, self.outbox = [], []

    def enqueue(self, x):
        self.inbox.append(x)

    def dequeue(self):
        if not self.outbox:
            while self.inbox:             # each element moves at most once
                self.outbox.append(self.inbox.pop())
        if not self.outbox:
            raise IndexError("dequeue from empty queue")
        return self.outbox.pop()

q2 = TwoStackQueue()
for x in "abc":
    q2.enqueue(x)
print(q2.dequeue(), q2.dequeue(), q2.dequeue())   # a b c

Practical Notes

  • Python’s default recursion limit (about 1,000 frames) means the one-stack version fails for large queues; it is an exercise, not production code.

  • In real code, use collections.deque for an O(1) queue.

Interview Tip

Explain the recursive dequeue and that the call stack acts as the second stack, give its O(n) dequeue cost, then mention the two-stack queue with O(1) amortised operations as the practical alternative. Acknowledging the recursion-depth limit shows careful thinking.

18

How to implement a stack using two queues with efficient push in Python?

Stack implemented using two queues with efficient push means simulating LIFO behavior by using two FIFO queues, while keeping the push() operation O(1) and performing the element transfer on pop() or peek().

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Goal: Force LIFO from two FIFO structures. With push-efficient design, every new element is placed directly into the active queue, so insertion stays cheap.

  • Active queue: q1 holds every element in push order, so the most recently pushed element is always at its rear.

  • Transfer on pop: To get the stack top (which is the last pushed element), move every element except the final one from the active queue to the empty helper queue. The remaining element is removed and returned as the stack top, then swap the two queues so the helper becomes empty for the next operation.

  • LIFO mapping: The last element pushed ends up being the only element left in the active queue before transfer, so popping it matches stack behavior.

Time and Space Complexity

Operation Complexity Reason
push(x) O(1) Insert directly into the active collections.deque with no loop.
pop() O(n) In the worst case move n-1 elements from active queue to helper queue for a stack of n elements.
peek()/top() O(n) Same transfer as pop(), but the moved element must be pushed back into the helper queue before swap.
is_empty() O(1) Check size of the active queue.
size() O(1) Return length of the active queue.
  • Space complexity: O(n) in total, which includes the two queues holding all n stack elements. The recursion stack is not used here (iterative). The input elements themselves are counted.

  • Cases: Best/Average/Worst for push() are all O(1). For pop()/peek() best case O(1) only if the stack has exactly 1 element (no moves), average/worst O(n). No amortized case applies to a single pop() by fixed transfer.

Edge Cases to Handle

  • Empty input: pop() and peek() must raise an error (do not pop from empty queues).

  • One element: push once, pop returns it and stack becomes empty.

  • Duplicates: Allowed. The queue identity of values must not be assumed unique.

  • Negative numbers: Must be stored and returned as is (integers).

  • Already sorted input: No effect on correctness or the stated complexities.

  • Large n: Be aware pop() becomes linear and must not use list.pop(0) or list.insert(0, x) anywhere.

Step-By-Step Trace (Example)

Trace for operations: push(10), push(20), push(30), pop()

Step Operation Active q1 (front -> rear) Helper q2 Stack view (top on right conceptually) Notes
1 push(10) [10] [] [10] Push efficient: append to active queue.
2 push(20) [10, 20] [] [10, 20] Direct append, top would be 20.
3 push(30) [10, 20, 30] [] [10, 20, 30] Direct append, top is 30.
4 pop() Move 10 and 20 to q2, leaving [30]; pop 30. [10, 20] [10, 20] Swap: q1 = [10, 20] becomes active and q2 = []. Returns 30 after moving 2 elements.

Code Example

from collections import deque
from typing import Optional

class StackWithTwoQueues:
    """
    A stack implemented using two queues with efficient push.

    - push(x): O(1)
    - pop():   O(n)
    - peek():  O(n)
    - is_empty(): O(1)
    """
    def __init__(self) -> None:
        # Active queue holds stack elements in FIFO form for transfer
        self.q1: deque[int] = deque()
        # Helper queue used to reverse order on pop/peek
        self.q2: deque[int] = deque()

    def push(self, value: int) -> None:
        """Push an element onto the stack. Push is efficient (O(1))."""
        # Push directly into active queue
        self.q1.append(value)

    def pop(self) -> int:
        """Remove and return the top element of the stack. O(n)."""
        if self.is_empty():
            raise IndexError("pop from empty stack")
        # Move all except last element from q1 to q2
        while len(self.q1) > 1:
            self.q2.append(self.q1.popleft())
        # The last element in q1 is the stack top
        top_element: int = self.q1.popleft()
        # Swap q1 and q2 so q1 becomes the active queue
        self.q1, self.q2 = self.q2, self.q1
        return top_element

    def peek(self) -> int:
        """Return the top element without removing it. O(n)."""
        if self.is_empty():
            raise IndexError("peek from empty stack")
        # Move all except last element from q1 to q2
        while len(self.q1) > 1:
            self.q2.append(self.q1.popleft())
        # Last element is top
        top_element: int = self.q1[0]
        # Move it to q2 as well and swap to restore order
        self.q2.append(self.q1.popleft())
        # Swap q1 and q2
        self.q1, self.q2 = self.q2, self.q1
        return top_element

    def is_empty(self) -> bool:
        """Check if the stack is empty. O(1)."""
        return len(self.q1) == 0

    def size(self) -> int:
        """Return the number of elements in the stack. O(1)."""
        return len(self.q1)

if __name__ == "__main__":
    stack = StackWithTwoQueues()
    stack.push(10)
    stack.push(20)
    stack.push(30)
    print(stack.peek())  # Expected output: 30
    print(stack.pop())   # Expected output: 30
    print(stack.pop())   # Expected output: 20
    print(stack.is_empty()) # Expected output: False

Best Practices

  • Use the right tools: Use collections.deque for popleft() (O(1)) instead of list.pop(0) or list.insert(0, x). Do not reach for either in any loop here.

  • Swap, don’t copy: Swap self.q1 and self.q2 after transfer. After swap, q2 is the old q1 which will be empty and ready to be reused.

  • Guard early: Always check is_empty() before pop() or peek() and raise IndexError.

  • Keep push direct: To satisfy “efficient push”, never move elements on push(); only move on pop()/peek().

  • No recursion: This design is iterative to avoid hitting Python’s recursion limit.

Common Pitfalls

  • Forgetting the swap: If you don’t swap q1 and q2, the helper queue becomes the “active” one incorrectly and future operations break.

  • Moving the wrong count: For pop(), move until len(self.q1) == 1, then pop that single element. For peek(), move all except last but re-insert that last element before swapping.

  • Using list.pop(0): list.pop(0) is O(n) per call and would stack up badly; always use deque.popleft().

  • Not restoring state for peek: Failing to return the last element to the structure will corrupt the stack order.

  • Assuming push-efficient = both efficient: With exactly two queues you cannot have both push() and pop() O(1) at the same time; choosing push-efficient is the point of this variant.

  • Interview follow-up to expect: “If you want efficient pop instead, which side do you put elements on?” Be ready to state the trade-off clearly.

19

How do you implement three stacks using one array?

The standard single-array partitioning solution divides one backing array into three contiguous regions and maintains a separate top index for each stack. Each stack behaves as a normal LIFO stack within its assigned region.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For an array of capacity n, calculate each stack’s boundaries:

  • Stack 0: indices [0, n // 3)

  • Stack 1: indices [n // 3, 2 * n // 3)

  • Stack 2: indices [2 * n // 3, n)

Each stack has a top index:

  • top = start - 1 means the stack is empty.

  • push writes at top + 1 and advances the top.

  • pop reads from top and moves it backward.

  • peek reads from top without removing the value.

Because the regions are contiguous, pushing or popping one stack never affects another stack.

Complexity

Operation Best Average Worst Reason
push O(1) O(1) O(1) Writes to a preallocated list index
pop O(1) O(1) O(1) Reads one index and updates the top
peek O(1) O(1) O(1) Reads one index
is_empty O(1) O(1) O(1) Compares top and start indices
  • Total space: O(n) for the shared backing array.

  • Auxiliary space: O(1) for boundary and top indices; the input itself is not separately counted.

  • Each stack can hold approximately n / 3 elements. Remainder capacity is assigned to the later stacks.

Edge Cases

  • Empty stack: pop and peek raise IndexError.

  • One element: The element is pushed and popped normally.

  • Duplicates and negative numbers: Valid values with no special handling.

  • Full stack: push raises IndexError rather than writing into another stack’s region.

  • Invalid stack ID: Only IDs 0, 1, and 2 are accepted.

  • Capacity below three: Rejected because every stack needs at least one slot.

Code Example

class ThreeStacks:
    """Implement three LIFO stacks using one preallocated list."""

    def __init__(self, capacity: int) -> None:
        if capacity < 3:
            raise ValueError("capacity must be at least 3")

        self._values: list[int] = [0] * capacity
        self._starts: list[int] = [
            capacity * stack_id // 3 for stack_id in range(3)
        ]
        self._ends: list[int] = [
            capacity * (stack_id + 1) // 3 for stack_id in range(3)
        ]
        self._tops: list[int] = [start - 1 for start in self._starts]

    def _validate_stack_id(self, stack_id: int) -> None:
        if stack_id not in (0, 1, 2):
            raise IndexError("stack_id must be 0, 1, or 2")

    def push(self, stack_id: int, value: int) -> None:
        self._validate_stack_id(stack_id)

        next_index = self._tops[stack_id] + 1
        if next_index >= self._ends[stack_id]:
            raise IndexError(f"stack {stack_id} is full")

        self._values[next_index] = value
        self._tops[stack_id] = next_index

    def pop(self, stack_id: int) -> int:
        self._validate_stack_id(stack_id)

        top = self._tops[stack_id]
        if top < self._starts[stack_id]:
            raise IndexError(f"stack {stack_id} is empty")

        value = self._values[top]
        self._values[top] = 0
        self._tops[stack_id] = top - 1
        return value

    def peek(self, stack_id: int) -> int:
        self._validate_stack_id(stack_id)

        top = self._tops[stack_id]
        if top < self._starts[stack_id]:
            raise IndexError(f"stack {stack_id} is empty")

        return self._values[top]

    def is_empty(self, stack_id: int) -> bool:
        self._validate_stack_id(stack_id)
        return self._tops[stack_id] < self._starts[stack_id]


stacks = ThreeStacks(9)
stacks.push(0, 10)
stacks.push(0, 20)
stacks.push(1, 30)
stacks.push(2, -40)

print(stacks.pop(0))      # 20
print(stacks.peek(1))     # 30
print(stacks.pop(2))      # -40
print(stacks.is_empty(0)) # False

Best Practices

  • Use zero-based stack IDs consistently and validate them at API boundaries.

  • Check for empty before pop or peek; do not rely on a sentinel value because valid data may contain 0.

  • Preallocating the shared array gives constant-time writes and makes each stack’s capacity explicit.

  • Keep each stack’s top within its own region to prevent cross-stack corruption.

  • If workloads require highly uneven capacities, a fixed three-way partition may waste space; movable-boundary designs are more complex and may require O(n) data movement.

Interview Tips

Common follow-up questions include:

  • How would you support size(stack_id)?

  • How would you resize the shared array while preserving all elements?

  • How would you implement the structure with three separate lists?

  • What changes if stack 0 needs to grow beyond one-third of the array?

The key invariant is that every stack’s top must remain between its start and end boundaries.

20

How do you reverse a string using a stack?

A stack reverses a string by applying the last-in, first-out (LIFO) principle: push each character onto the stack, then pop characters into a new string. The characters are retrieved in the opposite order from which they were inserted.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  1. Create an empty stack.

  2. Traverse the string from left to right, pushing each character with append.

  3. Pop characters from the stack with pop and append them to the result.

  4. Return the completed string.

For example, with "stack":

Operation Stack Result
Push s ["s"] ""
Push t ["s", "t"] ""
Push a ["s", "t", "a"] ""
Push c ["s", "t", "a", "c"] ""
Push k ["s", "t", "a", "c", "k"] ""
Pop k ["s", "t", "a", "c"] "k"
Pop c ["s", "t", "a"] "kc"
Pop a ["s", "t"] "kca"
Pop t ["s"] "kcat"
Pop s [] "kcats"

Complexity

Case Time Space Reason
Best O(n) O(n) Every character must be pushed and popped.
Average O(n) O(n) The stack contains at most n characters.
Worst O(n) O(n) The same operations occur regardless of character values.
  • Time: Each of the n characters is pushed and popped once. Python list append and pop are O(1) amortized.

  • Space: O(n) auxiliary space for the stack, excluding the input and returned string. The returned string also uses O(n) space; if input and output are included, total space remains O(n).

Code Example

def reverse_string(text: str) -> str:
    """Reverse a string using a LIFO stack."""
    stack: list[str] = []
    result: list[str] = []

    for character in text:
        stack.append(character)

    while stack:
        result.append(stack.pop())

    return "".join(result)


print(reverse_string("stack"))  # Expected output: "kcats"

Edge Cases

  • Empty string: Returns "" because the stack and result remain empty.

  • One character: Pushes and pops that character, returning the same value.

  • Spaces and punctuation: Treated as ordinary characters.

  • Unicode: Python iterates Unicode code points, but reversing code points can split a user-perceived character such as a combined accent sequence.

Common Pitfalls

  • Peeking an empty stack: Accessing stack[-1] without checking if stack: raises IndexError.

  • Using the front of the list: pop(0) is O(n) and defeats the purpose of stack operations. Use pop() instead.

  • Expecting reverse(): Strings are immutable, so create a separate result rather than trying to reverse one in place.

  • Overcomplicating the solution: Python’s text[::-1] is simpler, but a stack demonstrates the LIFO technique interviewers expect.

21

How do you reverse a stack without using any additional data structure?

To reverse a stack without an extra stack, list or queue, use recursion, letting the call stack hold elements temporarily. The algorithm uses two recursive functions: reverse pops the top element, reverses the rest, and then calls insert_at_bottom, which places that element underneath everything else by popping down to the empty stack, pushing the element, and pushing the others back. This takes O(n^2) time and O(n) recursion depth.

Read full answer

Applies toPython, Java, C++ and similar languages; a classic recursion-on-stacks interview problem

Algorithm

reverse(stack):
    if stack is empty: return
    top = pop()
    reverse(stack)              # reverse the remaining elements
    insert_at_bottom(stack, top)

insert_at_bottom(stack, x):
    if stack is empty: push(x); return
    top = pop()
    insert_at_bottom(stack, x)
    push(top)

Implementation in Python

def insert_at_bottom(stack, x):
    if not stack:
        stack.append(x)
        return
    top = stack.pop()
    insert_at_bottom(stack, x)
    stack.append(top)

def reverse(stack):
    if not stack:
        return
    top = stack.pop()
    reverse(stack)
    insert_at_bottom(stack, top)

s = [1, 2, 3, 4]          # top is 4
reverse(s)
print(s)                  # [4, 3, 2, 1]  (top is now 1)

Trace for [1, 2, 3] (top is 3)

reverse: pop 3, reverse [1, 2]
  reverse: pop 2, reverse [1]
    reverse: pop 1, reverse [] -> return
    insert_at_bottom([], 1) -> [1]
  insert_at_bottom([1], 2) -> [2, 1]
insert_at_bottom([2, 1], 3) -> [3, 2, 1]

Complexity

Measure Cost Reason
Time O(n^2) insert_at_bottom is O(k) for a stack of size k, called n times
Space O(n) recursion depth The call stack holds popped elements

“No additional data structure” means none that you allocate explicitly; the recursion still uses O(n) memory on the call stack.

Practical Considerations

  • Python’s default recursion limit is around 1,000 frames, so large stacks raise RecursionError. Increasing the limit with sys.setrecursionlimit risks crashing the interpreter if the C stack runs out.

  • In production code, stack.reverse() on a Python list is O(n) and in place.

  • If the stack is implemented as a linked list, you can reverse it in O(n) time and O(1) extra space by reversing the node pointers, which genuinely uses no additional structure.

class Node:
    def __init__(self, val, next=None):
        self.val, self.next = val, next

def reverse_linked_stack(top):
    prev = None
    while top:
        top.next, prev, top = prev, top, top.next
    return prev               # new top

top = Node(3, Node(2, Node(1)))        # 3 -> 2 -> 1 (3 is the top)
top = reverse_linked_stack(top)
vals = []
while top:
    vals.append(top.val); top = top.next
print(vals)                            # [1, 2, 3]

Interview Tip

Present the reverse plus insert_at_bottom recursion, trace a small example, and state O(n^2) time and O(n) recursion depth. Mentioning the linked-list pointer reversal as an O(n), O(1)-space alternative shows you think beyond the textbook answer.

22

How do you sort a stack using recursion?

To sort a stack with recursion (so the largest element ends on top), use two recursive functions. sort_stack pops the top element, recursively sorts the rest, and then calls sorted_insert to put that element back in the right place. sorted_insert pushes the element directly if the stack is empty or its top is smaller or equal; otherwise it pops the top, recursively inserts the element below it, and pushes the popped top back. The method uses only stack operations plus the call stack, runs in O(n^2) time, and uses O(n) recursion depth. It works like insertion sort.

Read full answer

Applies toPython, Java, C++ and similar languages; a common recursion and stack interview problem

Algorithm

sort_stack(stack):
    if stack is empty: return
    x = pop()
    sort_stack(stack)
    sorted_insert(stack, x)

sorted_insert(stack, x):
    if stack is empty or top <= x: push(x); return
    t = pop()
    sorted_insert(stack, x)
    push(t)

Implementation in Python

def sorted_insert(stack, x):
    if not stack or stack[-1] <= x:
        stack.append(x)
        return
    top = stack.pop()
    sorted_insert(stack, x)
    stack.append(top)

def sort_stack(stack):
    if not stack:
        return
    x = stack.pop()
    sort_stack(stack)
    sorted_insert(stack, x)

s = [30, -5, 18, 14, -3]     # top is -3
sort_stack(s)
print(s)                     # [-5, -3, 14, 18, 30]  (top is 30, the largest)

Trace for [3, 1, 2] (top is 2)

sort_stack: pop 2, sort [3, 1]
  sort_stack: pop 1, sort [3]
    sort_stack: pop 3, sort [] -> return
    sorted_insert([], 3) -> [3]
  sorted_insert([3], 1): 3 > 1, pop 3, insert 1 -> [1], push 3 -> [1, 3]
sorted_insert([1, 3], 2): 3 > 2, pop 3; top 1 <= 2, push 2 -> [1, 2]; push 3 -> [1, 2, 3]

Complexity

Measure Cost
Time O(n^2) in the worst case (each insertion may walk the whole sorted part)
Best case O(n) when the stack is already sorted (each insertion pushes immediately)
Space O(n) recursion depth
Stability Stable: equal elements keep their relative order because of the <= comparison

Variations

  • Descending order (smallest on top): change the comparison to stack[-1] >= x.

  • Custom ordering: pass a key function, for example sorting tasks by priority.

Practical Notes

  • Python’s recursion limit (about 1,000) restricts this to small stacks; an iterative version with a second stack avoids it (see “sort a stack using another stack”).

  • In real code, sort the underlying list directly (stack.sort(), O(n log n)).

Interview Tip

Describe the two recursive functions, trace a small example, and give the O(n^2) time and O(n) recursion depth. Comparing it to insertion sort and mentioning the iterative two-stack alternative shows you understand both the algorithm and its limits.

23

How do you sort a stack using another stack?

To sort a stack using one temporary stack, repeatedly pop an element from the input stack and, while the temporary stack’s top is greater than that element, move those larger elements back to the input stack; then push the element onto the temporary stack. The temporary stack always stays sorted (largest on top), so when the input is empty, it holds the sorted result. This is iterative insertion sort with stacks: O(n^2) time in the worst case and O(n) extra space, with no recursion-depth limits.

Read full answer

Applies toPython, Java, C++ and similar languages; a common stack interview problem (for example in Cracking the Coding Interview)

Algorithm

temp = empty stack
while input is not empty:
    x = input.pop()
    while temp is not empty and temp.top > x:
        input.push(temp.pop())
    temp.push(x)
return temp        # sorted with the largest on top

Implementation in Python

def sort_with_stack(stack):
    temp = []
    while stack:
        x = stack.pop()
        while temp and temp[-1] > x:      # move larger items back to the input
            stack.append(temp.pop())
        temp.append(x)
    return temp                            # ascending from bottom to top

print(sort_with_stack([34, 3, 31, 98, 92, 23]))   # [3, 23, 31, 34, 92, 98]

Trace for Input [34, 3, 31] (top is 31)

Step Popped Moves back to input Temp stack after push
1 31 none [31]
2 3 31 [3] (input now [34, 31])
3 31 none [3, 31]
4 34 none [3, 31, 34]

Complexity

Measure Cost
Time, worst case O(n^2) (for example when items arrive in an order that forces many moves)
Time, best case O(n) (each element pushes straight onto temp)
Extra space O(n) for the temporary stack
Stability Stable with > (equal elements are not moved past each other)

Variations

  • Descending result (smallest on top): change the condition to temp[-1] < x.

  • Sort back into the original stack: after building temp, pop everything back into the original stack, which reverses the order (smallest on top).

  • Restricted environments: if you may use only push, pop, peek and is_empty, this algorithm still works because it uses nothing else.

Comparison With the Recursive Version

Approach Extra structure Recursion Large inputs
Two stacks (iterative) One temporary stack None Works (limited only by memory)
Recursion only None explicit (call stack) O(n) depth Hits recursion limits

Interview Tip

Describe how the temporary stack stays sorted by moving larger elements back, trace a short example, and state O(n^2) time and O(n) space. Noting the best case, stability, and that it avoids recursion limits shows a complete understanding.

24

How can you implement a shuffling algorithm using a stack?

A fair shuffle with stacks works like drawing cards from random depths of a deck: for each position, pick a uniformly random depth k among the remaining cards, pop k cards onto a temporary stack, pop the target card into the output stack, then push the temporary cards back. Every remaining card is equally likely to be chosen at each step, so all n! orderings are equally likely, giving a uniform shuffle in O(n^2) time with only stack operations. If random access is allowed, the Fisher-Yates shuffle does the same in O(n) and is what you should use in practice; naive approaches like “riffle once” or random swaps with a biased range are not uniform.

Read full answer

Applies tocard and game simulations, randomised test data, sampling, and data structures interviews

Stack-Only Uniform Shuffle

import random

def stack_shuffle(stack, rng=random):
    """Uniform shuffle using only push and pop on stacks."""
    out, temp = [], []
    while stack:
        k = rng.randrange(len(stack))     # depth of the card to draw (0 = top)
        for _ in range(k):
            temp.append(stack.pop())       # set aside cards above it
        out.append(stack.pop())            # draw the chosen card
        while temp:
            stack.append(temp.pop())       # put the others back in order
    return out

deck = list(range(1, 9))
print(stack_shuffle(deck, random.Random(42)))
# [7, 8, 1, 4, 5, 6, 3, 2]

At each step the chosen depth k is uniform over the remaining cards, so each card has probability 1/remaining of being drawn next: the same reasoning that makes Fisher-Yates uniform.

Checking Uniformity

import random
from collections import Counter

def stack_shuffle(stack, rng):
    out, temp = [], []
    while stack:
        k = rng.randrange(len(stack))
        for _ in range(k):
            temp.append(stack.pop())
        out.append(stack.pop())
        while temp:
            stack.append(temp.pop())
    return out

rng = random.Random(1)
counts = Counter(tuple(stack_shuffle([1, 2, 3], rng)) for _ in range(60000))
print(len(counts), min(counts.values()) > 9500)   # 6 True  (all 3! orders, each near 10,000)

Complexity

Algorithm Time Extra space Uniform?
Stack draw (above) O(n^2) O(n) Yes
Fisher-Yates (array) O(n) O(1) Yes
Single riffle (split and interleave) O(n) O(n) No: about 7 riffles are needed to mix a 52-card deck well
Swap each element with any random index 0..n-1 O(n) O(1) No: biased (n^n outcomes do not divide evenly into n! orders)

Fisher-Yates for Comparison

import random

def fisher_yates(a, rng=random):
    for i in range(len(a) - 1, 0, -1):
        j = rng.randint(0, i)          # inclusive: 0..i
        a[i], a[j] = a[j], a[i]
    return a

print(fisher_yates(list(range(1, 9)), random.Random(42)))
# [4, 5, 7, 8, 3, 6, 1, 2]

Python’s own random.shuffle implements Fisher-Yates.

Practical Notes

  • Use a cryptographically secure source (secrets.SystemRandom()) for gambling, lotteries or security-sensitive shuffles.

  • A pseudo-random generator with a small state cannot produce every permutation of very large decks; for 52 cards, 52! is about 2^226, larger than many simple generators’ period or seed space.

  • Seed the generator only for reproducible tests.

Interview Tip

Describe the draw-from-random-depth method, explain why it is uniform, and give its O(n^2) cost, then recommend Fisher-Yates when random access is allowed. Pointing out why naive swaps or a single riffle are biased shows strong understanding of randomness.

25

How do you check whether parentheses are balanced using a stack?

To check balanced brackets, scan the string from left to right. Push every opening bracket onto a stack. For each closing bracket, the stack must be non-empty and its top must be the matching opening bracket; pop it if so, otherwise the string is unbalanced. At the end, the string is balanced only if the stack is empty. This handles (), [] and {} together, runs in O(n) time, and uses O(n) space in the worst case.

Read full answer

Applies tocompilers and parsers, code editors, expression evaluators, JSON and XML validators; LeetCode 20 "Valid Parentheses"

Implementation in Python

def is_balanced(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
        # other characters are ignored
    return not stack

tests = ["{[()()]}", "([)]", "((", "a*(b+c)-{d/[e]}", ")("]
print([is_balanced(t) for t in tests])
# [True, False, False, True, False]

Trace for {[()]}

Char Action Stack
{ push {
[ push { [
( push { [ (
) top ( matches, pop { [
] top [ matches, pop {
} top { matches, pop empty

Stack empty at the end, so the string is balanced.

Failure Cases

Input Why it fails
([)] ) arrives when the top is [
(( Stack not empty at the end
)( ) arrives when the stack is empty

Complexity

  • Time: O(n), each character is pushed and popped at most once.

  • Space: O(n) in the worst case (all opening brackets); O(1) if only one bracket type is allowed (see below).

Optimisation for a Single Bracket Type

With only ( and ), a counter replaces the stack:

def balanced_round(s):
    depth = 0
    for ch in s:
        if ch == "(":
            depth += 1
        elif ch == ")":
            depth -= 1
            if depth < 0:
                return False
    return depth == 0

print(balanced_round("(()())"), balanced_round("())("))   # True False

This does not work for multiple bracket types, because ([)] has correct counts but wrong nesting.

Practical Extensions

  • Report the error position: store (char, index) on the stack and return the index of the first mismatch or the unclosed bracket.

  • Ignore brackets inside strings or comments when checking source code (track a simple lexer state).

  • Early exit: if the string length is odd and it contains only brackets, it cannot be balanced.

Interview Tip

Explain the push-on-open, match-on-close, empty-at-end rule, trace a short example, and give O(n) time and space. Mentioning the counter shortcut for one bracket type, and why it fails for several, shows depth.

26

How do you find duplicate (redundant) parentheses in an expression?

An expression has duplicate (redundant) parentheses when a pair of brackets encloses nothing new, either an empty pair or a pair that directly wraps another pair, as in ((a+b)). With a stack: push every character except ). When you see ), pop until the matching (, counting the characters popped. If nothing was popped before reaching (, the pair adds nothing and is a duplicate. This runs in O(n) time and assumes the expression is balanced.

Read full answer

Applies toexpression simplification, linters and formatters, compilers and interview problems on stacks

Idea

  • In ((a+b)), the inner ) pops b, +, a and then (, so it is fine. The outer ) immediately finds ( on top: the outer pair is redundant.

  • In (a+(b)/c), the inner (b) pops only b. It is a duplicate only under the stricter definition below.

Implementation in Python

def has_duplicate_parentheses(expr):
    stack = []
    for ch in expr:
        if ch == ")":
            inside = 0
            while stack and stack[-1] != "(":
                stack.pop()
                inside += 1
            if inside == 0:          # nothing between this pair and the previous one
                return True
            stack.pop()              # remove the "("
        elif ch != " ":
            stack.append(ch)
    return False

tests = ["((a+b))", "(a+b)*(c+d)", "((a+b)+((c+d)))", "(((a+(b)))+(c+d))", "()"]
print([has_duplicate_parentheses(t) for t in tests])
# [True, False, True, True, True]

Trace for ((a+b))

Char Action Stack
( push (
( push ( (
a, +, b push ( ( a + b
) pop b, +, a (3 items), then pop ( (
) top is ( immediately: 0 items, so duplicate

Stricter Definition: Brackets Around a Single Operand

Some versions also treat (b) (one operand, no operator) as redundant. Check whether the popped content contains an operator:

def has_redundant_brackets(expr):
    stack = []
    for ch in expr:
        if ch == ")":
            has_operator = False
            while stack and stack[-1] != "(":
                if stack.pop() in "+-*/":
                    has_operator = True
            stack.pop()
            if not has_operator:
                return True
        elif ch != " ":
            stack.append(ch)
    return False

print(has_redundant_brackets("(a+(b))"), has_redundant_brackets("(a+b)*c"))   # True False

Clarify which definition the interviewer wants. A fuller “redundant for precedence” check, where (a*b)+c is also redundant, requires comparing operator precedence inside and outside the brackets, which is a harder problem.

Complexity

  • Time: O(n), each character is pushed and popped at most once.

  • Space: O(n) for the stack.

Edge Cases

  • Assume the input is balanced; otherwise validate first, or handle an empty stack when popping (.

  • Ignore whitespace.

  • Multi-character operands ((abc)) work the same way.

Interview Tip

Explain the rule (when ) arrives, there must be something between it and its (), trace ((a+b)), and state O(n) time and space. Asking whether (b) should count as redundant, and showing the operator check, shows careful reading of the requirements.

27

How is a stack used to evaluate a postfix expression?

To evaluate a postfix (Reverse Polish Notation) expression, scan the tokens from left to right with a stack of operands. Push each number. When you see an operator, pop two operands (the first pop is the right operand, the second is the left), apply the operator, and push the result. When the tokens run out, the stack must hold exactly one value, which is the answer. Postfix needs no parentheses or precedence rules, so evaluation is a single O(n) pass.

Read full answer

Applies tocalculators (HP RPN calculators), compilers and interpreters (stack-based bytecode such as the JVM and CPython), spreadsheet engines; LeetCode 150 "Evaluate Reverse Polish Notation"

Algorithm

for token in tokens:
    if token is a number: push(token)
    else:
        right = pop(); left = pop()
        push(apply(token, left, right))
result = pop()   # stack must now be empty

Implementation in Python

import operator

OPS = {
    "+": operator.add,
    "-": operator.sub,
    "*": operator.mul,
    "/": lambda a, b: int(a / b),    # truncate toward zero, as LeetCode 150 requires
}

def eval_postfix(tokens):
    stack = []
    for tok in tokens:
        if tok in OPS:
            if len(stack) < 2:
                raise ValueError(f"not enough operands for {tok!r}")
            right = stack.pop()
            left = stack.pop()
            stack.append(OPS[tok](left, right))
        else:
            stack.append(int(tok))
    if len(stack) != 1:
        raise ValueError("malformed expression")
    return stack[0]

print(eval_postfix("2 3 1 * + 9 -".split()))          # -4   ((2 + 3*1) - 9)
print(eval_postfix(["4", "13", "5", "/", "+"]))        # 6    (4 + 13/5)
print(eval_postfix("10 6 9 3 + -11 * / * 17 + 5 +".split()))   # 22

Trace for 2 3 1 * + 9 -

Token Action Stack
2 push 2
3 push 2 3
1 push 2 3 1
* pop 1, 3; push 3*1 = 3 2 3
+ pop 3, 2; push 2+3 = 5 5
9 push 5 9
- pop 9, 5; push 5-9 = -4 -4

Operand Order Matters

For - and /, the second popped value is the left operand: 8 2 / means 8 / 2 = 4, not 2 / 8. Getting this backwards is the most common bug.

Complexity

  • Time: O(n) for n tokens.

  • Space: O(n) in the worst case (many operands before operators).

Error Handling

Problem Detection
Too few operands Fewer than two items when an operator arrives
Too many operands More than one item left at the end
Division by zero Check right == 0 before dividing
Unknown token int() raises ValueError

Extensions

  • Unary operators (negation, sqrt): pop one operand.

  • Functions with fixed arity: pop the required number of arguments.

  • Floating point: use float and true division.

  • Prefix (Polish) notation: scan from right to left, and the first popped operand is the left one.

Why It Matters

Stack-based virtual machines execute code in essentially this way. CPython compiles a + b * c into bytecode that loads a, b, c, then performs BINARY_OP instructions (multiply, then add) on its value stack.

Interview Tip

Explain push operands, pop two on an operator, push the result, and one value at the end. Stress the operand order for subtraction and division, and mention error checks and the link to stack-based bytecode for extra depth.

28

How do you convert an infix expression to postfix using a stack?

To convert infix to postfix, use Dijkstra’s shunting-yard algorithm: scan tokens left to right, send operands straight to the output, and keep operators on a stack. Before pushing an operator, pop operators of higher precedence (or equal precedence, if the new operator is left-associative) to the output. Push ( onto the stack, and on ) pop to the output until the matching (. At the end, pop all remaining operators. The conversion runs in O(n) time.

Read full answer

Applies tocalculators, compilers and expression parsers, spreadsheet formula engines, and query languages

Rules

Token Action
Operand Append to output
( Push
) Pop to output until (; discard the (
Operator o While the top is an operator t with higher precedence than o, or equal precedence and o is left-associative, pop t to output; then push o
End of input Pop all remaining operators to output

Precedence: ^ (highest, right-associative), then * and /, then + and - (left-associative).

Implementation in Python

import re

PREC = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3}
RIGHT_ASSOC = {"^"}

def to_postfix(expr):
    tokens = re.findall(r"\d+|[A-Za-z]+|[-+*/^()]", expr)
    out, ops = [], []
    for tok in tokens:
        if tok.isalnum():
            out.append(tok)
        elif tok == "(":
            ops.append(tok)
        elif tok == ")":
            while ops and ops[-1] != "(":
                out.append(ops.pop())
            if not ops:
                raise ValueError("mismatched parentheses")
            ops.pop()                                   # discard "("
        else:
            while (ops and ops[-1] != "(" and
                   (PREC[ops[-1]] > PREC[tok] or
                    (PREC[ops[-1]] == PREC[tok] and tok not in RIGHT_ASSOC))):
                out.append(ops.pop())
            ops.append(tok)
    while ops:
        if ops[-1] == "(":
            raise ValueError("mismatched parentheses")
        out.append(ops.pop())
    return " ".join(out)

print(to_postfix("a + b * c"))              # a b c * +
print(to_postfix("(a + b) * c"))            # a b + c *
print(to_postfix("a - b - c"))              # a b - c -
print(to_postfix("a ^ b ^ c"))              # a b c ^ ^
print(to_postfix("3 + 4 * 2 / (1 - 5) ^ 2 ^ 3"))   # 3 4 2 * 1 5 - 2 3 ^ ^ / +

Trace for a + b * c

Token Output Stack
a a
+ a +
b a b +
* a b + * (higher precedence than ‘+`, so `+` stays)
c a b c + *
end a b c * +

Associativity

  • a - b - c means (a - b) - c, so equal-precedence - pops first: a b - c -.

  • a ^ b ^ c means a ^ (b ^ c) (right-associative), so ^ does not pop an equal ^: a b c ^ ^.

Complexity

  • Time: O(n); each token is pushed and popped at most once.

  • Space: O(n) for the stack and output.

Extensions

  • Unary minus: detect a - at the start or after ( or an operator, and convert it to a separate unary operator with high precedence.

  • Functions (max(a, b)): push function names, handle commas by popping to the nearest (.

  • Evaluate directly: instead of producing output, keep a second stack of values and apply each popped operator immediately (two-stack evaluation).

Interview Tip

State the shunting-yard rules, especially the precedence and associativity condition for popping, and trace a short example. Showing why a - b - c and a ^ b ^ c produce different patterns demonstrates real understanding.

29

How do you build a binary expression tree from an expression?

A binary expression tree stores operators in internal nodes and operands in leaves, so that an in-order traversal gives the infix expression and a post-order traversal gives postfix. The simplest way to build it is from postfix: scan tokens, push a leaf node for each operand, and for each operator, pop two nodes (right, then left), make them the children of a new operator node, and push that node. The last node left is the root. For an infix input, first convert it to postfix with the shunting-yard algorithm, or build the tree directly with two stacks (operators and nodes). Both approaches take O(n).

Read full answer

Applies tocompilers (abstract syntax trees), calculators, symbolic algebra, query planners, and rule engines

Building From Postfix

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

OPERATORS = set("+-*/^")

def build_from_postfix(tokens):
    stack = []
    for tok in tokens:
        if tok in OPERATORS:
            right = stack.pop()
            left = stack.pop()
            stack.append(Node(tok, left, right))
        else:
            stack.append(Node(tok))
    if len(stack) != 1:
        raise ValueError("malformed expression")
    return stack[0]

def inorder(n):
    if n.left is None:
        return n.val
    return f"({inorder(n.left)} {n.val} {inorder(n.right)})"

def evaluate(n):
    if n.left is None:
        return float(n.val)
    a, b = evaluate(n.left), evaluate(n.right)
    return {"+": a + b, "-": a - b, "*": a * b, "/": a / b, "^": a ** b}[n.val]

root = build_from_postfix("3 4 + 2 * 7 -".split())
print(inorder(root))     # (((3 + 4) * 2) - 7)
print(evaluate(root))    # 7.0

Resulting tree:

-
       / \
      *   7
     / \
    +   2
   / \
  3   4

Building Directly From Infix (Two Stacks)

import re

PREC = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3}

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def build_from_infix(expr):
    nodes, ops = [], []

    def reduce():
        op = ops.pop()
        right, left = nodes.pop(), nodes.pop()
        nodes.append(Node(op, left, right))

    for tok in re.findall(r"\d+|[A-Za-z]+|[-+*/^()]", expr):
        if tok.isalnum():
            nodes.append(Node(tok))
        elif tok == "(":
            ops.append(tok)
        elif tok == ")":
            while ops[-1] != "(":
                reduce()
            ops.pop()
        else:
            while (ops and ops[-1] != "(" and
                   (PREC[ops[-1]] > PREC[tok] or (PREC[ops[-1]] == PREC[tok] and tok != "^"))):
                reduce()
            ops.append(tok)
    while ops:
        reduce()
    return nodes[0]

def postorder(n):
    return n.val if n.left is None else f"{postorder(n.left)} {postorder(n.right)} {n.val}"

print(postorder(build_from_infix("a + b * (c - d)")))   # a b c d - * +

This is the shunting-yard algorithm, but instead of writing operators to an output list, each popped operator combines the top two nodes into a subtree.

Traversals and Their Meaning

Traversal Result
In-order (with parentheses) Infix expression
Pre-order Prefix (Polish) notation
Post-order Postfix (RPN); also the evaluation order

Complexity

  • Time: O(n) to build; O(n) to evaluate or traverse.

  • Space: O(n) for nodes and stacks; evaluation recursion depth equals tree height.

Practical Notes

  • Unary operators (negation) create nodes with one child.

  • Compilers build abstract syntax trees this way (often with recursive-descent or Pratt parsers), then optimise them: constant folding turns 2 * 3 into 6.

Interview Tip

Show the postfix build (operand leaves, operator pops two and pushes a subtree), mention converting infix with shunting-yard or using two stacks, and demonstrate traversals and evaluation. Linking it to compiler syntax trees shows practical relevance.

30

How do you check balanced parentheses in a file too large for memory?

For a file that does not fit in memory, stream it in fixed-size chunks and run the normal stack algorithm across chunk boundaries. The stack holds only unmatched opening brackets, so memory is O(maximum nesting depth), not O(file size). For a single bracket type you need only a counter (O(1) memory). If the nesting itself could be enormous, compress the stack with run-length encoding, or spill it to disk. Report the byte offset of the first error so it can be found in the file.

Read full answer

Applies tovalidating huge JSON, XML or log files, source-code archives, data pipelines and streaming parsers

Streaming Algorithm (Multiple Bracket Types)

import io

PAIRS = {")": "(", "]": "[", "}": "{"}
OPENERS = set(PAIRS.values())

def check_stream(stream, chunk_size=1 << 20):
    stack, offset = [], 0
    while True:
        chunk = stream.read(chunk_size)
        if not chunk:
            break
        for i, ch in enumerate(chunk):
            if ch in OPENERS:
                stack.append(ch)
            elif ch in PAIRS:
                if not stack or stack[-1] != PAIRS[ch]:
                    return False, offset + i          # position of the first error
                stack.pop()
        offset += len(chunk)
    return (not stack), (offset if stack else None)

# Simulate a large file with a small chunk size so brackets span chunk boundaries
data = "{" + "[()]" * 1000 + "}"
print(check_stream(io.StringIO(data), chunk_size=7))        # (True, None)
print(check_stream(io.StringIO("{[(])}"), chunk_size=2))    # (False, 3)

In production, open the file with open(path, "r", encoding="utf-8") (or read bytes and compare byte values) and use a large chunk size such as 1 to 16 MB for efficient I/O.

Memory Usage

Case Memory
One bracket type O(1): an integer depth counter
Several bracket types O(maximum depth) for the stack of unmatched openers
Very deep nesting Run-length encode the stack: store (char, count) pairs
Pathologically deep nesting Spill stack segments to a temporary file

Run-Length Encoded Stack

Deeply nested files often repeat the same opener (for example millions of [). Storing [("[", 2_000_000)] instead of two million entries keeps memory small:

def push(stack, ch):
    if stack and stack[-1][0] == ch:
        stack[-1][1] += 1
    else:
        stack.append([ch, 1])

def pop_matches(stack, opener):
    if not stack or stack[-1][0] != opener:
        return False
    stack[-1][1] -= 1
    if stack[-1][1] == 0:
        stack.pop()
    return True

s = []
for ch in "[[[[(":
    push(s, ch)
print(s)                        # [['[', 4], ['(', 1]]
print(pop_matches(s, "("), s)   # True [['[', 4]]

Practical Considerations

  • Encoding: brackets are ASCII, so reading bytes avoids decoding cost; with UTF-8, multi-byte characters never contain ASCII bracket bytes, so byte-level scanning stays correct.

  • Strings and comments: for real formats (JSON, code), track lexer state so brackets inside quoted strings are ignored, including escaped quotes that may cross chunk boundaries.

  • Performance: the job is I/O-bound; use buffered reads, memory-mapped files, or vectorised scanning (find bracket positions with bytes.translate or NumPy) to skip non-bracket bytes quickly.

  • Parallelism: for very large files on fast storage, split into chunks and process them in parallel with an associative merge.

Complexity

  • Time: O(N) for N bytes, one pass.

  • Memory: O(chunk size + nesting depth), or O(chunk size) for one bracket type.

Interview Tip

Explain streaming in chunks with the stack carried across boundaries, point out that memory depends on nesting depth rather than file size, and mention the counter shortcut, run-length encoding and error offsets. Noting that brackets inside strings need lexer state shows practical experience.

31

How do you check brace balance in a 1 TB file in parallel?

To check brackets in parallel, split the file into chunks and let each worker reduce its chunk to a compact summary: the unmatched closing brackets at the start (which must be matched by earlier chunks) and the unmatched opening brackets at the end (which later chunks must close). These summaries combine associatively: match the left summary’s open brackets against the right summary’s close brackets. So the chunks can be processed independently and merged in a tree or left-to-right reduction. The file is balanced if the final summary has no unmatched brackets and no type mismatch occurred.

Read full answer

Applies todistributed and multi-core processing (Python multiprocessing, Spark, MapReduce, GPUs), validating huge logs, JSON Lines and data dumps

Chunk Summary

For each chunk, run a stack scan:

  • A closing bracket with an empty stack is unmatched on the left: record it in need (in order).

  • A closing bracket that mismatches the top means the file is invalid (a type mismatch inside the chunk).

  • Openers left on the stack at the end form open (in order).

For one bracket type, the summary is just two integers: (closers_needed, openers_left).

Merging Summaries

merge(L, R):
    match L.open (from its end) against R.need (from its start)
    if a pair mismatches: invalid
    leftover R.need  -> appended to L.need
    leftover L.open  -> followed by R.open

Implementation in Python

from functools import reduce
from multiprocessing import Pool

PAIRS = {")": "(", "]": "[", "}": "{"}

def summarize(chunk):
    need, stack = [], []
    for ch in chunk:
        if ch in "([{":
            stack.append(ch)
        elif ch in PAIRS:
            if stack:
                if stack[-1] != PAIRS[ch]:
                    return None                    # mismatch inside the chunk
                stack.pop()
            else:
                need.append(PAIRS[ch])             # opener this chunk needs from the left
    return (need, stack)

def merge(left, right):
    if left is None or right is None:
        return None
    l_need, l_open = left
    r_need, r_open = right
    l_open = list(l_open)
    i = 0
    while i < len(r_need) and l_open:
        if l_open.pop() != r_need[i]:
            return None
        i += 1
    return (l_need + r_need[i:], l_open + r_open)

def is_balanced_parallel(chunks, workers=4):
    with Pool(workers) as pool:
        summaries = pool.map(summarize, chunks)
    final = reduce(merge, summaries, ([], []))
    return final == ([], [])

if __name__ == "__main__":
    text = "{[(" + "()[]{}" * 500 + ")]}"
    chunks = [text[i:i + 97] for i in range(0, len(text), 97)]
    print(is_balanced_parallel(chunks))                       # True
    bad = "{[(" + "()" * 50 + "])}"
    print(is_balanced_parallel([bad[i:i + 13] for i in range(0, len(bad), 13)]))   # False

merge is associative, so the summaries can also be combined in a balanced tree (log depth), which suits distributed frameworks.

Scaling to 1 TB

Concern Approach
Splitting Split by byte ranges (for example 256 MB chunks); brackets are single ASCII bytes, so any byte boundary works
Reading Each worker reads its own range with seek or memory mapping; parallel reads from fast SSDs or a distributed file system (HDFS, S3)
Throughput Scan bytes with vectorised operations or native code; a single core scans hundreds of MB to a few GB per second, so 1 TB on many cores takes minutes
Summary size Usually tiny; in the worst case it is proportional to unmatched brackets, which can be run-length encoded
Merge Tree reduction in Spark (treeReduce) or a final step on the driver
Error location Store the byte offset of the first mismatch with each summary

Caveats

  • Brackets inside strings or comments: lexer state (inside a string or not) depends on earlier chunks. Solutions: compute summaries for both possible starting states and pick the right one during the merge, or use a format with safe split points (JSON Lines split at newlines).

  • Mismatch detection inside a chunk is local, but a mismatch between chunks appears only during the merge.

Complexity

  • Work: O(N) total.

  • Parallel time: O(N / P + merge cost), where the merge depends on the size of the summaries and is O(log P) levels for a tree reduction.

Interview Tip

Explain the chunk summary (unmatched closers needed, unmatched openers left), show that merging is associative so chunks can be processed in parallel, and discuss practical 1 TB concerns like byte-range splitting and tree reduction. Mentioning the lexer-state problem for strings shows real depth.

32

How would you design large-scale, real-time undo operations using stacks?

A scalable undo system keeps two stacks per document or session: an undo stack of applied operations and a redo stack of undone ones. Each entry is a command that knows how to apply and invert itself. New actions push onto the undo stack and clear the redo stack. To work at scale and in real time, store small inverse operations rather than full snapshots, coalesce rapid keystrokes, cap or spill old history to storage, persist history so undo survives reconnects, and in collaborative editors undo only the user’s own operations, transforming them against others’ changes (operational transformation or CRDTs).

Read full answer

Applies totext and code editors, design tools, spreadsheets, collaborative documents (Google Docs, Figma-like tools), and admin consoles with "undo" actions

Core Design: Command Pattern With Two Stacks

from collections import deque

class InsertText:
    def __init__(self, pos, text):
        self.pos, self.text = pos, text
    def apply(self, doc):
        doc.text = doc.text[:self.pos] + self.text + doc.text[self.pos:]
    def invert(self):
        return DeleteText(self.pos, self.text)

class DeleteText:
    def __init__(self, pos, text):
        self.pos, self.text = pos, text
    def apply(self, doc):
        doc.text = doc.text[:self.pos] + doc.text[self.pos + len(self.text):]
    def invert(self):
        return InsertText(self.pos, self.text)

class Document:
    def __init__(self, max_history=1000):
        self.text = ""
        self.undo_stack = deque(maxlen=max_history)   # bounded: oldest entries drop off
        self.redo_stack = []

    def execute(self, cmd):
        cmd.apply(self)
        self.undo_stack.append(cmd)
        self.redo_stack.clear()                        # a new action invalidates redo

    def undo(self):
        if self.undo_stack:
            cmd = self.undo_stack.pop()
            cmd.invert().apply(self)
            self.redo_stack.append(cmd)

    def redo(self):
        if self.redo_stack:
            cmd = self.redo_stack.pop()
            cmd.apply(self)
            self.undo_stack.append(cmd)

doc = Document()
doc.execute(InsertText(0, "Hello"))
doc.execute(InsertText(5, " world"))
doc.undo();  print(repr(doc.text))     # 'Hello'
doc.redo();  print(repr(doc.text))     # 'Hello world'
doc.execute(DeleteText(0, "Hello "))
print(repr(doc.text), len(doc.redo_stack))   # 'world' 0

A deque(maxlen=...) acts as a stack (append and pop at the right end) that silently drops the oldest entries when full.

Scaling Considerations

Concern Technique
Memory per session Store operations (deltas), not snapshots; cap history length or total bytes
Very long histories Keep recent entries in memory and older ones in storage (database, object store), loaded on demand
Noise from keystrokes Coalesce: merge consecutive typing within about a second, or within one word, into one undo step
Grouped actions Transactions or macro commands: “paste and format” is one entry containing several operations
Expensive operations Store the inverse cheaply (for example the deleted text) instead of recomputing
Durability Append operations to a log; rebuild stacks after reconnects or crashes
Snapshots Periodic snapshots plus deltas allow quick restore without replaying everything
Many sessions Keep stacks per document per user in a fast store (Redis) with TTLs; partition by document

Real-Time Collaboration

With several users editing at once, a global undo stack would undo other people’s work. Instead:

  • Keep a per-user undo stack of that user’s operations.

  • When undoing, compute the inverse and transform it against operations applied since (operational transformation), or use CRDT-based undo (Yjs’s UndoManager tracks local changes and reverses only those).

  • Send the inverse as a new operation to everyone, so history stays append-only and consistent.

Undo for Server-Side Actions

For actions with external effects (sending an email, charging a card), undo is a compensating action (cancel, refund) rather than a true reversal. Common patterns:

  • Delayed execution: show “Undo” for a few seconds before actually sending (Gmail’s “Undo send”).

  • Soft deletes: mark records as deleted and purge later.

Interview Tip

Describe the command pattern with undo and redo stacks and why new actions clear redo, then address scale: deltas instead of snapshots, coalescing, bounded and persisted history, and per-user undo with transformation in collaborative editing. Mentioning compensating actions for irreversible operations shows real-world thinking.

33

How does stack memory allocation work in large-data scenarios?

Stack allocation reserves memory by simply moving a stack pointer: each function call pushes a frame with its local variables, return address and saved registers, and returning pops it. This is extremely fast (no allocator, no fragmentation, automatic cleanup) and cache-friendly, but the stack is small and fixed per thread (commonly 8 MB for the main thread on Linux, 1 MB on Windows), so large data must live on the heap. In large-data scenarios, the stack holds only small fixed-size values and pointers, while big buffers go to the heap, memory-mapped files or arena (stack-like) allocators that bring stack-style speed to large allocations.

Read full answer

Applies toC, C++, Rust, Go, Java and Python runtimes, embedded systems and high-performance data processing

Stack vs Heap

Aspect Stack Heap
Allocation cost Move the stack pointer (about one instruction) Allocator call (free lists, size classes, locks or thread caches)
Deallocation Automatic on function return Manual (free), RAII, reference counting or garbage collection
Size limit Small, fixed per thread Limited by RAM and address space
Lifetime Until the function returns Until freed
Fragmentation None Possible
Typical contents Locals, return addresses, small arrays, pointers to heap data Large buffers, dynamic structures, objects outliving a call

What Goes Wrong With Large Data on the Stack

void process(void) {
    double matrix[2000][2000];   /* about 32 MB: overflows an 8 MB stack -> crash */
    /* ... */
}

Fix: allocate on the heap (malloc, std::vector, Box), or use memory-mapped files for data larger than RAM.

#include <vector>

void process() {
    std::vector<double> matrix(2000 * 2000);   // 32 MB on the heap; freed automatically
    // index with matrix[i * 2000 + j]
}

Techniques for Large-Data Workloads

Technique Idea Example
Keep handles on the stack, data on the heap Stack holds pointers, sizes, iterators std::vector, Rust Vec, Go slices
Arena / bump allocators Allocate from a big block by bumping a pointer, free all at once Per-request arenas in servers; compilers; Rust bumpalo
Memory pools Reuse fixed-size blocks Network buffers, game engines
Memory-mapped files Let the OS page data in on demand Databases, search indexes, numpy.memmap
Streaming Process chunks instead of loading everything File parsers, ETL pipelines
Escape analysis Compiler places non-escaping objects on the stack automatically Go, Java HotSpot (scalar replacement)
Larger thread stacks Configure stack size when deep recursion is unavoidable ulimit -s, pthread_attr_setstacksize, -Xss in Java, threading.stack_size in Python

Arena Allocation in Python Terms

Python objects always live on the heap, but the idea can be shown with a preallocated buffer and a “stack pointer”:

class Arena:
    def __init__(self, size):
        self.buf = bytearray(size)
        self.top = 0                       # like a stack pointer

    def alloc(self, n):
        if self.top + n > len(self.buf):
            raise MemoryError("arena full")
        start = self.top
        self.top += n
        return memoryview(self.buf)[start:start + n]

    def mark(self):
        return self.top

    def release_to(self, mark):            # free everything allocated after mark
        self.top = mark

arena = Arena(1024)
m = arena.mark()
a = arena.alloc(100); b = arena.alloc(200)
print(arena.top)          # 300
arena.release_to(m)
print(arena.top)          # 0

Deep Recursion With Large Inputs

Recursive algorithms (DFS, quicksort, tree traversal) on large inputs can overflow the call stack. Replace recursion with an explicit stack on the heap:

def dfs_iterative(graph, start):
    seen, stack, order = {start}, [start], []
    while stack:
        node = stack.pop()
        order.append(node)
        for nxt in reversed(graph[node]):
            if nxt not in seen:
                seen.add(nxt)
                stack.append(nxt)
    return order

chain = {i: [i + 1] for i in range(100_000)}
chain[100_000] = []
print(len(dfs_iterative(chain, 0)))   # 100001  (no RecursionError)

Interview Tip

Explain why stack allocation is fast (pointer bump, automatic cleanup) but limited in size, then describe how large data is handled: heap allocation with stack handles, arenas, memory mapping, streaming, and explicit stacks instead of deep recursion. Quoting typical default stack sizes shows practical knowledge.

34

How do you solve the stock span problem using a stack?

The stock span for day i is the number of consecutive days up to and including day i on which the price was less than or equal to today’s price. A monotonic stack of indices with strictly decreasing prices solves it in O(n): for each day, pop all indices whose price is less than or equal to today’s; the span is the distance to the index left on top (or i + 1 if the stack is empty); then push today’s index. Each index is pushed and popped at most once, so the total work is linear.

Read full answer

Applies tofinancial analytics, monotonic-stack interview problems (LeetCode 901 "Online Stock Span"), and "previous greater element" style questions

Example

Prices: [100, 80, 60, 70, 60, 75, 85]

Day Price Span Reason
0 100 1 No earlier day
1 80 1 100 > 80
2 60 1 80 > 60
3 70 2 60 <= 70, then 80 > 70
4 60 1 70 > 60
5 75 4 60, 70, 60 <= 75, then 80 > 75
6 85 6 Everything back to 100

Implementation in Python

def stock_span(prices):
    spans, stack = [], []            # stack holds indices with decreasing prices
    for i, p in enumerate(prices):
        while stack and prices[stack[-1]] <= p:
            stack.pop()
        spans.append(i + 1 if not stack else i - stack[-1])
        stack.append(i)
    return spans

print(stock_span([100, 80, 60, 70, 60, 75, 85]))   # [1, 1, 1, 2, 1, 4, 6]

The index on top after popping is the previous greater element: the most recent day with a strictly higher price.

Online Version (Prices Arrive One at a Time)

class StockSpanner:
    def __init__(self):
        self.stack = []                  # (price, span) pairs, prices strictly decreasing

    def next(self, price):
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]  # absorb the spans of smaller prices
        self.stack.append((price, span))
        return span

s = StockSpanner()
print([s.next(p) for p in [100, 80, 60, 70, 60, 75, 85]])   # [1, 1, 1, 2, 1, 4, 6]

Storing spans instead of indices means you do not need to keep the whole price history.

Why It Is O(n)

  • Each index (or price) is pushed exactly once.

  • Each is popped at most once.

  • So the inner while loop runs at most n times in total, giving O(n) time and O(n) space. The amortised cost per next call is O(1).

Naive Approach for Comparison

Walking back from each day until a higher price is found is O(n^2) in the worst case, for example on steadily rising prices.

Related Monotonic-Stack Problems

Problem Stack keeps
Next greater element Decreasing stack, resolve on a larger value
Daily temperatures Indices waiting for a warmer day
Largest rectangle in histogram Increasing heights
Trapping rain water Decreasing heights

Interview Tip

Define the span precisely (consecutive days with price less than or equal to today), show the decreasing monotonic stack, trace an example, and justify O(n) by the push-once, pop-once argument. Offering the online StockSpanner version with stored spans shows strong command of the pattern.

35

How do you calculate trapped rainwater between towers using a stack?

With a stack, trapped rainwater is computed layer by layer. Keep a stack of indices with decreasing heights. When the current bar is taller than the bar on top, that top bar is the bottom of a basin: pop it, and if a bar remains on the stack, it is the left wall while the current bar is the right wall. The water held above the popped bottom is (min(left, right) - bottom height) x (distance between the walls - 1). Add it to the total and repeat, then push the current index. Each index is pushed and popped once, so the algorithm runs in O(n) time with O(n) space.

Read full answer

Applies tomonotonic-stack interview problems (LeetCode 42 "Trapping Rain Water"), terrain and reservoir modelling exercises

Implementation in Python

def trap(heights):
    stack, water = [], 0                       # indices with decreasing heights
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] < h:
            bottom = stack.pop()
            if not stack:
                break                          # no left wall: water flows away
            left = stack[-1]
            width = i - left - 1
            depth = min(heights[left], h) - heights[bottom]
            water += width * depth
        stack.append(i)
    return water

print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))   # 6
print(trap([4, 2, 0, 3, 2, 5]))                     # 9

Trace for [4, 2, 0, 3, 2, 5]

i h Pops (bottom) Left wall Width x depth Water so far
0 4 none 0
1 2 none 0
2 0 none 0
3 3 index 2 (h 0) index 1 (h 2) 1 x (2 - 0) = 2 2
3 3 index 1 (h 2) index 0 (h 4) 2 x (3 - 2) = 2 4
4 2 none 4
5 5 index 4 (h 2) index 3 (h 3) 1 x (3 - 2) = 1 5
5 5 index 3 (h 3) index 0 (h 4) 4 x (4 - 3) = 4 9

The stack fills water in horizontal layers: each pop adds one rectangular slab bounded by the nearest taller bars on both sides.

Why It Works

  • The stack holds bars in decreasing height, so the bar beneath the popped one is the nearest taller-or-equal bar on the left.

  • The current bar is the first taller bar on the right.

  • Water above the bottom is limited by the shorter of the two walls.

Complexity

Measure Cost
Time O(n): each index pushed once and popped at most once
Space O(n) for the stack

Alternative: Two Pointers (O(1) Space)

def trap_two_pointers(h):
    left, right = 0, len(h) - 1
    left_max = right_max = water = 0
    while left < right:
        if h[left] < h[right]:
            left_max = max(left_max, h[left])
            water += left_max - h[left]
            left += 1
        else:
            right_max = max(right_max, h[right])
            water += right_max - h[right]
            right -= 1
    return water

print(trap_two_pointers([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))   # 6

This computes water column by column using the rule water[i] = min(max left, max right) - height[i].

Approach Time Space Fills
Monotonic stack O(n) O(n) Horizontal layers
Two pointers O(n) O(1) Vertical columns
Prefix and suffix max arrays O(n) O(n) Vertical columns

Interview Tip

Explain the decreasing stack, how a taller bar pops a basin bottom and uses the left and right walls to compute a slab, and trace a small example. Mentioning the two-pointer O(1)-space solution as an alternative shows breadth.

36

How can you minimise stack overflow risk when memory is limited?

Stack overflow happens when the call stack exceeds its fixed size, usually because of deep or unbounded recursion or large local variables. To minimise the risk with limited memory: replace deep recursion with iteration and an explicit heap-allocated stack, keep stack frames small (move big buffers to the heap or static storage), bound recursion depth and validate input sizes, use tail recursion only where the compiler guarantees tail-call optimisation, choose algorithms with logarithmic depth (recurse on the smaller half in quicksort), and measure stack usage with static analysis, stack canaries or high-water marks, especially on embedded systems.

Read full answer

Applies toembedded and real-time firmware (FreeRTOS, Zephyr), systems programming in C, C++ and Rust, interpreters (Python, JavaScript), and recursive algorithms on large inputs

Common Causes

Cause Example
Unbounded or very deep recursion DFS on a long linked chain; recursive parsing of deeply nested JSON
Large local arrays char buf[64 * 1024] inside a function on a 4 KB task stack
Many small threads or tasks with tiny stacks RTOS tasks with 512-byte stacks
Hidden stack use alloca, variable-length arrays, large structs passed by value
Interrupt handlers Nested interrupts on the same stack

Techniques

1. Convert recursion to iteration

def tree_depth_iterative(root):
    """root is (value, [children]); explicit stack lives on the heap."""
    if root is None:
        return 0
    best, stack = 0, [(root, 1)]
    while stack:
        (val, children), d = stack.pop()
        best = max(best, d)
        for child in children:
            stack.append((child, d + 1))
    return best

# A chain 50,000 deep would overflow Python's default recursion limit (about 1,000)
node = (0, [])
for i in range(1, 50_000):
    node = (i, [node])
print(tree_depth_iterative(node))   # 50000

2. Keep frames small

  • Allocate large buffers on the heap, in static memory or from a memory pool.

  • Pass large structs by pointer or reference, not by value.

  • Avoid alloca and variable-length arrays with untrusted sizes.

3. Limit depth

  • Validate input: reject JSON nested deeper than, say, 512 levels (many parsers have such limits).

  • Pass a depth counter and stop or switch to an iterative fallback beyond a threshold.

4. Use algorithms with bounded depth

  • Quicksort: recurse on the smaller partition and loop on the larger, guaranteeing O(log n) stack depth.

  • Introsort (used by C++ std::sort) switches to heapsort when recursion gets too deep.

  • Balanced trees keep traversal depth at O(log n).

5. Tail-call optimisation (with care)

Scheme guarantees it; C and C++ compilers often apply it at higher optimisation levels but do not guarantee it; Python and Java do not perform it. Do not rely on it unless the language guarantees it.

6. Measure and monitor

Tool or method Environment
-fstack-usage (GCC) and static call-graph analysis Embedded C
Stack painting (fill with a pattern, check high-water mark) RTOS (uxTaskGetStackHighWaterMark in FreeRTOS)
Stack canaries and guard pages Detect overflow before memory corruption
ulimit -s, RLIMIT_STACK Linux processes
-Xss Java thread stack size

7. Configure stacks sensibly

  • Size task and thread stacks from measured worst-case usage plus a margin.

  • Use separate interrupt stacks where the hardware supports it.

  • In managed runtimes, run deep recursive work in a thread with a larger stack (threading.stack_size in Python, new Thread(group, runnable, name, stackSize) in Java).

Interview Tip

Name the causes (deep recursion, big locals), then give concrete fixes: iterative algorithms with explicit stacks, small frames, depth limits, smaller-half recursion, and measuring high-water marks. Pointing out that Python and Java do not optimise tail calls shows precise knowledge.

37

Which techniques improve locality of reference for a stack?

A stack has naturally good temporal locality (the top is touched repeatedly), and you can maximise spatial locality by storing elements contiguously in an array rather than as separately allocated linked nodes. Further techniques: store values inline instead of pointers to scattered objects, preallocate or grow geometrically to avoid reallocations, use chunked (segmented) arrays for huge stacks, keep elements small and aligned (pack fields, struct-of-arrays where useful), avoid false sharing in multi-threaded code with per-thread stacks, and keep hot data near the top by pushing in an order that matches access.

Read full answer

Applies tohigh-performance code in C, C++, Rust, Java and Go, interpreters' value stacks, graph traversal and parsing engines

Array-Based vs Linked Stacks

Aspect Contiguous array stack Linked-list stack
Memory layout Adjacent elements in one block Nodes scattered across the heap
Cache behaviour Top elements share cache lines; prefetch-friendly Each node access may miss the cache
Allocation Occasional reallocation (amortised O(1)) One allocation per push
Per-element overhead None Pointer plus allocator header

On modern CPUs, a cache miss to main memory costs on the order of 100 ns versus about 1 ns for an L1 hit, so layout often matters more than instruction count.

Techniques

1. Contiguous storage

#include <vector>

std::vector<int> stack;
stack.reserve(1 << 16);    // preallocate to avoid reallocation and copying
stack.push_back(42);
int top = stack.back();
stack.pop_back();

std::stack uses std::deque by default, which stores elements in chunks; std::stack<int, std::vector<int>> gives a fully contiguous layout.

2. Store values, not pointers

A stack of struct Frame { int node; int depth; } stored inline is far more cache-friendly than a stack of pointers to heap objects. In Java, a stack of int in an int[] beats ArrayDeque<Integer> (boxed objects scattered on the heap).

3. Compact elements

  • Use the smallest suitable types (32-bit indices instead of 64-bit pointers when possible).

  • Pack related fields so one element fits in as few bytes as practical; 64-byte cache lines hold 16 four-byte ints.

  • Consider struct of arrays if only some fields are read on hot paths.

4. Geometric growth and reuse

  • Grow by a factor (1.5x or 2x) to keep pushes amortised O(1) and reallocations rare.

  • Reuse the same stack across iterations (clear instead of reallocating) to keep memory warm in cache.

5. Segmented stacks for very large sizes

Fixed-size chunks (for example 4 KB or a page each) linked together avoid huge reallocations while preserving locality within each chunk.

6. Multi-threaded locality

  • Give each thread its own stack (work-stealing deques in fork/join pools) rather than sharing one contended stack.

  • Pad per-thread structures to separate cache lines to avoid false sharing.

7. Access order

In DFS, push children in the order that will be visited next so the most recently pushed (and most cache-warm) element is processed first.

Python Illustration

Python lists store pointers to objects, so locality is limited; for numeric data, an array or NumPy-backed buffer stores values contiguously:

from array import array

stack = array("i")          # contiguous C ints, not pointers to int objects
for v in range(5):
    stack.append(v)
print(stack.pop(), stack[-1], stack.itemsize)   # 4 3 4

Interview Tip

Explain why contiguous arrays beat linked nodes for cache behaviour, then list techniques: inline values, compact elements, preallocation, segmented arrays and per-thread stacks. Quoting the rough cost difference between a cache hit and a memory access shows you understand why it matters.

38

What is a lock-free stack, and where is it used?

A lock-free stack, classically the Treiber stack (R. Kent Treiber, 1986), is a linked-list stack where push and pop update the top pointer with an atomic compare-and-swap (CAS) instead of a lock. A thread reads the current top, prepares its change, and CASes the top from the old value to the new one; if another thread changed it first, the CAS fails and the thread retries. Because a failed CAS means another thread succeeded, the system always makes progress. Lock-free stacks are used in memory allocators and free lists, object pools, work-stealing schedulers and runtime internals, where blocking would hurt latency. They must handle the ABA problem and safe memory reclamation.

Read full answer

Applies toC++ (`std::atomic`), Java (`AtomicReference`), Rust (crossbeam), Go (`sync/atomic`), and OS kernels

Treiber Stack in Java

import java.util.concurrent.atomic.AtomicReference;

public class TreiberStack<T> {
    private static final class Node<T> {
        final T value;
        Node<T> next;
        Node(T value) { this.value = value; }
    }

    private final AtomicReference<Node<T>> top = new AtomicReference<>();

    public void push(T value) {
        Node<T> node = new Node<>(value);
        Node<T> oldTop;
        do {
            oldTop = top.get();
            node.next = oldTop;
        } while (!top.compareAndSet(oldTop, node));   // retry if top changed
    }

    public T pop() {
        Node<T> oldTop, newTop;
        do {
            oldTop = top.get();
            if (oldTop == null) return null;           // empty stack
            newTop = oldTop.next;
        } while (!top.compareAndSet(oldTop, newTop));
        return oldTop.value;
    }
}

Java’s garbage collector prevents a node from being reused while another thread still references it, which avoids the classic ABA problem in this version.

The ABA Problem (in Languages Without GC)

  1. Thread 1 reads top = A (with A.next = B) and is paused.

  2. Thread 2 pops A, pops B, frees B, then pushes A back (same address).

  3. Thread 1 resumes: CAS(top, A, B) succeeds because top is A again, but B was freed. The stack is now corrupt.

Fixes:

Technique Idea
Tagged pointers / version counters CAS on (pointer, counter); the counter changes on every update (double-width CAS or spare pointer bits)
Hazard pointers Threads announce nodes they are reading; nodes are not freed while announced
Epoch-based reclamation Free nodes only after all threads have moved past the epoch (crossbeam-epoch in Rust)
Garbage collection Java, Go, C#: nodes are not reused while referenced

Properties

Property Lock-free stack Mutex-protected stack
Blocking None; a stalled thread cannot block others A preempted lock holder blocks everyone
Progress Lock-free (some thread always completes) Can stall
Contention All threads CAS on one top pointer: a hot spot Also a hot spot, plus sleeping and waking costs
Complexity Higher (ABA, reclamation, memory ordering) Simple

Under very heavy contention, the single top pointer becomes a bottleneck. The elimination-backoff stack (Hendler, Shavit and Yerushalmi) lets a concurrent push and pop “cancel out” in a side array without touching top, improving scalability.

Where It Is Used

  • Memory allocators and free lists: per-size-class lists of free blocks.

  • Object and buffer pools: reuse of connections, network buffers, or task objects.

  • Runtime internals: garbage collector work lists, thread pool task caches.

  • Real-time and interrupt-safe code: no lock that could be held by a preempted thread.

  • Undo or event logs where many producers push and consumers pop in LIFO order.

Interview Tip

Describe CAS-based push and pop with the retry loop, explain why it is lock-free, and cover the ABA problem with its fixes (tagged pointers, hazard pointers, epochs, GC). Mentioning contention on the top pointer and elimination-backoff shows advanced understanding.

39

How can a stack be used in producer-consumer scenarios?

In a producer-consumer setup, producers add work items and consumers remove them through a shared buffer. Using a stack (LIFO) as that buffer means consumers always take the most recently produced item first. That suits cases where fresh items matter more than old ones (latest sensor reading, most recent user request), or where cache locality favours recently touched data (work-stealing schedulers process their own newest tasks). The buffer must be thread-safe (lock plus condition variables, or a lock-free stack), and usually bounded so producers block or drop items when it is full. The trade-off is that LIFO is unfair: old items can starve, so it is a poor fit when ordering or fairness matters.

Read full answer

Applies tothread pools and schedulers (Java ForkJoinPool, Go runtime, Tokio's LIFO slot), resource pools, real-time data feeds, and Java's `LinkedBlockingDeque`

Bounded Blocking LIFO Buffer in Python

import queue
import threading

buffer = queue.LifoQueue(maxsize=5)       # thread-safe, bounded stack
results = []
lock = threading.Lock()

def producer(start):
    for i in range(start, start + 5):
        buffer.put(i)                      # blocks when full

def consumer():
    while True:
        item = buffer.get()                # blocks when empty
        if item is None:
            buffer.task_done()
            break
        with lock:
            results.append(item)
        buffer.task_done()

consumers = [threading.Thread(target=consumer) for _ in range(2)]
for c in consumers: c.start()
producers = [threading.Thread(target=producer, args=(s,)) for s in (0, 100)]
for p in producers: p.start()
for p in producers: p.join()
buffer.join()                              # wait until all items are processed
for _ in consumers: buffer.put(None)       # one stop signal per consumer
for c in consumers: c.join()
print(len(results), sorted(results)[:3])   # 10 [0, 1, 2]

queue.LifoQueue wraps a list with a lock and condition variables, giving blocking put and get with a maximum size.

LIFO vs FIFO for Producer-Consumer

Aspect Stack (LIFO) Queue (FIFO)
Order Newest first Oldest first
Freshness Excellent Old items processed before new ones
Fairness Poor: old items can starve Fair
Cache locality Good: newest items likely still in cache Weaker
Latency under overload New requests served quickly; old ones wait or time out Everyone waits longer

Real-World Uses

  • Work-stealing schedulers: each worker pushes and pops its own tasks LIFO (good locality, depth-first execution of divide-and-conquer work), while idle workers steal from the other end FIFO (oldest, usually larger tasks). Java’s ForkJoinPool and Go’s scheduler follow this pattern; Tokio adds a LIFO slot for the most recently woken task.

  • Overload handling: some systems serve requests LIFO when overloaded, because the newest requests have clients still waiting, while old ones have likely already timed out (adaptive LIFO, described in Facebook’s work on queue management and controlled delay).

  • Resource pools: connection or buffer pools return the most recently released object, which is warm in cache and keeps idle objects at the bottom so they can be trimmed.

  • Latest-value feeds: a UI only needs the newest reading; older ones can be discarded.

Design Considerations

  • Bound the stack to apply backpressure, or drop the oldest entries when full (a bounded deque).

  • Avoid starvation: add timeouts, age limits, or switch to FIFO when the load is normal.

  • Thread safety: locks with condition variables, or lock-free stacks for high-throughput, low-latency paths.

  • Shutdown: use sentinel values or cancellation tokens so consumers exit cleanly.

Interview Tip

Explain the shared buffer, why LIFO helps freshness and locality, and the starvation trade-off, then give real examples: work-stealing schedulers, adaptive LIFO under overload and resource pools. Showing a bounded, thread-safe implementation demonstrates practical skill.

40

How would you maintain a history of operations on a stack?

There are three main ways to keep a history of stack operations. Log every operation (push x, pop) in an append-only list, so you can replay the stack to any point. Make the stack persistent: an immutable linked list where every push or pop creates a new version that shares structure with the old one, so each version costs O(1) time and space. Or store periodic snapshots plus operation logs for quick restore. Persistent stacks are the most elegant, because a linked-list stack is naturally persistent: a version is just a pointer to its top node.

Read full answer

Applies toundo and time-travel debugging, versioned data structures, auditing, functional programming (Clojure, Haskell, Scala), and interview design questions

Approach 1: Operation Log

class LoggedStack:
    def __init__(self):
        self.items, self.log = [], []

    def push(self, x):
        self.items.append(x)
        self.log.append(("push", x))

    def pop(self):
        x = self.items.pop()
        self.log.append(("pop", x))      # record the value for audit and undo
        return x

    def state_at(self, version):
        """Replay the first `version` operations."""
        s = []
        for op, x in self.log[:version]:
            if op == "push":
                s.append(x)
            else:
                s.pop()
        return s

ls = LoggedStack()
ls.push(1); ls.push(2); ls.pop(); ls.push(3)
print(ls.log)            # [('push', 1), ('push', 2), ('pop', 2), ('push', 3)]
print(ls.state_at(2))    # [1, 2]

Replay costs O(k) for version k; add periodic snapshots to cap the replay length.

Approach 2: Persistent (Immutable) Stack

class Node:
    __slots__ = ("value", "next", "size")
    def __init__(self, value, next):
        self.value, self.next = value, next
        self.size = 1 + (next.size if next else 0)

class PersistentStack:
    def __init__(self):
        self.versions = [None]           # version 0: empty stack

    def push(self, version, x):
        self.versions.append(Node(x, self.versions[version]))
        return len(self.versions) - 1

    def pop(self, version):
        top = self.versions[version]
        if top is None:
            raise IndexError("pop from empty stack")
        self.versions.append(top.next)   # reuse the rest of the list
        return top.value, len(self.versions) - 1

    def to_list(self, version):
        out, node = [], self.versions[version]
        while node:
            out.append(node.value)
            node = node.next
        return out[::-1]                 # bottom to top

ps = PersistentStack()
v1 = ps.push(0, "a")
v2 = ps.push(v1, "b")
val, v3 = ps.pop(v2)
v4 = ps.push(v3, "c")
v5 = ps.push(v2, "x")                    # branch from an older version
print(ps.to_list(v2), ps.to_list(v4), ps.to_list(v5))
# ['a', 'b'] ['a', 'c'] ['a', 'b', 'x']

Versions v4 and v5 share the node for "a"; nothing is copied. You can even branch from old versions, like a version-control tree.

Approach 3: Snapshots Plus Log

  • Store a full snapshot every k operations and log operations between snapshots.

  • Restoring version v: load the nearest earlier snapshot and replay at most k operations.

  • Common in databases and event-sourced systems.

Comparison

Approach Push/pop cost Access version v Extra space Notes
Operation log O(1) O(v) replay O(operations) Simple; great for auditing
Persistent stack O(1) O(1) to get the top, O(size) to list O(operations) nodes Versions share structure; supports branching
Snapshots plus log O(1) amortised O(k) replay O(n / k) snapshots Bounded restore time
Full copy per operation O(n) O(1) O(n x operations) Wasteful; avoid

Practical Considerations

  • Memory limits: cap history, compress old entries, or move them to disk.

  • Auditing: add timestamps and user IDs to logged operations.

  • Concurrency: immutable versions can be read safely by many threads without locks.

Interview Tip

Present the three approaches with their trade-offs, and highlight that a linked-list stack is naturally persistent because push and pop create new versions sharing the old nodes. Showing a branch from an older version makes the idea concrete.

41

How would you monitor a stack's capacity thresholds?

To monitor a stack’s capacity, instrument its size: track the current depth, the high-water mark (maximum depth seen), and operation rates, and compare them against configured thresholds (for example a warning at 70 percent of capacity and a critical alert at 90 percent). When thresholds are crossed, emit metrics and alerts, and optionally act automatically: apply backpressure to producers, reject or shed new pushes, or grow capacity. Use hysteresis so alerts do not flap, and export the metrics to a monitoring system (Prometheus, CloudWatch) for dashboards and trend analysis. For call stacks, the same idea appears as stack high-water marks in embedded systems.

Read full answer

Applies tobounded stacks and buffers in services, task schedulers, undo histories, embedded and RTOS task stacks, and resource pools

Design

Component Purpose
Capacity limit Maximum allowed size
Current size gauge Instant view of usage
High-water mark Peak usage since start or since the last reset
Thresholds with hysteresis Warn at 70 percent, clear below 60 percent; critical at 90 percent
Rate counters Pushes and pops per second; rejected pushes
Actions Alert, apply backpressure, shed load, scale

Implementation in Python

class MonitoredStack:
    def __init__(self, capacity, warn=0.7, critical=0.9, clear=0.6, on_event=print):
        self.items, self.capacity = [], capacity
        self.warn, self.critical, self.clear = warn, critical, clear
        self.level = "ok"
        self.high_water = 0
        self.rejected = 0
        self.on_event = on_event

    def _check(self):
        usage = len(self.items) / self.capacity
        self.high_water = max(self.high_water, len(self.items))
        new_level = self.level
        if usage >= self.critical:
            new_level = "critical"
        elif usage >= self.warn:
            new_level = "warning"
        elif usage < self.clear:
            new_level = "ok"                               # hysteresis: clear only below 60 percent
        if new_level != self.level:
            self.level = new_level
            self.on_event(f"{new_level}: {len(self.items)}/{self.capacity}")

    def push(self, x):
        if len(self.items) >= self.capacity:
            self.rejected += 1                             # backpressure signal
            return False
        self.items.append(x)
        self._check()
        return True

    def pop(self):
        x = self.items.pop()
        self._check()
        return x

s = MonitoredStack(capacity=10)
for i in range(11):
    s.push(i)
for _ in range(6):
    s.pop()
print("high water:", s.high_water, "rejected:", s.rejected, "level:", s.level)
# warning: 7/10
# critical: 9/10
# warning: 8/10
# ok: 5/10
# high water: 10 rejected: 1 level: ok

Between 60 and 70 percent nothing changes: once warned, the level returns to ok only below 60 percent, which prevents flapping when usage hovers around a threshold.

Exporting Metrics

# With prometheus_client (pip install prometheus-client)
from prometheus_client import Counter, Gauge

stack_size = Gauge("work_stack_size", "Current items in the work stack")
stack_capacity = Gauge("work_stack_capacity", "Configured capacity")
rejected_pushes = Counter("work_stack_rejected_total", "Pushes rejected because the stack was full")

Alert rules can then use expressions like work_stack_size / work_stack_capacity > 0.9 for 5m, and dashboards show trends and high-water marks.

Automatic Responses

  • Backpressure: block or slow producers when near capacity.

  • Load shedding: reject low-priority pushes first.

  • Scaling: add consumers or workers when depth stays high.

  • Trimming: for histories (like undo), drop the oldest entries.

Call Stacks in Embedded Systems

  • Stack painting: fill a task’s stack with a known pattern at start; the untouched area shows the high-water mark.

  • FreeRTOS provides uxTaskGetStackHighWaterMark() and an overflow hook (configCHECK_FOR_STACK_OVERFLOW).

  • Alert or log when headroom falls below a margin, and size stacks from measured peaks.

Interview Tip

Describe the metrics (size, high-water mark, rejections), thresholds with hysteresis, export to a monitoring system, and automatic actions like backpressure. Mentioning embedded stack high-water marks shows you can apply the idea to call stacks as well as data structures.

42

How is a stack trace used in debugging and exception handling?

A stack trace is a snapshot of the call stack at the moment an exception or error occurred: the chain of function calls, files and line numbers that led to it, usually listed from the outermost call to the failing one (Python) or the reverse (Java). In debugging, it shows where the failure happened and how the program got there, which narrows the search to specific code paths. In exception handling, programs log the trace with context, preserve the original cause when wrapping exceptions, and send traces to error-tracking tools so production issues can be diagnosed without reproducing them.

Read full answer

Applies toPython tracebacks, Java and Kotlin exceptions, JavaScript `Error.stack`, .NET, Go panics, and crash reports for native code (C, C++, Rust)

Reading a Python Traceback

import traceback

def parse_price(text):
    return float(text)

def total(items):
    return sum(parse_price(i["price"]) for i in items)

try:
    total([{"price": "9.99"}, {"price": "n/a"}])
except ValueError:
    lines = traceback.format_exc().strip().splitlines()
    print(lines[0])
    print(lines[-1])
# Traceback (most recent call last):
# ValueError: could not convert string to float: 'n/a'

The full traceback lists each frame (total, the generator expression, parse_price) with file and line number, ending with the exception type and message. Read it bottom-up to find the failing line, then upward to see which caller passed the bad data.

Java Example

java.lang.NullPointerException: Cannot invoke "String.length()" because "name" is null
    at com.shop.UserService.validate(UserService.java:42)
    at com.shop.UserController.create(UserController.java:18)
    ...
Caused by: ...

The top frame is where the exception was thrown; Caused by sections show wrapped original exceptions.

Using Stack Traces Effectively

Practice Why
Find the first frame in your own code Library frames often just report the symptom
Read the exception message and type Often names the bad value or null variable
Follow the call chain Shows which caller supplied bad input
Check “Caused by” / chained exceptions The root cause is often the innermost one
Compare with recent changes Line numbers point to code changed in a deploy

Exception Handling Best Practices

  • Log with the trace: logger.exception("failed to create order") in Python logs the message and traceback; in Java, pass the exception object to the logger.

  • Chain exceptions to keep the root cause: raise OrderError("cannot price order") from err in Python, new ServiceException("...", cause) in Java.

  • Do not swallow exceptions (except: pass) or log only the message; the trace is the most valuable part.

  • Add context: request ID, user ID, input identifiers (not secrets or personal data).

  • Do not show traces to end users: they reveal internal details and help attackers. Return a generic error with a correlation ID and log the trace server-side.

  • Use error-tracking tools (Sentry, Rollbar, Datadog, Google Cloud Error Reporting) that group traces, count occurrences and link them to releases.

Special Cases

Situation How to get useful traces
Asynchronous code Async-aware traces (Python asyncio tracebacks, Node.js async stack traces), plus correlation IDs
Native crashes Core dumps, symbol files, addr2line, debuggers (gdb, lldb) to symbolicate addresses
Minified JavaScript Source maps to map back to original code
Optimised builds Inlining may hide frames; keep debug symbols separately
Distributed systems Combine stack traces with distributed tracing (OpenTelemetry) across services

Interview Tip

Explain that a stack trace records the call path at the failure point, show how to read one to find the failing line and its caller, and cover handling practices: log with context, chain exceptions, never swallow them, and hide traces from users. Mentioning source maps and error-tracking tools shows production experience.

43

How do you handle stack overflow in memory-constrained environments?

In memory-constrained environments, you handle stack overflow in three layers: prevent it (bounded recursion, iterative algorithms, small frames, stack sizes based on measured worst case), detect it early (guard pages, stack canaries, stack painting with high-water marks, MPU or hardware stack-limit registers), and recover safely when it happens (catch it where the runtime allows, run handlers on a separate stack, then reset or restart the task or device in a known state). On microcontrollers, an overflow usually corrupts memory silently, so detection plus a controlled reset is safer than trying to continue.

Read full answer

Applies toembedded C and C++ on microcontrollers (ARM Cortex-M), RTOS tasks (FreeRTOS, Zephyr), Linux processes, and managed runtimes (Java `StackOverflowError`, Python `RecursionError`, .NET)

Prevention

Technique Detail
Avoid or bound recursion Use loops with explicit stacks; enforce maximum depth
Small frames No large local arrays; pass structs by pointer; avoid alloca and variable-length arrays
Static stack analysis GCC -fstack-usage and -Wstack-usage=N, call-graph tools to compute worst-case depth
Size stacks from measurements Use high-water marks under worst-case tests, plus a safety margin
Separate interrupt stacks Cortex-M uses the main stack (MSP) for exceptions and the process stack (PSP) for tasks
Coding standards MISRA C discourages recursion in safety-critical code

Detection

Mechanism How it works
Guard pages (MMU systems) An unmapped page below the stack causes a fault on overflow
MPU regions (microcontrollers) A small no-access region at the stack limit triggers a MemManage fault
Stack limit registers ARMv8-M PSPLIM and MSPLIM fault when the stack pointer goes past the limit
Stack painting Fill the stack with a pattern (such as 0xA5) and check how much was overwritten
RTOS checks FreeRTOS configCHECK_FOR_STACK_OVERFLOW calls vApplicationStackOverflowHook; Zephyr has stack sentinels and hardware stack protection
Compiler canaries -fstack-protector detects buffer overruns that smash the frame
/* FreeRTOS: called when a task's stack overflow is detected */
void vApplicationStackOverflowHook(TaskHandle_t task, char *name) {
    log_fault("stack overflow", name);   /* store in no-init RAM or flash for later analysis */
    NVIC_SystemReset();                  /* controlled reset into a known-good state */
}

Recovery

  • Microcontrollers: log the fault (task name, stack pointer, program counter) to persistent memory, then reset. A watchdog timer guarantees a reset if the system hangs.

  • Linux native programs: a SIGSEGV handler can run only on an alternate signal stack (sigaltstack), because the normal stack is exhausted. It should log and exit; continuing is unsafe.

  • Java: StackOverflowError can be caught, but only near the entry point to abandon the operation. Prefer fixing the recursion or running the work in a thread with a larger stack.

  • Python: RecursionError is raised at the recursion limit (about 1,000 by default), before the C stack overflows. Catch it to reject the input, or rewrite the code iteratively.

def depth(obj):
    if isinstance(obj, list):
        return 1 + max((depth(x) for x in obj), default=0)
    return 0

nested = []
cur = nested
for _ in range(5000):
    cur.append([]); cur = cur[0]

try:
    depth(nested)
except RecursionError:
    print("input too deeply nested; rejected")   # input too deeply nested; rejected

Design for Graceful Degradation

  • Validate input depth at boundaries (JSON parsers often limit nesting).

  • Fallback algorithms: switch from recursive to iterative processing beyond a depth.

  • Isolate risky work in a separate task or process with its own stack, so an overflow restarts only that component.

  • Watchdog and health checks to restart hung components.

Interview Tip

Organise the answer as prevent, detect and recover, giving embedded-specific tools (MPU guards, stack limit registers, FreeRTOS hooks, watchdogs) and runtime-specific behaviour (Java StackOverflowError, Python RecursionError, sigaltstack). Stressing that a controlled reset is safer than continuing after corruption shows embedded experience.

44

How do you normalise a Unix pathname using a stack?

To normalise (simplify) a Unix path, split it on / and process each part with a stack of directory names. Skip empty parts and . (they mean “current directory”), pop on .. (go to the parent, if there is one), and push any other name. Finally, join the stack with / and prefix a leading / for absolute paths. This handles repeated slashes, trailing slashes, . and .. in O(n) time.

Read full answer

Applies tofile systems and shells, web servers and URL routers, build tools; LeetCode 71 "Simplify Path"

Rules

Part Action
Empty string (from // or a trailing /) Skip
. Skip
.. Pop if the stack is non-empty (for absolute paths, .. at the root stays at the root)
Any other name Push

Implementation in Python

def simplify_path(path):
    stack = []
    for part in path.split("/"):
        if part in ("", "."):
            continue
        if part == "..":
            if stack:
                stack.pop()
        else:
            stack.append(part)
    return "/" + "/".join(stack)

tests = ["/home/", "/../", "/home//foo/", "/a/./b/../../c/", "/a/b/c/../../../..", "/.../a/../b/"]
for t in tests:
    print(f"{t!r:24} -> {simplify_path(t)!r}")
# '/home/'                 -> '/home'
# '/../'                   -> '/'
# '/home//foo/'            -> '/home/foo'
# '/a/./b/../../c/'        -> '/c'
# '/a/b/c/../../../..'     -> '/'
# '/.../a/../b/'           -> '/.../b'

... is an ordinary directory name, not a special token.

Trace for /a/./b/../../c/

Part Action Stack
a push a
. skip a
b push a b
.. pop a
.. pop (empty)
c push c

Result: /c.

Relative Paths

For relative paths, a .. that cannot be popped must be kept, because it refers to a directory above the starting point:

def normalize_relative(path):
    stack = []
    for part in path.split("/"):
        if part in ("", "."):
            continue
        if part == "..":
            if stack and stack[-1] != "..":
                stack.pop()
            else:
                stack.append("..")
        else:
            stack.append(part)
    return "/".join(stack) or "."

print(normalize_relative("../a/./b/../../c"), normalize_relative("a/.."))   # ../c .

Complexity

  • Time: O(n) for a path of length n (split, one pass, join).

  • Space: O(n) for the parts and stack.

Real-World Notes

  • Symbolic links: purely textual normalisation can differ from the real file system (a/link/.. may not equal a if link points elsewhere). Python’s os.path.normpath is textual; os.path.realpath and pathlib.Path.resolve() follow symlinks.

  • Security: normalise before checking that a requested file stays inside an allowed directory, to block path traversal like /static/../../etc/passwd. Also decode URL-encoded sequences such as %2e%2e first.

  • POSIX detail: a path beginning with exactly two slashes (//) may have implementation-defined meaning; most simplification exercises treat it as /.

Interview Tip

State the rules (skip empty and ., pop on .., push names), trace an example, and give O(n) complexity. Mentioning relative-path handling, symlinks, and the path-traversal security use shows you understand where the algorithm matters in practice.

45

How do you find the next greater element for each item using a stack?

The next greater element (NGE) of each item is the first element to its right that is strictly larger, or -1 if none exists. A monotonic decreasing stack of indices solves it in O(n): scan left to right; while the current value is greater than the value at the index on top, pop that index and record the current value as its answer; then push the current index. Indices still on the stack at the end have no greater element. Each element is pushed once and popped at most once, which gives linear time.

Read full answer

Applies tomonotonic-stack problems (LeetCode 496, 503 and 739 "Daily Temperatures"), stock and time-series analysis, histogram problems

Implementation in Python

def next_greater(nums):
    result = [-1] * len(nums)
    stack = []                                  # indices whose next greater is unknown
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            result[stack.pop()] = x
        stack.append(i)
    return result

print(next_greater([4, 5, 2, 25]))          # [5, 25, 25, -1]
print(next_greater([13, 7, 6, 12]))         # [-1, 12, 12, -1]
print(next_greater([2, 1, 2, 4, 3]))        # [4, 2, 4, -1, -1]

Trace for [13, 7, 6, 12]

i Value Pops (index: answer) Stack after (values)
0 13 none 13
1 7 none 13 7
2 6 none 13 7 6
3 12 2: 12, 1: 12 13 12
end 0 and 3 stay -1

The stack always holds values in decreasing order from bottom to top, waiting for something larger.

Why It Is O(n)

Each index enters the stack once and leaves it at most once, so the total number of pops across the whole loop is at most n. The time is O(n) and the space is O(n).

Common Variants

Circular array (LeetCode 503): iterate twice over the indices with i % n, pushing only during the first pass.

def next_greater_circular(nums):
    n = len(nums)
    result, stack = [-1] * n, []
    for i in range(2 * n):
        x = nums[i % n]
        while stack and nums[stack[-1]] < x:
            result[stack.pop()] = x
        if i < n:
            stack.append(i)
    return result

print(next_greater_circular([1, 2, 1]))     # [2, -1, 2]

Distance to the next greater element (Daily Temperatures): store i - popped_index instead of the value.

def daily_temperatures(t):
    ans, stack = [0] * len(t), []
    for i, temp in enumerate(t):
        while stack and t[stack[-1]] < temp:
            j = stack.pop()
            ans[j] = i - j
        stack.append(i)
    return ans

print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))   # [1, 1, 4, 2, 1, 1, 0, 0]

Other directions and comparisons

Problem Change
Next smaller element Use an increasing stack (pop while top > current)
Previous greater element After popping smaller values, the remaining top is the answer for the current element
Next greater or equal Pop while top <= current
NGE for a subset (LeetCode 496) Compute NGE for the larger array once; store answers in a dict

Naive Approach for Comparison

Scanning right from each element is O(n^2) in the worst case (for example a strictly decreasing array).

Interview Tip

Explain the decreasing stack of unresolved indices, show that a larger value resolves them by popping, and justify O(n) with the push-once, pop-once argument. Offering the circular and Daily Temperatures variants shows you can adapt the pattern.

46

How do you detect a cycle in a directed graph using stack-based DFS?

A directed graph has a cycle exactly when depth-first search finds a back edge: an edge to a node that is still on the current DFS path. Track three states per node: unvisited (white), on the current path (grey) and finished (black). With an explicit stack, push a node and mark it grey, then walk its neighbours one at a time. If a neighbour is grey, you found a cycle. When all of a node’s neighbours are processed, mark it black and pop it. Visiting every node and edge once gives O(V + E) time, and the explicit stack avoids recursion limits on large graphs.

Read full answer

Applies todependency resolution (build systems, package managers), deadlock detection (wait-for graphs), task schedulers and DAG validation (Airflow, CI pipelines), and course-schedule style problems (LeetCode 207)

Why Grey Matters

Reaching an already black node is not a cycle: that node’s subtree is finished and does not lead back to the current path. Only reaching a grey node (an ancestor on the current path) closes a loop. A single “visited” flag is not enough in directed graphs.

Iterative Implementation in Python

WHITE, GREY, BLACK = 0, 1, 2

def find_cycle(graph):
    """graph: dict node -> list of neighbours. Returns a cycle as a list, or None."""
    color = {u: WHITE for u in graph}
    parent = {}
    for start in graph:
        if color[start] != WHITE:
            continue
        stack = [(start, iter(graph[start]))]       # (node, iterator over neighbours)
        color[start] = GREY
        while stack:
            node, neighbours = stack[-1]
            nxt = next(neighbours, None)
            if nxt is None:
                color[node] = BLACK                   # all neighbours done
                stack.pop()
            elif color.get(nxt, WHITE) == GREY:       # back edge: cycle found
                cycle, cur = [nxt], node
                while cur != nxt:
                    cycle.append(cur)
                    cur = parent[cur]
                cycle.append(nxt)
                return cycle[::-1]
            elif color.get(nxt, WHITE) == WHITE:
                color[nxt] = GREY
                parent[nxt] = node
                stack.append((nxt, iter(graph.get(nxt, []))))
    return None

dag = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": []}
cyclic = {"a": ["b"], "b": ["c"], "c": ["d"], "d": ["b"]}
print(find_cycle(dag))       # None
print(find_cycle(cyclic))    # ['b', 'c', 'd', 'b']

Keeping a neighbour iterator on the stack is what lets the iterative version know when a node is finished, which is when it turns black. A simpler “pop and push all neighbours” DFS loses that information and cannot detect cycles correctly.

Trace on the Cyclic Graph

Step Stack (path) Event
1 a a grey
2 a b b grey
3 a b c c grey
4 a b c d d grey
5 a b c d d -> b, and b is grey: cycle b, c, d, b

Complexity

  • Time: O(V + E), each node and edge processed once.

  • Space: O(V) for colours, parents and the stack.

Alternative: Kahn’s Algorithm (Topological Sort)

Repeatedly remove nodes with in-degree 0. If some nodes are never removed, the graph has a cycle. It uses a queue instead of DFS and also produces a topological order.

from collections import deque

def has_cycle_kahn(graph):
    indeg = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            indeg[v] += 1
    q = deque(u for u, d in indeg.items() if d == 0)
    seen = 0
    while q:
        u = q.popleft(); seen += 1
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return seen != len(graph)

dag = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": []}
cyclic = {"a": ["b"], "b": ["c"], "c": ["d"], "d": ["b"]}
print(has_cycle_kahn(dag), has_cycle_kahn(cyclic))   # False True

Undirected Graphs Are Different

In an undirected graph, a cycle is any edge to a visited node other than the parent; three colours are not needed. Union-find is another option.

Interview Tip

Explain the white, grey and black states and why only a grey neighbour means a cycle, show the iterative DFS with neighbour iterators on the stack, and give O(V + E). Mentioning Kahn’s algorithm as an alternative and returning the actual cycle path shows depth.

Sign in to keep reading

You've opened 2 full answers. Sign in to read all 46 Stacks answers, mark what you know and pick up where you left off.

Report a mistake

What's wrong?

All Data Structures & Algorithms subjects