Who is still waiting?

Temperatures [71,69,69,73].

Before 73 arrives, which indices are unresolved? Why keep both equal 69s?

1 / 10

Derive the unresolved order

Future scanning from every day repeats work.

Instead, each arrival resolves the most recent colder questions.

If it cannot resolve the newest question, why can it stop?

2 / 10

Valid Parentheses — predict before coding

The stack stores unmatched openings in nesting order. Counts alone cannot distinguish properly nested brackets from crossing pairs.

Decision: Why is "([)]" invalid despite having one opening and closing of each type?

Presenter notes

Model answer: The ) arrives while [ is the most recent unmatched opening. Counts balance, but the nesting order is wrong.

Correctness argument: After processing a prefix, the stack contains exactly its unmatched opening brackets, oldest to newest. An opening extends that list. A closing bracket must match the most recent unmatched opening: matching an earlier one would cross a still-open pair and violate nesting. Thus an empty stack or wrong top proves invalidity, while popping a matching top preserves the invariant. At the end, an empty stack means every opening and closing participated in a correctly nested matching pair. A nonempty stack witnesses openings with no corresponding close. This establishes necessity and sufficiency, including the valid empty string.

Debugging prompt: Test a leading closer, a trailing opener, mixed nesting, and empty input. Compare bracket types, not just stack length.

3 / 10

Simplify Path — predict before coding

A lexical path stack models directory components. Dot and dot-dot have special meaning only as whole components; names such as ... are ordinary names.

Decision: What does "/a/.../../b//./" simplify to?

Presenter notes

Model answer: "/a/b". The literal directory ... is pushed, then the following .. removes it; repeated slashes and . are ignored.

Correctness argument: After consuming a prefix of path components, the stack represents its canonical route from root. Empty components and a single dot leave the route unchanged. A double dot removes the most recent ordinary component when one exists; at root it has no effect because an absolute path cannot ascend above root. Any other component extends the route by that literal directory name. Each case preserves equivalence under the stated lexical rules. Joining the final components with one slash and adding the initial slash gives a canonical absolute path with neither redundant separators nor a trailing slash except at root.

Debugging prompt: Do not treat every name containing a dot as special. Test attempts to go above root. This function does not access a filesystem, resolve symlinks, or establish security confinement.

4 / 10

Min Stack — predict before coding

The minimum is part of each prefix state. Recording the prefix minimum alongside every pushed value makes popping a duplicate minimum unambiguous.

Decision: After Push(2), Push(1), Push(1), Pop(), what must GetMin return?

Presenter notes

Model answer: 1. One occurrence of the minimum remains; deleting all minimum metadata when one copy is popped would be wrong.

Correctness argument: Maintain equal-length value and minimum stacks, with mins[i] equal to the minimum of values[:i+1]. On push, append the new value and the smaller of it and the previous prefix minimum; this proves the invariant for the extended prefix. On pop, remove one element from each stack, restoring the already-correct metadata for the shorter prefix. Top reads the final value, and GetMin reads the final prefix minimum. Storing a minimum at every depth naturally preserves repeated minima: removing one occurrence reveals the correct minimum at the previous depth.

Debugging prompt: Test duplicate minima, increasing and decreasing sequences, and returning to an empty stack before reuse. Top and GetMin require a nonempty stack; the existing Pop on empty is a no-op.

5 / 10

Evaluate Reverse Polish Notation — predict before coding

The stack contains completed subexpression values whose parent operators have not yet arrived. Operand order is carried by position, not by operator commutativity.

Decision: What does ["7","-3","/"] evaluate to, and why is the result not -3?

Presenter notes

Model answer: -2. Integer division truncates toward zero; mathematical floor of -7/3 would instead be -3.

Correctness argument: For every processed token prefix, the stack lists the values of completed expression fragments in their original left-to-right order. An integer token contributes one new fragment. A binary operator combines the last two fragments: the last popped value is the right operand b and the next is the left operand a, so replace them with a op b. This is exactly the postfix grammar rule, preserving the fragment-value invariant. For a valid complete expression, all fragments eventually combine into one value, which is the answer. Go integer division supplies the specified truncation toward zero when the divisor is nonzero.

Debugging prompt: Use subtraction and negative division to expose operand reversal. Inputs must form a valid expression, have nonzero divisors, and keep parsed/intermediate values within the intended int range; this function is not an error-reporting parser.

6 / 10

Daily Temperatures — predict before coding

The stack holds unresolved days, not temperatures alone. A new warmer day resolves exactly the colder unresolved suffix, with the first such day being the nearest answer.

Decision: For [70,70,71], what are the waiting times?

Presenter notes

Model answer: [2,1,0]. An equal temperature is not warmer, so the first 70 must wait past the second 70.

Correctness argument: Indices on the stack are increasing and their temperatures are non-increasing. Every stacked day has seen no warmer day in the processed suffix. If the current temperature is strictly warmer than the top day, it is the first warmer day for that index, so their index difference is final. Pop and repeat for any earlier colder unresolved days. Remaining days are at least as warm as the current one and remain unresolved. Pushing the current index preserves both orders. At termination, unresolved days have no warmer future day and keep zero. Each index is pushed and popped at most once.

Debugging prompt: Use equal plateaus, strictly descending temperatures, and one final warm spike. Storing temperatures without indices loses the distance needed for the answer.

7 / 10

Largest Rectangle in Histogram — predict before coding

Popping a height means its first strictly lower bar on the right has arrived. The stack reveals how far that height can extend left without crossing a lower barrier.

Decision: For heights [2,2,2], what area must eventually be considered even though equal heights are not popped immediately?

Presenter notes

Model answer: 6. The earliest height-2 representative eventually spans all three bars when the sentinel closes the plateau.

Correctness argument: The stack contains indices with non-decreasing heights. When a lower current height arrives, a popped bar cannot extend through this right boundary. After the pop, the remaining top supplies a left boundary for the rectangle considered, giving width right-left-1, or right when the stack is empty. Every bar between those boundaries is at least the popped height. Equal-height bars can remain stacked; later popping their earliest representative exposes the full plateau width, so no maximal rectangle is lost. Any optimal rectangle has some minimum-height bar and is considered when its right boundary closes. A virtual zero-height sentinel closes all positive-height candidates at the end.

Debugging prompt: Test increasing input so the sentinel must do the work, decreasing input, zeros, and equal plateaus. Width is i-left-1, not i-left. The reference uses a virtual sentinel and does not append to the caller's slice.

8 / 10

Basic Calculator — predict before coding

Parentheses suspend an outer accumulator and its pending sign. When the inner expression finishes, it becomes one signed operand of that suspended context.

Decision: What is the value of "1-(2-(3+4))", and which sign applies to the whole inner expression?

Presenter notes

Model answer: 6. The outer minus applies to the value 2-(3+4)=-5, so 1-(-5)=6; it cannot be applied only to the first inner number.

Correctness argument: Within one nesting level, result is the sum of committed signed operands, num is the decimal value currently being read, and sign applies to that pending operand. A plus or minus commits num and sets the next sign. Opening a parenthesis saves the outer result and sign, then starts an independent inner accumulator. Closing it commits the last inner number and restores outerResult+outerSign*innerResult, exactly substituting the parenthesized value into its context. Spaces do not change state, and the final commit includes the last number. Induction over tokens and nested subexpressions gives the value of a valid expression in the supported grammar.

Debugging prompt: Test multi-digit operands, nested subtraction, and unary minus at expression or parenthesis starts. Preserve the valid-expression grammar; this is not a general parser for multiplication, division, or arbitrary chains of unary operators.

9 / 10

Reconstruct and transfer

Explain strict versus non-strict comparisons for equal temperatures and histogram bars.

Derive rectangle width.

Account for every push and pop once.

10 / 10