Stage 1 · Code
Interview Synthesis
Explain, Implement & Verify
Practice the full interview loop: clarify, baseline, invariant, Go implementation, edge tests, complexity, and follow-up.
The Seven-Step Interview Loop
A strong interview solution is a sequence of checkable decisions. Correct code matters, but the interviewer also needs to see that you can remove ambiguity, compare trade-offs, preserve an invariant, and verify the result without relying on the judge. Use the same loop on every problem until it becomes automatic.
- Clarify: restate the contract and ask about bounds, ordering, duplicates, mutation, overflow, and the required result when no answer exists.
- Brute force: give the simplest correct approach, its complexity, and why it becomes too expensive.
- Invariant: state what remains true after each iteration or recursive return and why that state is sufficient.
- Code: implement in small phases whose names mirror the explanation; keep boundary conventions explicit.
- Edge tests: trace empty or minimum input, a normal case, and a case that stresses the invariant.
- Complexity: count how often each item enters, leaves, or is revisited; include auxiliary and output space.
- Follow-up: identify which assumption powered the optimization and explain what changes when the assumption changes.
Say “I shrink until the window is valid, and each left endpoint is removed once,” not “now I increment left.” The first sentence exposes the proof and the amortized complexity; the second only describes syntax.
Concrete Go Walkthrough
Prompt: given an array of positive integers and a positive target, return the minimum length of a contiguous subarray whose sum is at least target. Return 0 if no such subarray exists.
| Step | What to say |
|---|---|
| Clarify | Values are strictly positive; the result is a length; input may be empty; no solution returns 0; int arithmetic is sufficient for the stated bounds. |
| Brute force | Start at every left index, extend right until the target is reached, and track the shortest length. That is O(n²) time and O(1) space. |
| Invariant | Before each right expansion, sum equals nums[left..right-1]. While sum is at least target, the current window is valid and removing its positive left value is the only way to test a shorter window ending at right. |
| Pattern | A dynamic sliding window is valid because all values are positive: expanding cannot decrease sum and shrinking cannot increase it. |
Trace target = 7 and nums = [2,3,1,2,4,3]. When right reaches the second 2, the sum is 8 and the window [2,3,1,2] is valid; shrinking records length 4. At value 4, shrinking finds [1,2,4] with length 3. At the final 3, the window [4,3] reaches 7 and produces the optimum length 2.
Verify Before You Declare Done
Testing should target assumptions and transitions, not just produce several random examples. For this solution, the dangerous points are entering the valid state, shrinking past it, handling no solution, and returning the sentinel correctly.
| Test | Expected | What it checks |
|---|---|---|
| target=7, nums=[2,3,1,2,4,3] | 2 | Multiple valid windows and repeated shrinking |
| target=4, nums=[4] | 1 | A one-element window becomes valid immediately |
| target=8, nums=[1,1,1] | 0 | Sentinel and no-solution contract |
| target=3, nums=[] | 0 | Empty input without indexing |
| target=6, nums=[1,2,3] | 3 | The only valid window uses the full array |
Now state complexity from operations, not from loop nesting: each element enters sum once through right and leaves at most once through left, so time is O(n). The algorithm stores a few integers, so auxiliary space is O(1). The input slice is not copied or mutated.
Applied exercise
Run a verbal verification pass
Implement the same prompt from a blank editor while recording yourself or speaking aloud as if an interviewer were present.
- Spend no more than two minutes clarifying and stating the no-solution behavior.
- Describe the O(n²) baseline before naming sliding window.
- State positivity as the assumption that makes boundary movement monotonic.
- Implement without looking at the walkthrough.
- Trace the single-element, no-solution, and repeated-shrink cases.
- Conclude with time, auxiliary space, and whether the input is mutated.
Deliverable
A compilable Go function plus a seven-line interview transcript—one line for each stage of the loop.
Completion checks
- The invariant names both the exact window represented by sum and why shrinking is safe.
- The implementation returns 0 rather than the sentinel when no window qualifies.
- The complexity explanation accounts for total pointer movement instead of calling the nested loop O(n²).
- The transcript identifies positivity as an assumption rather than an incidental detail.
Handle the Follow-Up
A common follow-up allows negative values. Do not patch the window. Say exactly what broke: after adding a negative value, an invalid window can become valid; after removing a negative left value, sum can increase. Boundary movement is no longer monotonic, so discarded starts may still belong to the optimum.
For the related problem “shortest subarray with sum at least target” and arbitrary integers, use prefix sums with a monotonic deque of candidate prefix indices. Prefix difference gives each subarray sum; increasing prefix values remove dominated candidates from the back, while a large enough difference removes valid starts from the front. The follow-up is a different invariant, not a small edit to the positive-only solution.
When a constraint changes, point to the exact proof step it invalidates. That demonstrates transferable reasoning even if there is not enough time to implement the harder variant.
Why is the nested while loop in minSubarrayLen still part of an O(n) algorithm?
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.