Lab 07 — Stuck Recovery

Goal

Train the explicit “stuck protocol” so that when you don’t see the optimal in an interview, you don’t freeze — you systematically work through a checklist that has a high chance of unblocking you within 3 minutes.

Background Concepts

  • The 11-step stuck protocol (see FRAMEWORK.md)
  • The difference between productive struggle and unproductive freeze
  • How to ask for a hint without losing the interview

Interview Context

Every candidate gets stuck. The signal in your favor is how you respond. A candidate who gets stuck and applies a visible recovery protocol is a strong signal. A candidate who gets stuck and goes silent is a weak signal regardless of whether they recover.

Problem Statement

Three problems below are deliberately chosen to be above what you can solve cold without a known pattern. For each:

  1. Apply the 11-step stuck protocol explicitly, narrating each step
  2. Time-cap each step at 60 seconds
  3. If you’ve used 8+ steps without progress, ask for a hint (in this lab, “ask for a hint” means: read the hint section at the bottom)
  4. Continue until solved
  5. Document which step generated the breakthrough

Problems (medium-difficulty, but you don’t have the pattern yet):

  1. Container With Most Water: given heights, find two indices i, j such that min(h[i], h[j]) * (j - i) is maximum.
  2. Longest Palindromic Substring: find the longest palindromic substring of a string.
  3. Search In Rotated Sorted Array: given a sorted array rotated at an unknown pivot, find target in O(log N).

(If you already know all 3 cold, replace with 3 unfamiliar mediums.)

Constraints

Standard. Assume N ≤ 10^5.

Clarifying Questions

For each problem, list 3 you’d ask the interviewer.

Examples

Construct 3 examples for each.

Initial Brute Force

For each problem, write the O(N^2) brute force first.

Brute Force Complexity

State.

Optimization Path — Apply The Stuck Protocol

The 11 steps in order:

  1. Restate the problem. Out loud, in your own words.
  2. Write the brute force. It is correct, even if slow.
  3. Examine the constraints. What does N suggest?
  4. Construct smaller examples. Solve N=2, N=3 by hand.
  5. Look for repeated work. What does the brute force recompute?
  6. Look for sortedness or monotonicity. Could sorting help? Is something monotonic?
  7. Look for symmetry / pattern from a known DS family. Two-pointer? Sliding window? Heap?
  8. Try graph modeling. Some non-graph problems become BFS/DFS when you reframe.
  9. Try a math approach. Closed form? Modular arithmetic? Combinatorial identity?
  10. State the simplest approach you have. Even if not optimal — get it down.
  11. Ask for a nudge. Phrase: “I’ve explored A, B, and C. I think the answer might involve D-family of approaches but I’m not seeing it cleanly. Could you nudge me?”

Final Expected Approach

For each problem, the recovery protocol leads to:

  1. Container With Most Water: Two pointers from both ends, moving the smaller one inward. Step 7 (two-pointer pattern) gets you there. Loop invariant: the optimal answer doesn’t include any pair (L, R) we’ve already discarded.

  2. Longest Palindromic Substring: Either expand-around-center (step 4 — by hand on N=3,4,5 you spot the center idea) or DP (step 5 — repeated work on overlapping substrings). Manacher’s is optimal but step 4/5 is enough.

  3. Search In Rotated Sorted Array: Modified binary search. Step 6 — “is something monotonic?” — at least one half is sorted. Use that to decide which half to recurse into.

Data Structures Used

  • Two pointers (#1)
  • Center expansion / DP table (#2)
  • Modified binary search (#3)

Correctness Argument

For each, the post-recovery solution has a clear correctness argument:

  1. The “moving the smaller one” strategy is correct because moving the larger pointer cannot increase min(h[i], h[j]) (still bounded by the smaller) and reduces width.
  2. Center-expansion enumerates every (center, length) pair exactly once.
  3. The half that is sorted contains target iff target is in [lo, mid] (or [mid, hi]); otherwise recurse on the other half.

Complexity

  1. O(N) time, O(1) space
  2. O(N^2) time (center expansion); Manacher’s is O(N)
  3. O(log N) time, O(1) space

Implementation Requirements

For each problem, after applying the protocol, implement it and run tests. The deliverable is the protocol log + working code.

Tests

  • Smoke: given example
  • Edge: N=0, N=1, N=2
  • Adversarial: all-equal heights (#1), all-same-char string (#2), no rotation (#3 with sorted input)
  • Random: 50 small random inputs vs brute

Follow-up Questions

  • “Why didn’t you see the optimal immediately?” — be honest: “I hadn’t internalized the two-pointer pattern yet” or “I tried sweeping linearly and missed the symmetry.”
  • “What pattern would you check next time?” — internalize the answer.
  • “When would you fail to recognize this in an interview?” — when nervous, or when the problem is wrapped in unfamiliar context.

Product Extension

In production, “stuck on a bug” follows the same shape: restate symptom, find a minimal reproduction, narrow the search, hypothesize cause, verify by experiment, ask a teammate. The protocol generalizes.

Language/Runtime Follow-ups

  • Python: for #2, naive O(N^2) center expansion may TLE on N = 10^5 due to constant factors; consider Manacher’s for full credit
  • Java: String.substring in older versions copies; in newer versions it shares — beware version differences
  • C++: raw character arrays beat std::string for hot loops

Common Bugs

  • Stuck protocol going too fast — you skip step 4 (small examples) and miss the breakthrough that lives there
  • Stuck protocol going too slow — you spend 5 minutes on step 5 instead of moving on
  • Not asking for a hint when 11 steps are exhausted (rare, but happens — pride costs the interview)
  • Asking for a hint too early (before step 6) — looks weak

Debugging Strategy

If your protocol runs took >15 minutes per problem, you spent too long per step. Cap individual steps at 60 seconds; if no progress, move on.

If you finished without a hint, congratulations — but verify that you didn’t already know the pattern, in which case use a different problem.

Deliverable

  1. Per-problem stuck protocol log: for each of the 3 problems, a written record of which step you tried, how long, what you tried, did it advance you?
  2. The breakthrough step annotated.
  3. Working implementation + tests for each problem.
  4. Reflection: which 2 steps are weakest for you? (e.g., many candidates skip step 4 — small examples — because it feels too elementary, but it’s often the highest-yield step.)

Mastery Criteria

  • Solved all 3 problems with explicit protocol use
  • Spent ≤ 15 min per problem (including coding + tests)
  • Identified the breakthrough step accurately
  • Used at most 1 hint across the 3 problems
  • Identified your two weakest protocol steps
  • Re-attempted with the weak steps as starting points and noticed faster progress

Hints (peek only after attempting)

Container With Most Water hint: “Think about what happens at the two extreme ends — and which pointer moving inward could possibly improve the answer.”

Longest Palindrome hint: “Every palindrome has a center. How many possible centers are there?”

Search In Rotated Sorted Array hint: “Even though the full array is rotated, one half across any midpoint must be sorted. Can you tell which half?”