Question 1

What is a stack and what operations does it have?

Accepted Answer

Start with the definition: a stack is an abstract data type following LIFO (Last In, First Out) — the last element pushed is the first popped. The stack-of-plates analogy makes it click immediately. List the operations with their complexity — stating complexity is expected: push(x) O(1), pop() O(1), peek() O(1), isEmpty() O(1), size O(1). Then note the two implementations: over an array (the practical default — cache-friendly) and over a linked list (never reallocates). Both give O(1) core operations. The strongest part is answering why use a stack at all: an array could do everything anyway, but a stack states the intent and makes misuse impossible — removing from the middle simply isn't in the interface. Close with real examples: the call stack, undo, bracket matching, DFS.

Question 2

Explain the algorithm that checks whether brackets are balanced.

Accepted Answer

Start by answering why a stack: the rule for brackets is "the most recently opened must be closed first" — that is exactly LIFO, so a stack fits naturally. The algorithm: Walk the string once On an opening bracket ((, [, {), push it On a closing bracket: first, if the stack is empty return false (an extra closer); then pop and check the types match — if not, false After the loop, return stack.isEmpty() — leftover openers mean false Complexity: O(n) time, O(n) space in the worst case (every character an opener). List the edge cases out loud — the most valuable part of the answer: empty string (true), only openers "(((" (false, caught by the final check), only closers ")))" (false, caught by the empty-stack check), wrong pairing "([)]" (false), and non-bracket characters (ignored). Finish with the extension: real linters use the same technique for HTML tags, quotes and code blocks; and to produce a useful error message you store the bracket's position on the stack alongside the bracket itself.

Question 3

What's the difference between implementing a stack over an array vs a linked list? Which would you pick?

Accepted Answer

Say up front that the core operations are O(1) in both — the difference isn't complexity but practical properties. That framing makes the answer strong. Array-based: push amortized O(1) (an O(n) copy when capacity fills), pop/peek O(1) Dense memory — no per-element metadata Good cache locality — noticeably faster in practice Downside: an O(n) pause at growth points, and some wasted unused capacity Linked-list based: Guaranteed O(1) on every operation — never a copy pause An extra pointer of memory per node Poor cache locality Every push allocates an object — GC pressure The choice: "By default I pick the array-based one — Array in JS, ArrayDeque in Kotlin, List in Dart. Cache locality and simplicity almost always win. I'd choose a linked list only when every operation must be guaranteed O(1) (a real-time system where a copy pause is unacceptable) or when elements are very large." One extra nuance: in Java/Kotlin avoid java.util.Stack — it is legacy, extends Vector and synchronises on every operation; ArrayDeque is faster. Knowing that detail signals experience.

Question 4

What is the relationship between the call stack and the stack data structure?

Accepted Answer

State the relationship directly: the call stack is the stack data structure — it's just managed by the runtime rather than by your program. How it works: on a call, a frame is pushed (parameters, locals, return address); on return, the frame is popped. The most recently called function returns first — pure LIFO. List the consequences — this is what makes the answer valuable: Stack traces print in LIFO order: the top line is the most recent call, and going down you walk toward the callers. Knowing that matters when debugging. Stack overflow — pushes accumulating without pops; since the stack is bounded (a few MB), deep recursion fills it. Recursion's space complexity equals its depth, because the frames coexist on the stack. Every recursion can be written iteratively — you replace the call stack with an explicit heap stack. The recursive and iterative DFS are literally two faces of the same algorithm. Tail call optimisation — if the recursive call is the last operation, the frame can be reused; Kotlin does this with tailrec, most JS runtimes and Dart do not. End with the practical takeaway: "For algorithms whose depth depends on the input, I write them iteratively with an explicit stack — then the limit is the size of the heap, not the call stack's few megabytes."

Question 5

How would you keep two stacks in one array? Or build a queue from two stacks?

Accepted Answer

These are classic "structure design" questions, so explaining the idea clearly matters more than writing the code. Two stacks in one array: grow one from the start (index 0 rightwards) and the other from the end (last index leftwards). Fullness is the condition top1 + 1 == top2. The advantage is dynamic sharing — one can occupy far more space than the other, whereas splitting the array down the middle would leave one half idle while the other overflowed. All operations O(1). A queue from two stacks: keep an inbox and an outbox. enqueue(x): push onto inbox — O(1) dequeue(): if outbox is empty, move everything from inbox into outbox (which reverses the order and yields FIFO), then pop from outbox The complexity analysis is the real point of the question: a single dequeue can be O(n) in the worst case, but each element is moved exactly once in its lifetime, so dequeue is amortized O(1). Articulating that amortized argument correctly is the most important part of the answer. There's a mirror question too — a stack from two queues: possible, but either push or pop becomes O(n); it's less efficient than the reverse, and saying so shows comparative judgement. Add the practical note: in real code I'd use a ready-made ArrayDeque/Queue for FIFO; these constructions are mostly interview exercises testing whether you can reason with restricted primitives.

Criterion	Array-based	Linked-list based
push	amortized O(1) — append at the end	O(1) — insert at the head
pop / peek	O(1) — from the end	O(1) — from the head
Memory	Dense; unused capacity can be wasted	An extra pointer per node
Growth	An O(n) copy when capacity fills (rare)	No copying at all
Cache locality	Good — faster in practice	Poor
Size limit	Bounded by memory	Bounded by memory
Practical choice	Default — JS `Array`, Kotlin `ArrayDeque`, Dart `List`	Only for special requirements

Stack (LIFO)

📚 Sources and documentation