Algorithms from zero
Lists, stacks, queues: multiple-choice review
Crux Multiple-choice synthesis across the unit: linked-list cost model, pointer manipulation, LIFO/FIFO discipline, deque implementation, and the monotonic-stack amortized argument.
Your altitude — climbing toward senior
ZeroJuniorMiddleSenior
You are at middle altitude — in the skySix questions that cut across the whole unit. Each one is a decision an interviewer pushes on — not a definition to recite, but a cost model to defend and an implementation choice to justify.
Goal
Confirm you can connect the memory layout of a linked list to its cost model, reason about pointer manipulation without losing nodes, pick the right LIFO/FIFO discipline for a problem, and explain why a monotonic stack is linear despite its inner loop.
Quiz
Completed
A workload pushes at the head 10,000 times and then reads by index 100 times at random positions. You must pick array vs singly linked list. Which is faster overall, and why?
Heads-up Arrays win only on indexing and cache locality. Here the workload is insert-heavy at the head, which is exactly the linked list's O(1) strength versus the array's O(n) shift.
Heads-up Both support the operations, but the costs differ by an order of magnitude: the array pays O(n) per head insert, the linked list pays O(1). The dominant cost is the 10k head inserts.
Heads-up The conclusion is right but the reason is wrong. Index access on a linked list is O(n) — no address formula, you must hop pointers. The linked list wins on the head inserts, not on indexing.
Quiz
Completed
You are writing in-place reversal of a singly linked list. A colleague writes current.next = prev; current = current.next; inside the loop. What breaks?
Heads-up The standard loop saves the successor first: const next = current.next; current.next = prev; prev = current; current = next;. Skipping the save corrupts the traversal because you overwrote the pointer you needed.
Heads-up There is no leak — the GC reclaims unreachable nodes. The bug is a logic error: the traversal moves the wrong direction because the successor pointer was destroyed before being saved.
Heads-up It fails on every non-trivial list. As soon as you overwrite current.next and then read it, you follow the reversed pointer back to prev instead of advancing.
Quiz
Completed
You repeatedly insert and delete at the head of a singly linked list and keep hitting null-pointer special cases for the empty-list and head positions. What is the cleanest structural fix?
Heads-up A back pointer helps with O(1) predecessor access, but it does not remove the head/empty special cases — you still branch on whether head is null. The sentinel removes the branch by guaranteeing a predecessor.
Heads-up Swallowing the error hides the bug, it does not fix the logic. The structural fix is a sentinel node so the previous-node reference is always valid.
Heads-up A count does not unify the code paths for head versus middle operations. The sentinel is what makes 'insert at head' identical to 'insert in the middle.'
Quiz
Completed
You are validating nested brackets in a config parser, and separately you are doing a level-order (breadth-first) walk of a tree. Which structures fit, and why?
Heads-up A stack on the tree gives depth-first, not level-order. Level-order requires FIFO so that a node's children wait behind all nodes already enqueued at the current level — that is a queue.
Heads-up A queue on brackets would pop the oldest open bracket first, the reverse of nesting. Bracket matching needs the most-recent-first discipline of a stack.
Heads-up Exactly backward. Nesting is last-opened-first-closed (stack); breadth-first is arrival-order (queue). Swapping them gives the wrong traversal and wrong validation.
Quiz
Completed
You implement a FIFO queue on a JavaScript array using push to enqueue and shift to dequeue. Under a sustained stream of N enqueue+dequeue pairs, what is the total cost and the fix?
Heads-up push is amortized O(1), but shift is O(n): removing index 0 forces every later element down one slot. N dequeues over a growing array sum to O(N^2).
Heads-up There is nothing logarithmic here. shift is linear in the array length, and summing linear costs over N operations yields quadratic, not N log N.
Heads-up A proper deque (doubly linked list or circular buffer) is O(1) at both ends, but an array with shift is not that — shift still reindexes. The point is to stop using shift.
Quiz
Completed
A monotonic-stack solution to next-greater-element has a while loop inside a for loop, yet it is O(n), not O(n^2). What is the precise argument?
Heads-up The inner loop can pop many elements in a single outer step (a tall element clears a long run). It is not constant per step — the bound is global: every element is popped at most once over the whole run.
Heads-up Nothing is sorted; the stack maintains a monotonic subset internally. The linear bound comes from each element entering and leaving the stack once, not from sorting.
Heads-up There is no halving. Every element is visited; the efficiency comes from the push-once/pop-once invariant, which caps total stack operations at 2n.
Recap
The through-line of the unit is one cost model and three disciplines. Memory layout sets the cost: contiguity buys O(1) indexing, scattering buys O(1) head insertion — you choose based on the dominant operation. Pointer manipulation is about saving links before you overwrite them and using a sentinel to erase head special cases. The stack (LIFO) and queue (FIFO) are disciplines, not data structures: pick by whether you need most-recent-first or arrival-order, and never dequeue with shift. The monotonic stack is the payoff — a stack plus an ordering invariant turns an O(n^2) scan into O(n) by the push-once/pop-once amortized argument.