Elite Coding Interview Mastery Program

A complete, lab-based, phase-structured training system to take you from beginner/intermediate to a candidate who can succeed at any coding interview — FAANG, infrastructure companies, distributed systems teams, compilers/runtimes, quant/HFT, staff/principal practical coding, and competitive-programming-style interviews.

This is not a roadmap. It is a training system: every phase has concept docs, runtime docs, hands-on labs in a fixed format, mock interviews with rubrics, failure analysis, and spaced repetition.

How To Use This Program

1. Pick a track in schedules/ — Accelerated (12 weeks), Serious (6 months), or Elite (12 months).
2. Read the universal framework first — FRAMEWORK.md. Use it on every problem.
3. Work through phases in order — they have dependencies. Do not skip Phase 0 or Phase 1.
4. For every problem, fill out REVIEW_TEMPLATE.md and schedule revisits via SPACED_REPETITION.md.
5. When you fail, run the diagnosis in FAILURE_ANALYSIS.md. Do not skip this.
6. Mock interview weekly minimum — see phase-11-mock-interviews/.
7. Graduate only when READINESS_CHECKLIST.md is fully passed.

Global Framework Documents

Schedules

Phases

Difficulty Ladder

For each level: failure is normal. The value is in the review process and the failure analysis, not the original solve.

When to repeat a level: if your unaided success rate is below the threshold above, do another 30–50 problems at the same level before moving up. Moving up too early calcifies bad habits.

Progress Tracking

Use a single spreadsheet/journal with columns:

• Date
• Phase / Pattern
• Problem name + source
• Solved unaided? (Y/N)
• Time spent
• Got it on first attempt? (Y/N)
• Why missed (if missed) — link to FAILURE_ANALYSIS.md category
• Next review date — from SPACED_REPETITION.md

Without tracking, the spaced repetition system collapses. Without spaced repetition, knowledge decays faster than you accumulate it.

A Note On Honesty

This curriculum cannot guarantee outcomes. What it guarantees is:

1. If you complete every phase honestly (failed problems reviewed, mocks done with full effort, no shortcuts), you will recognize > 95% of common interview problem patterns.
2. You will be able to solve unfamiliar problems — because the framework forces you to derive solutions, not memorize them.
3. You will fail mock interviews repeatedly and learn from each one. This is the entire point.
4. You will know your own weaknesses precisely, and which phase to revisit.

Skip the failure analysis, skip the reviews, skip the mocks — and the curriculum becomes a list of topics. Topics don’t get you hired.

📖 Published · commit 406ccc0 · 2026-05-21 16:15 UTC

Universal Problem-Solving Framework

Use this on every problem. It is non-optional. The goal is to make solving deterministic, not heroic.

The 16-Step Framework

1. Restate The Problem

Say it back in your own words. If you can’t restate, you don’t understand. Ambiguous parts surface here.

2. Ask Clarifying Questions

• Input type, range, sign, precision
• Are inputs sorted? Distinct? Can be empty/null?
• Output format. One answer or all answers?
• Are duplicates allowed?
• Can the input mutate? Is it streamed?
• What should happen on invalid input?
• Constraints not given?

3. Identify Constraints

Constraints dictate the algorithm. Memorize this table:

4. Work Through Examples

Use the given example. Then build at least two more:

• A trivial case (size 1, empty)
• An adversarial case (max constraints, all duplicates, all negative, sorted descending)

Work them by hand. Annotate intermediate states. This often reveals the pattern.

5. Identify Brute Force

What is the dumbest correct solution? Write it down (pseudocode). Don’t skip this even if you “see” the optimal — the brute force is your correctness oracle for stress testing.

6. Analyze Brute Force Complexity

Time and space, in big-O. If it fits the constraints, you may be done. Often it does for small N.

7. Recognize Patterns

Run through the pattern checklist in phase-02-patterns/:

• Sorted or sortable? → two pointers, binary search
• Asks for max/min over windows? → sliding window, monotonic deque
• “Subarray with property X”? → prefix sum, sliding window
• “K-th something”? → heap, quickselect
• “Number of ways”? → DP, combinatorics
• “Shortest path”? → BFS / Dijkstra / 0-1 BFS
• “Connected components / cycles / dependencies”? → union-find / DFS / topo sort
• “Decision: can we do X with budget Y?” → binary search on answer
• “Optimal sequence with overlapping subproblems”? → DP

8. Derive Optimized Approach

Reduce repeated work. Cache, sort, hash, prune, transform. State the invariant of your approach.

9. Prove Correctness

• For greedy: exchange argument or cut property.
• For DP: state definition + transition + base cases + evaluation order.
• For graphs: cite the algorithm’s correctness theorem and verify preconditions.
• For two-pointer/sliding window: the loop invariant.

10. Write Clean Code

• Meaningful names
• Single-responsibility functions
• No premature abstraction
• Avoid mutating function parameters unless intentional
• Match the patterns of the language idiom

11. Test Smoke Cases

Walk the given examples through your code by hand. Don’t run yet. Find bugs before silicon does.

12. Test Edge Cases

• Empty / null
• Size 1 / size 2
• All duplicates
• All negative / mixed signs
• Sorted ascending / descending
• Max constraint values (overflow risk)
• Multiple valid answers (specify which one)
• Disconnected graph / cycle
• Concurrent access (where relevant)

13. Test Large Cases

Confirm complexity by reasoning, not by running. Will N=10^6 pass in 1 second? In your language’s runtime?

14. Explain Complexity

State time and space. State whether the bound is tight. Mention amortized vs worst-case if relevant. State assumptions (hash table O(1) average is an assumption).

15. Handle Follow-Ups

Anticipate. Most interviews follow up with one of:

• “What if the input doesn’t fit in memory?” → streaming, external sort, sketches
• “What if it’s distributed?” → sharding, consistent hashing
• “What if reads >> writes?” → caching, replicas
• “What if writes >> reads?” → log-structured, write-back
• “What if we need approximate answers?” → Bloom, HLL, count-min
• “How would you test this?” → unit + property + stress + concurrency
• “How would you debug a production failure?” → logs + metrics + repro

16. Discuss Production Implications

For practical engineering interviews: monitoring, logging, metrics, partial failure, backpressure, retries, idempotency, observability, deployment.

The Stuck Protocol

When you’ve been silent for >2 minutes, or have no progress for 5 minutes, switch into this mode. Do not freeze. Do not flail.

1. Restate What Is Known

Out loud. “I have an array of N integers, I want the longest subarray such that…”

2. Write Brute Force

Even if it’s O(N^4) and you know it won’t pass. Brute force gives you:

• A correctness oracle
• A starting point to optimize from
• Intermediate state to inspect for patterns

3. Inspect Constraints Again

Have you forgotten one? Often the constraint is the hint. N ≤ 20 screams bitmask. K ≤ 10 screams “K is in the state”.

4. Try Smaller Examples

Solve N=1, N=2, N=3 by hand. Patterns emerge. Often the recurrence falls out.

5. Look For Repeated Work

In the brute force, what’s recomputed? That’s your DP state or memoization target.

6. Look For Monotonicity

• Is there a value over which the answer is monotonic? → binary search on answer
• Is there a window whose property is monotonic? → sliding window, monotonic stack/deque

7. Look For Graph Modeling

Words like “depends on”, “leads to”, “transitions”, “groups”, “components”, “blocked by” all suggest graphs. Try modeling explicitly.

8. Look For DP State

Ask: “What information do I need at position i to decide what’s optimal going forward?” That information is the state.

9. Look For Greedy Invariant

Ask: “If I make the locally best choice, can I prove I never need to undo it?” If yes, greedy. If no, DP.

10. Ask For A Small Hint Professionally

Sample phrases:

• “I’ve considered X and Y but I’m having trouble seeing the structure. Could you nudge me toward the right family of approach?”
• “Is the input small enough that exponential is acceptable, or are we targeting polynomial?”

A well-asked hint costs you almost nothing. A 10-minute silence is fatal.

11. Recover And Continue

Take the hint, restate the new constraint or insight, commit out loud to a direction, and resume coding. Don’t apologize repeatedly. Move forward.

A Note On Discipline

This framework feels slow for the first 50 problems. By problem 200, you’ll execute steps 1–9 in 4 minutes flat. By problem 500, the framework runs subconsciously and you’ll only consciously invoke it when stuck.

The goal is not to memorize the framework. It’s to internalize it so deeply that when you read a problem, your brain runs steps 1–9 automatically.

Candidates who skip the framework “to save time” lose interviews to candidates who don’t, because the framework users:

• Catch ambiguity before they code
• Get the right complexity on the first attempt
• Don’t waste minutes coding the wrong thing
• Communicate clearly throughout
• Know what to test before they finish coding

Code Quality Standards For Interviews

Interview code is judged differently from production code. The bar is:

• Correct above all else
• Readable — the interviewer should follow it without you explaining every line
• Simple — the simplest solution that works, not the cleverest
• Defensive only at boundaries — validate inputs once, then trust them
• Testable — pure functions and clear data flow

Interview code is not:

• Production-ready (no logging, no metrics, no retries unless asked)
• Heavily commented (good names beat comments)
• Premature-abstraction (no factory factories)
• Defensive everywhere (validating inside hot loops is noise)

The Quality Dimensions

Bad vs Good Examples

Naming

Bad:

def f(a, b):
    r = []
    for x in a:
        if x > b:
            r.append(x)
    return r

Good:

def values_above(numbers, threshold):
    return [n for n in numbers if n > threshold]

Boundary Handling

Bad (validates in every iteration):

def sum_positive(nums):
    total = 0
    for n in nums:
        if nums is None or len(nums) == 0:  # checked every iteration
            return 0
        if n > 0:
            total += n
    return total

Good (validate once at the boundary):

def sum_positive(nums):
    if not nums:
        return 0
    return sum(n for n in nums if n > 0)

Excessive Cleverness

Bad (one-liner, hard to debug):

def has_duplicate(nums):
    return len(nums) != len({*nums}) if nums else False

Good (clear intent):

def has_duplicate(nums):
    seen = set()
    for n in nums:
        if n in seen:
            return True
        seen.add(n)
    return False

The good version also has the advantage of early termination — better complexity in practice.

Helper Functions

Bad (everything in one 50-line function):

def shortest_path(grid, start, end):
    # 50 lines of BFS, neighbor computation, distance tracking, all inline
    ...

Good (extract neighbor logic):

def shortest_path(grid, start, end):
    queue = deque([(start, 0)])
    visited = {start}
    while queue:
        pos, dist = queue.popleft()
        if pos == end:
            return dist
        for nxt in neighbors(grid, pos):
            if nxt not in visited:
                visited.add(nxt)
                queue.append((nxt, dist + 1))
    return -1

def neighbors(grid, pos):
    r, c = pos
    rows, cols = len(grid), len(grid[0])
    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != '#':
            yield (nr, nc)

Premature Abstraction

Bad (over-engineered for a single use):

class CounterStrategy:
    def count(self, items):
        raise NotImplementedError

class HashCounterStrategy(CounterStrategy):
    def count(self, items):
        d = {}
        for x in items:
            d[x] = d.get(x, 0) + 1
        return d

def majority_element(nums):
    counts = HashCounterStrategy().count(nums)
    return max(counts, key=counts.get)

Good:

def majority_element(nums):
    counts = Counter(nums)
    return counts.most_common(1)[0][0]

Mutation

Bad (mutates input):

def normalized(values):
    for i in range(len(values)):
        values[i] = values[i] / max(values)  # also recomputes max each iteration
    return values

Good (no mutation, single max computation):

def normalized(values):
    if not values:
        return []
    peak = max(values)
    return [v / peak for v in values]

Hidden State

Bad (global counter):

_call_count = 0
def fib(n):
    global _call_count
    _call_count += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Good (state passed explicitly):

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Language-Idiomatic Code

You should write code that looks like it was written by someone fluent in the language. Examples:

Python

• Use list/dict/set comprehensions where natural
• Use Counter, defaultdict, deque, heapq, bisect
• Use enumerate, zip, unpacking
• Avoid C-style for i in range(len(x)) if you only need values

Java

• Use enhanced for-loop where possible
• Use Map.computeIfAbsent, Map.getOrDefault
• Use Optional only where it fits the API; not for short-circuit logic
• Prefer ArrayDeque over Stack (legacy)

Go

• Prefer slices over arrays
• Use for range for both index and value
• Return errors explicitly; don’t panic in interview code
• Buffered channels only when justified

C++

• Use auto where it improves readability
• Range-based for-loops
• Prefer std::vector and std::unordered_map
• Use emplace_back over push_back for non-trivial types
• const references for non-trivial inputs

JavaScript/TypeScript

• Use Map/Set (not {}/array hacks) when keys aren’t strings or order matters
• const by default, let only when reassignment is needed
• Avoid var
• TS: prefer unknown over any at boundaries

Comments

• Avoid: comments that restate what the code says (// increment i).
• Prefer: comments that explain why — the non-obvious tradeoff, the invariant, the reason a less elegant approach was chosen.
• Required: a one-line comment above any non-trivial recurrence/invariant. Example: # dp[i][j] = max profit with i transactions ending at day j.

Length

For most coding interview problems:

• Easy: 10–25 lines
• Medium: 20–50 lines
• Hard: 30–80 lines

If your Easy is 80 lines, you’re overengineering. If your Hard is 200 lines, you’ve gone wrong somewhere — re-examine the approach.

Final Self-Review Checklist

Before saying “I’m done”:

1. ☐ Function/variable names are meaningful
2. ☐ No dead code, no commented-out blocks
3. ☐ Boundary checks at the entry, not in the hot loop
4. ☐ Helper functions for distinct logical units
5. ☐ No mutation of input unless intentional and stated
6. ☐ No globals introduced
7. ☐ Standard library used idiomatically
8. ☐ Indentation/formatting consistent
9. ☐ Code I would be willing to send a colleague for review

Interview Communication Rules

Coding interviews are collaborative problem-solving sessions, not exams. Half the signal an interviewer collects is how you communicate. A correct silent solution often scores worse than a slightly imperfect one with strong communication.

Core Principles

1. Narrate continuously, but not constantly. Your mouth does not need to track your fingers character-by-character. It tracks your intent.
2. Show your reasoning, not just your conclusion. “I’m choosing a hashmap because we need O(1) lookup by ID” beats silently typing Map<String, Foo>.
3. Two-way street. Pause for confirmation at decision points. The interviewer wants to be involved.
4. Hide nothing. If you’re unsure, say so. If you don’t remember an API, say so. Hiding looks worse than admitting.
5. Forward motion always. Even when stuck, narrate progress: “I’m now going to try a smaller example” is forward motion.

Phase 1 — Opening (first 1–3 minutes)

What to do

• Read the problem fully (don’t start coding)
• Restate it
• Ask clarifying questions
• Confirm constraints

Sample phrases

“Let me read this through once first… OK. So if I understand correctly, I need to [restate]. Is that right?”

“Before I start, can I confirm a few things about the input? Specifically: can the array be empty? Can it contain negative numbers? Are there duplicates?”

“What’s the expected size of N here? Around 10^5? OK, so we’re targeting O(N log N) or better.”

“If there are multiple valid outputs, can I return any one, or is there a specific one expected?”

Anti-patterns

• Starting to code immediately
• Asking 15 questions in a row (drip-feed them as they become relevant)
• Asking questions whose answers are obvious from the problem statement (signals you didn’t read carefully)

Phase 2 — Brute Force (1–3 minutes)

What to do

• State the dumbest correct solution
• Compute its complexity
• Confirm whether it’s acceptable

Sample phrases

“Let me start with the brute force just to anchor. I could check every pair, which would be O(N^2). Given N is up to 10^5, that’s 10^10 operations — too slow. So we need something better.”

“The naive solution is O(2^N) — that’s fine for N=20 but won’t scale. Let me see if we can do better.”

“If we sort first, that gives us O(N log N) for the sort, and then… let me think about the scan.”

Anti-patterns

• Skipping brute force (“I know the optimal already”)
• Computing brute force complexity wrong (always double-check)
• Stating brute force without saying whether it suffices

Phase 3 — Optimization (3–10 minutes)

What to do

• Think out loud
• State observations
• Propose ideas and evaluate them
• Commit to one direction
• Sanity-check before coding

Sample phrases

“I notice the array is sorted, which means I can probably use two pointers…”

“The fact that K is small — only up to 10 — suggests we might want K in our DP state.”

“I see a pattern of repeated subproblems here. Let me define a state: dp[i][j] = …”

“Let me try a small example to verify my recurrence…”

“OK, I think my approach is: sort by start time, then greedily pick. Let me convince myself this works with an exchange argument…”

Anti-patterns

• Switching ideas every 30 seconds without exploring any
• Coding before stating the approach
• Not verifying correctness on a small example

Phase 4 — Coding (10–25 minutes)

What to do

• Narrate intent at function/block boundaries
• Explain non-obvious choices
• Stay quiet during routine syntax
• Ask “is the API I’m assuming OK?” if uncertain

Sample phrases

“I’m going to use a heap here, in Python that’s heapq. Pushing tuples to break ties by ID.”

“For the visited set, I’ll use a hash set rather than a 2D boolean array, since we’re not sure of the bounds.”

“I’m using a sentinel value of -1 to mean ‘not yet computed’ in the memoization.”

“Let me extract this into a helper function — it’ll make the recursion cleaner.”

Anti-patterns

• Silent typing for 5+ minutes
• Constant low-level narration (“now I’m typing a for loop”)
• Going down a rabbit hole on language minutiae mid-flow

Phase 5 — Testing (3–5 minutes)

What to do

• Walk through the given example
• Walk through your own edge cases
• Catch and fix bugs before the interviewer points them out

Sample phrases

“Let me trace through example 1. Initial state: … after iteration 1: … after iteration 2: … final answer: 7. Matches the expected.”

“Edge cases: what if the array is empty? My code would… let me check… yes, it returns 0, which is correct.”

“What about all negatives? Hmm, my initialization assumes a non-negative max. Let me fix that — initialize to negative infinity.”

“I think there’s an off-by-one here. Let me re-examine the loop bound.”

Anti-patterns

• Skipping testing because “the code looks right”
• Testing only the happy path
• Defending broken code when a bug is pointed out (just fix it)

Phase 6 — Complexity & Follow-Ups (2–5 minutes)

What to do

• State time and space
• Mention assumptions
• Engage with follow-ups thoughtfully

Sample phrases

“Time complexity is O(N log N) — dominated by the sort. Space is O(N) for the auxiliary array, or O(1) if we sort in place.”

“Average case for the hashmap is O(1), but worst case is O(N) under adversarial hashing. In Python the dict implementation handles that reasonably well.”

“If we needed to scale this to 10 million users, I’d consider… [sharding / external sort / approximate counters / etc.]”

“If reads were much more frequent than writes, we might precompute and cache.”

Anti-patterns

• Claiming O(N) when it’s actually O(N log N)
• Forgetting space complexity
• Defensive answers to follow-ups (“I’d need more info” instead of engaging)

Handling Hints

If the interviewer gives a hint:

“Ah, that helps — so you’re saying we should [restate]. Let me adjust my approach…”

Then commit out loud to the new direction. Don’t second-guess. Take the hint, integrate it, move forward.

If you need a hint:

“I’ve explored [X] and [Y]. I’m having trouble seeing how to avoid the O(N^2) here. Could you nudge me toward the family of approach?”

A well-asked hint costs you almost nothing. Frozen silence is fatal.

Handling Mistakes

When you find your own bug:

“Hmm, let me re-examine this — I think there’s a bug at line N. Yes, the comparison should be < not ≤. Let me fix that.”

When the interviewer finds a bug:

“Oh, you’re right — the empty case isn’t handled. Let me add a guard.”

Never:

• Argue
• Explain why the bug is “not really a bug”
• Get flustered

Always:

• Acknowledge briefly
• Fix
• Move on

Handling Pressure / Freezing

If you blank:

“Give me 30 seconds to think.” (Then actually think — don’t fake it.)

Then run the stuck protocol. Out loud:

“OK, let me back up. What I know is [X]. The brute force was [Y]. The constraint that’s hinting at something is [Z]…”

Talking through the stuck protocol restarts your thinking and shows the interviewer you have a process for being stuck.

Closing Strong

Final 1–2 minutes:

“To summarize: I’m using [data structure] with [algorithm]. Time is O(…), space is O(…). Edge cases handled: empty, single element, duplicates, max constraints. The main risk in production would be [X], which I’d address by [Y].”

A clean summary leaves the interviewer with a tidy mental model of your work — much better than ending mid-test.

Body Language & Tone (Video / In-Person)

• Sit up. Look at the interviewer when explaining, at the editor when coding.
• Speak at moderate pace. Faster than normal = nervous, slower = padding.
• Avoid filler (“um”, “like”) — silence is preferable to filler.
• Don’t apologize repeatedly. One apology when you fix a bug is enough.
• Show interest in the problem. Curiosity is a positive signal.

Phrases To Avoid

• “This is easy” — even if it is, this can read as arrogant
• “I’ve seen this before” — be careful; if you go on autopilot you’ll miss the variant
• “I don’t know” with no follow-up — replace with “I don’t know X, but I can reason about it via Y”
• “That won’t work” without explanation
• “Just” used dismissively (“we just need to…”)

What Strong Communication Buys You

• Partial credit when your code is incomplete (the interviewer saw your reasoning)
• Hints offered earlier (interviewers want to help engaged candidates)
• Believability of follow-up answers (a candidate who reasoned clearly throughout is trusted on production tradeoffs)
• Hire signal even on hard problems you didn’t fully solve

Failure Analysis System

Every failed problem (or weak performance) maps to one or more failure categories. The category determines the drill that fixes it. Without this taxonomy, you’ll repeat the same mistake forever.

How To Use

After every miss:

1. Identify the primary failure category (the root cause, not the symptom).
2. Identify any secondary categories.
3. Run the listed drill within 24 hours.
4. Re-test on a similar problem within 1 week.

The 16 Failure Categories

1. Did Not Understand The Problem

Symptom: Solved a problem the interviewer didn’t ask. Root cause: Skipped restating, didn’t ask clarifying questions. Fix: Always restate. Always ask 3+ clarifying questions before coding. Drill: Take 10 LeetCode problems, do only steps 1–4 of FRAMEWORK.md (restate, clarify, identify constraints, examples). Don’t solve them. The drill is reading. Re-test: Mock interview with an interviewer who deliberately gives an ambiguous problem.

2. Missed Constraints

Symptom: Brute force passed at small N but TLE’d at full N. Or used 32-bit integer when sum exceeds 2^31. Root cause: Skipped step 3 of the framework. Fix: Make a habit: the moment you read a constraint, derive the target complexity out loud. Drill: Read 20 problems. For each, before reading the editorial, write down: target complexity, allowed N, integer width needed. Re-test: Solve 5 problems where the constraint is the hint (e.g., N≤20 → bitmask).

3. Could Not Find Brute Force

Symptom: Stared at the problem with no starting point. Root cause: Tried to find the optimal directly. Dangerous habit. Fix: Brute force is always possible. Iterate over every subset / pair / arrangement / state. State it even if it’s exponential. Drill: 10 problems. For each, write only the brute force in pseudocode. Don’t optimize. Re-test: Mock with a hard problem; goal is to communicate brute force in <3 minutes.

4. Could Not Optimize

Symptom: Wrote brute force, then froze. Root cause: No systematic optimization toolkit. Fix: Run the optimization checklist (step 7 of framework): pattern recognition, repeated-work elimination, monotonicity, sortedness exploitation, state compression, math. Drill: Take 10 brute-force solutions to known problems. For each, optimize without looking at the editorial using the checklist. Re-test: Solve 5 unfamiliar mediums in <30 min each.

5. Chose Wrong Data Structure

Symptom: Used a list where a set would have given O(1) lookup. Used a heap where a sorted array suffices. Used recursion where a stack would simplify. Root cause: Didn’t reason about access patterns. Fix: Before choosing a DS, list the operations you need and their frequency. Then pick the DS whose complexity matrix matches. Drill: phase-01-foundations/data-structures/ — reread the operations table for each DS. Then re-solve 5 problems consciously documenting why each DS was chosen. Re-test: Mock with explicit “why this DS?” follow-ups.

6. Bad Complexity

Symptom: Said O(N) when it was O(N log N). Or claimed O(1) on operations that are amortized. Root cause: Sloppy analysis, no habit of double-checking. Fix: State complexity and the basis. “O(N log N) because we sort, then linear scan” — not just “O(N log N)”. Drill: Take 20 of your own past solutions. Re-derive complexity. Compare to what you said. Re-test: Mock interviewer specifically grills on complexity.

7. Buggy Implementation

Symptom: Approach was right, but the code had off-by-ones, wrong operators, swapped variables. Root cause: Coding faster than thinking. Insufficient pre-coding clarity. Fix: Write pseudocode first. Trace through one example before running anything. Drill: Standard implementations: write binary search, BFS, DFS, union-find from scratch 10 times each. Use templates only after you can write them error-free. Re-test: Solve 5 problems with hand-traced verification before submission.

8. Weak Testing

Symptom: Submitted, got “wrong answer on test 7”. Hadn’t tested edge cases. Root cause: Skipped step 12 of the framework. Fix: Make the universal edge-case checklist a reflex. Before submission, run through it. Drill: Take 5 of your “wrong on hidden test” problems. Without looking at the test that failed, generate 10 edge cases for each. Re-test: Solve 5 problems and catch your own bug before submission. Score = problems where you fixed a bug pre-submission.

9. Poor Communication

Symptom: Mock interviewer said “I had no idea what you were thinking.” Root cause: Silent coding, or only narrating low-level mechanics. Fix: COMMUNICATION.md. Narrate intent at decision points. Drill: Solve 10 problems while recording yourself narrating. Listen back. Are you communicating decisions, or just typing aloud? Re-test: Mock with explicit communication scoring.

10. Froze Under Pressure

Symptom: Knew the technique in practice. Couldn’t access it in mock. Root cause: Insufficient mock volume. Fix: More mocks. Pressure tolerance is built only by exposure. Drill: 5 mocks in a week with a real human or pressure-simulating tool. Use the stuck protocol explicitly when you freeze. Re-test: Mock with cold problems. Goal: never go silent for >60 seconds.

11. Missed Edge Cases

Symptom: Solution was correct on examples but failed on size-1, empty, or max-constraint inputs. Root cause: Didn’t run the universal checklist. Fix: Build muscle memory for: empty / 1 / 2 / dup / negative / sorted / reversed / max / disconnected / cycle. Drill: Take 10 past solutions. For each, brainstorm 5 edge cases. Verify your code handles them. Re-test: Mock where edge cases are the gating criterion.

12. Runtime / Language Issue

Symptom: Code was algorithmically right but ran slow / crashed / behaved wrong due to language behavior. Examples: integer overflow in Java, dict iteration order bug, Python recursion limit, C++ undefined behavior. Root cause: Insufficient runtime depth. Fix: phase-09-language-runtime/ for your primary language. Drill: Read your language’s track end-to-end. Solve 5 problems specifically targeting the gotchas (e.g., overflow problems, recursion-depth problems). Re-test: Runtime-deep-dive mock (mock-09).

13. Concurrency Issue

Symptom: Race condition, deadlock, lost update, visibility bug. Root cause: Missing concurrency mental model. Fix: phase-09-language-runtime/ (concurrency sections) + phase-08-practical-engineering/ thread-pool / job-queue labs. Drill: Implement thread-pool, rate limiter, and producer-consumer queue from scratch with race-condition tests. Re-test: Concurrency-heavy mock (mock-11).

14. Overfit To Memorized Pattern

Symptom: Forced a known pattern that didn’t fit. E.g., applied sliding window to a problem that needed monotonic deque. Root cause: Pattern matching without understanding. Fix: Re-read pattern docs and focus on when the pattern does NOT apply. Drill: Take 10 problems. For each, list 3 patterns it might be, then eliminate 2 with reasoning. Re-test: Mock with problems specifically chosen to be near-misses of common patterns.

15. Did Not Prove Correctness

Symptom: Submitted a greedy that was wrong. Or a DP whose recurrence was incorrect. Root cause: Skipped step 9 of the framework. Fix: Force yourself to state the invariant or recurrence before coding. Drill: Take 10 greedy problems. For each, state the exchange argument. Take 10 DP problems. For each, state the recurrence + base case + evaluation order. Re-test: Solve 5 problems where the proof is the hard part.

16. Could Not Handle Follow-Up

Symptom: Solved the core problem, but interviewer’s follow-up (“how would this scale to 10M users?”) got a vague answer. Root cause: No production / system thinking. Fix: phase-08-practical-engineering/ labs all include the standard follow-up bank. Drill: Take 10 of your past solutions. For each, write a 2-paragraph answer to: “scale to 10M users”, “make distributed”, “handle partial failure”, “add observability”. Re-test: Senior-engineer mock (mock-07) which weighs follow-ups heavily.

Tracking Failures Over Time

Maintain a failures.md (or spreadsheet) with columns:

After 4 weeks, count by category. Your top 3 categories are your personal weakness profile. Spend the next 4 weeks specifically drilling those.

This is how you avoid the “I keep failing at the same thing” trap.

Common Compound Failures

Some categories often co-occur. If you see these together, treat the deeper one:

• #1 + #11 (didn’t understand + missed edges) → really #1. Fix understanding first.
• #3 + #4 (no brute force + couldn’t optimize) → really #3. You can’t optimize what you don’t have.
• #7 + #8 (buggy + weak testing) → really #8. Better testing catches bugs.
• #5 + #6 (wrong DS + bad complexity) → really #5. Right DS gives right complexity.
• #10 + #9 (froze + bad communication) → really #9. Talking unfreezes you.
• #14 + #15 (overfit pattern + no proof) → really #15. Proving forces understanding.

When Failures Are Good

Some failures are productive:

• First attempt at a new pattern → expected to fail, the failure teaches.
• Difficulty stretch (jumping a level) → expected to fail 50%+ of the time.
• Mock interviews → 30%+ failure rate is normal and healthy.

Failures are bad when:

• You repeat the same category 5+ times without improvement.
• You stop tracking them.
• You don’t run the drill.
• You blame the problem (“that was unfair”) instead of analyzing yourself.

Final Readiness Checklist

You are ready for the interviews you’re targeting only when every box below is honestly checked. This is binary, not aspirational.

Algorithmic Solving

• Solve LeetCode Easy in <12 minutes (90% success rate over 50 recent problems)
• Solve LeetCode Medium in 25–35 minutes (75% success rate over 100 recent problems)
• Solve LeetCode Hard in 45–60 minutes (50% success rate over 50 recent problems)
• Recognize the pattern within 2 minutes of reading any LeetCode Medium
• Derive a non-trivial optimization without seeing it before, on at least 30 unfamiliar problems

Brute Force & Optimization

• Can state the brute force in <2 minutes for any unseen problem
• Can compute brute force complexity correctly without aid
• Can derive optimal complexity from constraints alone
• Have written brute-force-comparator tests for at least 10 problems

Correctness & Proofs

• Can state DP recurrences with base cases and evaluation order on the spot
• Can produce an exchange argument for at least 5 greedy problems
• Can produce a counterexample to a wrong greedy in <5 minutes
• Have proved correctness for at least 20 different solutions (greedy, DP, graph)

Code Quality

• Can write binary search, BFS, DFS, union-find, topological sort, and Dijkstra from scratch error-free in <10 minutes each
• Code passes the self-review checklist on every solve
• No off-by-one bugs in 10 consecutive binary search problems
• No mutable default argument / shared-state bugs in 10 consecutive recursion problems

Testing

• Run the universal edge-case checklist as reflex on every problem
• Have written stress-test verifiers for at least 5 problems
• Catch your own bugs before submission on 80%+ of problems
• Property-based tested at least 3 implementations

Patterns

• All 28 patterns in phase-02-patterns/ — recognize signals in <2 minutes
• Have solved at least 5 problems per pattern
• Can explain when each pattern does not apply
• Can produce a clean template for each pattern from memory

Data Structures

• Internal representation, complexity, and memory behavior of all foundation DS in phase-01-foundations/
• Can choose between hashmap / sorted array / heap / BST given access patterns
• Can implement segment tree, Fenwick tree, trie, LRU cache from scratch
• Understand iterator invalidation, hash collision behavior, and resize cost in your primary language

Graph Algorithms

• BFS, DFS, Dijkstra, topological sort, union-find — implement from scratch in <10 minutes each
• Recognize when 0-1 BFS, Bellman-Ford, or A* is the right choice
• Can model a word problem as a graph (nodes + edges + weight) in <3 minutes
• Have completed all 9 product-style labs in phase-04-graphs/labs/

Dynamic Programming

• Can derive state + transition + base case for unseen DP problems
• Have completed brute-force → memo → tabulated → space-optimized for at least 15 problems
• Recognize 1D / 2D / interval / tree / digit / bitmask / knapsack signals
• Can articulate why greedy fails for a given DP problem

Language & Runtime

• Read your primary language’s track in phase-09-language-runtime/ end to end
• Can explain stack vs heap, scope/lifetime, value vs reference semantics fluently
• Can explain GC / ownership behavior of your language
• Can explain hash collision and resize behavior of your language’s hashmap
• Have used the language’s profiler at least once on real code

Concurrency

• Can identify race conditions and deadlocks in code review
• Have implemented thread pool, rate limiter, and bounded blocking queue from scratch
• Can articulate memory visibility / happens-before in your language
• Have used the race detector / equivalent at least once

Practical Engineering

• Completed at least 12 of the 23 labs in phase-08-practical-engineering/
• Can answer all 13 standard follow-ups (10M users, distributed, concurrency, race testing, metrics, logging, debugging, partial failure, memory leaks, extensibility, backpressure, retries, deduplication) on demand
• Can sketch a small system (LRU cache, rate limiter, autocomplete) on a whiteboard in 30 minutes

Communication

• Restate every problem before coding
• Ask 3+ clarifying questions per problem
• Narrate intent at decision points (not low-level mechanics)
• Recover from mistakes without flustering
• Handle hints gracefully and integrate them
• Close every solve with a clean summary

Mock Interview Performance

• Pass mock-03 (Medium LeetCode) — 7+/10 average
• Pass mock-05 (Big Tech phone) — 7+/10 average
• Pass mock-06 (Big Tech onsite) — 7+/10 average
• Pass mock-09 (runtime/language) — 7+/10 average
• Pass mock-11 (concurrency) — 7+/10 average
• (For senior+) Pass mock-07 (senior engineer)
• (For staff+) Pass mock-08 (staff practical)

Failure Analysis

• Maintain a failure log per FAILURE_ANALYSIS.md
• Top 3 personal failure categories identified
• At least 2 weeks of focused drilling on top failure category complete
• Re-test results show measurable improvement

Spaced Repetition

• Active spaced repetition rotation per SPACED_REPETITION.md
• At least 50 problems graduated to Tier 6
• No overdue reviews more than 1 week old

Recovery & Stuck Protocol

• Never go silent for >60 seconds in a mock
• Use the stuck protocol explicitly when stuck
• Recover from a wrong direction in <3 minutes
• Ask for hints professionally without losing composure

Production Awareness

• Can extend any solved problem with: scale to 10M, make distributed, handle partial failure, add observability
• Can articulate tradeoffs (memory vs latency, consistency vs availability, accuracy vs speed)

Targeted Roles

Beyond the universal checklist, additional criteria by role:

FAANG / Big Tech

• All universal items
• mock-05 + mock-06 passed twice with different problems

Infrastructure / Backend / Platform

• All universal items
• mock-08 + mock-10 passed
• All Phase 8 labs complete

Distributed Systems

• All universal items
• mock-08 + mock-10 + mock-11 passed
• Phase 8 + Phase 4 (graph) labs complete

Compiler / Runtime

• All universal items
• mock-09 passed twice
• Phase 9 fully complete for primary language
• Phase 3 (advanced DS) labs complete

Quant / HFT

• All universal items
• mock-12 (competitive style) passed
• Phase 7 (competitive) topics complete
• Phase 5 (DP) extreme topics complete

Senior / Staff / Principal Practical

• All universal items
• mock-07 + mock-08 passed twice each
• All Phase 8 labs complete with full follow-up answers
• Code quality bar unwaveringly met

Competitive Programming

• All universal items
• Phase 7 + Phase 12 complete
• mock-12 (competitive style) passed twice
• Solving Codeforces Div 2 D regularly

Honesty Test

For every checked box, ask: “Could I do this right now, cold, with no warm-up?”

If the answer is “after I review my notes” — uncheck it. Notes don’t come into the interview.

If the answer is “if I had a good day” — uncheck it. Interview days are sometimes bad days.

Honesty here is the difference between feeling ready and being ready.

Problem Review Template

Use this after every problem — solved or failed. The review is where the learning compounds. Without it, problems are forgotten in 72 hours.

Save each review as a separate file or notebook entry. Recommended: reviews/YYYY-MM-DD-problem-name.md.

Template

# Problem Name

## Source
LeetCode 42 / Codeforces Round 800 Div 2 C / etc.

## Difficulty
Easy / Medium / Medium-Hard / Hard / Very Hard / CP-Hard / Grandmaster

## Pattern(s)
Two pointers / Sliding window / DP-2D / Graph BFS / etc.
(Multiple patterns possible.)

## First Intuition
What was my first instinct on reading the problem?
What pattern did I think it was?
Was that intuition right?

## Brute Force
- Approach (1–2 sentences)
- Complexity: time / space
- Why it doesn't pass (or "passes within constraints")

## Optimal Idea
- Approach (3–5 sentences)
- Key insight (the *one* thing that unlocks the problem)
- Complexity: time / space

## Why I Missed It (if applicable)
The honest answer. Choose from:
- Didn't recognize the pattern
- Recognized the pattern but applied it wrong
- Couldn't derive the recurrence / invariant
- Wrong data structure choice
- Implementation bug
- Misread the problem
- Ran out of time
- Got the optimal but couldn't prove it

## Key Insight
The single sentence that, if I'd known it, would have unlocked the problem in 5 minutes.

## Data Structures Used
- DS 1: why
- DS 2: why
- (etc.)

## Complexity
Time: O(...)
Space: O(...)
Tight bound? Y/N
Amortized? Y/N

## Bugs I Made
- Off-by-one at line X
- Forgot to handle empty case
- Wrong comparison operator (<= vs <)
- Used wrong variable in inner loop
- Modified collection while iterating
- (etc.)

## Edge Cases I Missed
- Empty input
- Single element
- All duplicates
- All negatives
- Max constraint
- Disconnected component
- (etc.)

## Follow-ups Practiced
- "What if the input is streamed?" → answer
- "What if N is 10^9?" → answer
- "What if memory is constrained?" → answer

## Product Extension
How does this map to a real-world system?
e.g., "This LRU cache pattern is exactly what a CDN edge node uses for hot-content eviction."

## Language/Runtime Notes
- Specific stdlib gotcha I hit
- Memory behavior surprise
- Concurrency consideration if relevant

## How I Would Recognize This Again
A pattern signal in plain English:
"When the problem asks for the minimum window covering K elements over a stream, with constant-time element insertion/removal and order matters, it's a sliding window with a hashmap."

This is the most important field. Optimize for *recognition*, not memorization.

## Re-solve Schedule
Per [SPACED_REPETITION.md](SPACED_REPETITION.md):
- Same day: ☐ done / not done
- 2 days later: ☐ scheduled for [date]
- 1 week later: ☐ scheduled for [date]
- 2 weeks later: ☐ scheduled for [date]
- 1 month later: ☐ scheduled for [date]
- 3 months later: ☐ scheduled for [date]

## Attempts Log
| Date | Unaided? | Time | Outcome | Notes |
|---|---|---|---|---|
| 2026-05-20 | N | 45 min | Wrong, then hint | Missed monotonic stack pattern |
| 2026-05-22 | Y | 18 min | Correct | Recognized pattern immediately |
| 2026-05-29 | Y | 12 min | Correct | Optimal first attempt |

How To Fill It Out (Do’s and Don’ts)

DO

• Be brutally honest. “I gave up after 20 minutes” is more useful than “I solved it but slowly”.
• Name the one insight. Forcing yourself to a single sentence forces understanding.
• Re-solve from a blank file at scheduled intervals.
• Tag heavily. Pattern, difficulty, data structure — these become your search keys.

DON’T

• Copy the editorial verbatim. Translate into your own words.
• Skip the “Why I Missed It” field when you got it right — what was hard about it? What might have tripped you up if you’d been less lucky?
• Skip the “How I Would Recognize This Again” field. This is where 80% of the value lives.
• Move on without scheduling the next re-solve.

Review Aggregation

Every Friday: skim the week’s reviews. Look for patterns:

• “I keep missing monotonic stack opportunities” → drill that pattern.
• “I keep making off-by-one bugs in binary search” → write a personal binary search template and use it.
• “I keep choosing the wrong DP state on tree problems” → revisit phase-05-dp/categories/dp-tree.md.

Every month: aggregate into a personal weakness list. Top 3 weaknesses get dedicated drilling for the next month.

Spaced Repetition System

The brain forgets new information on a curve. Without re-exposure, ~70% of what you learn today is gone in 7 days. Spaced repetition counteracts this with strategically-timed reviews.

This system applies to two things:

1. Problems you’ve solved (especially failed-then-solved ones)
2. Concepts (patterns, data structures, algorithms)

The 6-Tier Interval Schedule

Graduation criterion: if Tier 6 is unaided in <120% of your best time, the problem is “owned” — drop it from active rotation. Otherwise, restart at Tier 3.

What “Re-solve” Means

Re-solving is not reading your old solution. It is:

1. Fresh editor / blank file.
2. Re-read the problem statement.
3. Solve from scratch.
4. Compare to your previous solution after.

If you can’t do it without peeking → demote one tier (tier 4 → tier 3) and continue.

What “Verbal Explanation” Means (Tier 5+)

Without writing code, explain out loud (record yourself if alone):

1. Restate the problem in your own words.
2. State the brute force.
3. State the optimal approach.
4. State the key insight.
5. State the complexity (time + space) and why.
6. State 3 edge cases and how they’re handled.
7. Sketch 2 follow-up answers.

Listen back. Did you stumble? Demote one tier. Did you flow? Tier graduated.

Concept-Level Spaced Repetition

For patterns and algorithms (not problems), use a similar schedule but with different review actions:

Logistics: How To Maintain The Schedule

Option 1: Spreadsheet

Columns: Problem | Last Solved | Tier | Next Review Date | Difficulty | Pattern | Notes

Sort by Next Review Date. Top of the list = today’s reviews.

Option 2: Anki (or SRS app)

• One card per problem.
• Front: problem name + difficulty.
• Back: pattern + key insight + complexity.
• Use the SRS scheduling.

Custom intervals matter — the default Anki intervals are tuned for vocabulary, not problems. Use 1d, 2d, 7d, 14d, 30d, 90d.

Option 3: Folder structure (no tooling)

reviews/
  today.md            # editable list of today's review problems
  upcoming/
    2026-05-22.md     # problems due that date
    2026-05-29.md
    ...
  archive/
    YYYY-MM-DD-problem-name.md

Each evening: move tomorrow’s file to today.md.

Daily Volume Guidelines

When you have N problems in active rotation, your daily review load looks like:

When daily reviews exceed your capacity:

• Graduate aggressively (drop owned problems).
• Slow down new problem intake.
• Consolidate easy/owned problems into “weekly batch reviews” instead of individual reviews.

What To Do When You Fall Behind

Inevitable. When you have 50+ overdue reviews:

1. Don’t panic-skip. Don’t mark them all done.
2. Triage by tier. Tier 1 + 2 are the most fragile — do those first.
3. Drop tier 5 + 6 for 1 week — they decay slowly.
4. Reduce new intake to 0 until reviews are caught up.
5. Audit: what made you fall behind? Too many new problems? Underestimated review time? Adjust intake rate.

Why This Matters

Without spaced repetition, your interview prep is a leaky bucket. You add 10 problems a week, lose 8 to forgetting, net +2.

With spaced repetition, you add 5 problems a week, retain 5, and after 3 months you have 60 deeply-owned problems instead of 30 vaguely-remembered ones.

In an interview:

• Vaguely-remembered → “I think I’ve seen this before, but I can’t quite…”
• Deeply-owned → “This is a [pattern] problem. The key insight is [X]. I’d solve it with [approach].”

The latter is a hire signal. The former is not.

Integration With The Curriculum

• Every problem solved during the curriculum enters Tier 1 automatically.
• Every problem in phase-11-mock-interviews/ you fail enters Tier 1 with a failure_category tag.
• Every concept in a phase README enters Tier 1 the day you finish the phase.
• The Tier 6 graduation criterion is also part of the READINESS_CHECKLIST.md.

12-Week Accelerated Track

Audience: You have a deadline in 8–14 weeks (a known interview, an offer expiring, a layoff window). You can put in 25–35 hours/week.

Tradeoffs you are accepting:

• You will skip Phase 7 (competitive programming) almost entirely.
• You will skip Phase 12 (grandmaster) entirely.
• You will get to “competent at FAANG mediums” not “consistently solves FAANG hards in 45 minutes”.
• Concept depth is sacrificed for problem volume in some weeks.

This track is sufficient for: new-grad / SWE2 FAANG, scaleups, most backend/platform roles. This track is NOT sufficient for: staff/principal interviews, quant/HFT, compiler/runtime, distributed systems specialty roles.

Daily Cadence

• Weekday: 3–5 hours
  • 90 min: new content (read concept doc + work through 1 lab)
  • 90 min: problem solving (3–5 problems)
  • 30 min: review (spaced repetition queue)
  • 30 min: failure analysis if you missed anything
• Saturday: 6 hours
  • 1 mock interview (90 min including review)
  • 4 hours problem solving
  • 30 min review
• Sunday: 4 hours
  • Weakness drilling on top failure category
  • Re-solve all this week’s failures
  • Plan next week

Total: 25–30 hours/week

Weekly Plan

Week 1 — Foundation Reset

Goal: Stop being random. Internalize the framework.

• Read README.md, FRAMEWORK.md, COMMUNICATION.md, CODE_QUALITY.md in full
• Complete all 7 labs in phase-00-execution-baseline/
• 25 LeetCode Easy problems applying the framework rigorously (full restate, brute force, optimize, test)
• 0 mocks (you’re not ready)

Mastery check: You can solve LeetCode Easy in 12 minutes with the full framework, narrating throughout.

Week 2 — Foundations Of Data Structures

• Read all 15 DS docs in phase-01-foundations/data-structures/
• 30 problems: array, string, hashmap, stack, queue (mostly Easy + a few Medium)
• 1 mock (Easy level)
• Read phase-01-foundations/runtime/ — stack vs heap, scope/lifetime, mutable vs immutable

Mastery check: Operations + complexity table for every DS reproducible from memory.

Week 3 — Linked Lists, Trees, Recursion

• Phase 1 labs: linked list reversal, recursion, binary search, basic trees
• 25 problems (15 Easy + 10 Medium)
• Read remaining runtime docs in Phase 1
• 1 mock (Easy/Medium mix)

Week 4 — Pattern Onboarding (Part 1)

• Read patterns: two pointers, sliding window, prefix sums, hashing, sorting+greedy, binary search, monotonic stack
• For each pattern: 4–5 problems (Medium-leaning)
• 1 mock (Medium)

Mastery check: Can recognize each pattern’s signal in <2 minutes for unseen problems.

Week 5 — Pattern Onboarding (Part 2)

• Read patterns: monotonic queue, intervals, linked list manipulation, tree DFS/BFS, graph DFS/BFS, topological sort
• 30 problems across these patterns
• 1 mock (Medium)

Week 6 — Pattern Onboarding (Part 3) + DP Intro

• Read patterns: union find, backtracking, basic DP, 1D DP
• Read phase-05-dp/concepts/ — memoization, state definition, transitions, base cases
• 25 DP problems (Easy → Medium)
• 1 mock (Medium)

Mastery check: Can write the brute → memo → tabulated → space-optimized progression for any 1D DP.

Week 7 — Trie, Heap, K-way Merge, 2D DP

• Read patterns: trie, heap top-K, K-way merge, 2D DP, knapsack, subsequence DP, string DP
• 25 problems
• 1 mock (Medium-Hard)

Week 8 — Graphs Deep Dive

• Read phase-04-graphs/algorithms/: BFS, DFS, multi-source BFS, 0-1 BFS, Dijkstra, topological sort, cycle detection, MST (Kruskal+Prim), union find
• 25 graph problems
• 2 product-style labs from phase-04-graphs/labs/
• 1 mock (Medium-Hard graph-heavy)

Week 9 — DP Deeper + Greedy

• Read DP categories: tree DP, interval DP, bitmask DP (overview), knapsack variants, LIS, edit distance
• Read phase-06-greedy/concepts/: greedy choice, exchange argument, invariants
• 25 problems (mix DP + greedy)
• 2 greedy labs (with proofs)
• 1 mock (Medium-Hard mixed)

Week 10 — Practical Engineering Coding

• Complete labs from phase-08-practical-engineering/: LRU cache, rate limiter, autocomplete, thread pool, KV store, retry+backoff
• Read your primary language’s track in phase-09-language-runtime/
• 15 problems (mediums + 1–2 hards)
• 2 mocks (1 Big Tech phone, 1 Big Tech onsite)

Week 11 — Hard Problems + Mock Marathon

• 20 LeetCode Hard problems
• Daily mock interviews (5 mocks this week, mix of phase-11-mock-interviews/ types)
• Failure analysis on every mock
• Drill top failure category

Week 12 — Polish, Confidence, Rest

• 3 mocks (cold, varied — no pre-warmup)
• Re-solve top 30 problems from spaced repetition queue
• Complete READINESS_CHECKLIST.md honestly
• 1 day complete rest before interview

Problem Volume Targets

Review Schedule (per SPACED_REPETITION.md)

Use the abbreviated tier schedule for accelerated track:

• Tier 1: same day
• Tier 2: 2 days
• Tier 3: 1 week
• Tier 4: 2 weeks
• (Skip tiers 5–6 — you don’t have time before interviews)

What This Track Cannot Buy You

• Deep competitive-programming intuition (Phase 7)
• Grandmaster-level pattern recognition (Phase 12)
• Long-term retention of all 270 problems (you’ll forget ~30% within 3 months without continued review)
• The kind of polish that comes from 6+ months of practice

If you finish Week 12 and your interview is delayed by 8+ weeks, switch to the 6-month track for the remaining time. Use the buffer to backfill Phase 7 basics and harden weak patterns.

6-Month Serious Track

Audience: You’re targeting strong Big Tech readiness. You can put in 15–25 hours/week sustainably for 6 months.

Tradeoffs:

• You will cover Phase 7 (competitive) selectively — not full grandmaster prep.
• You will get to “consistently solves FAANG hards in 45–60 minutes” with strong follow-ups.
• You will have meaningful depth in your primary language’s runtime.
• This is the recommended track for most readers.

Sufficient for: all FAANG levels including senior, infrastructure, platform, distributed systems, most backend specialties.

Daily Cadence

• Weekday: 2–3 hours
  • 60 min: new content (read + 1 lab or 2–3 concept docs)
  • 60 min: problem solving (2–4 problems)
  • 30 min: review queue
• Saturday: 4 hours
  • 1 mock interview (90 min)
  • 2 hours problem solving
  • 30 min: failure analysis + review
• Sunday: 2 hours
  • Re-solves at Tier 4–5
  • Weakness drilling

Total: 18–22 hours/week

Monthly Milestones

Month 1 — Foundations (Weeks 1–4)

Cover: Phase 0 + Phase 1 fully, Phase 9 (your primary language) partially.

• Week 1: Phase 0 (all 7 labs), 25 Easy problems
• Week 2: Phase 1 DS docs (arrays, strings, hashmaps, stacks, queues, linked lists), Phase 1 runtime (stack vs heap, scope, value/reference, mutability), 30 problems
• Week 3: Phase 1 DS continued (heaps, sorting, binary search, recursion, basic trees, basic graphs, basic DP), 30 problems, 2 labs
• Week 4: Phase 1 runtime complete (hash collisions, iterator invalidation, GC, memory leaks, deep/shallow copy), Phase 9 your-language (first half), 30 problems, 3 labs

End-of-month: all Phase 1 mastery checks pass. 1 mock at Easy level, scored 7+/10.

Volume: ~115 problems, 10+ labs.

Month 2 — Patterns Mastery (Weeks 5–8)

Cover: Phase 2 fully, Phase 9 your-language fully.

• Week 5: two pointers, sliding window, prefix sums, difference arrays, hashing, sorting+greedy. 5 problems per pattern.
• Week 6: binary search, binary search on answer, monotonic stack, monotonic queue, intervals, linked list manipulation. 5 per pattern.
• Week 7: tree DFS/BFS, graph DFS/BFS, topological sort, union find. 5 per pattern. 3 labs.
• Week 8: backtracking, basic DP, 1D DP, 2D DP, knapsack basics, subsequence DP, string DP, trie, heap top-K, K-way merge. 4 per pattern.

End-of-month: mastery check on all 28 patterns. 4 mocks (Easy-Medium-Medium-Medium-Hard).

Volume: ~140 problems, 9 labs.

Month 3 — Graphs + DP Deep (Weeks 9–12)

Cover: Phase 4 fully, Phase 5 fully (except convex hull / Knuth optimization, those are Month 6).

• Week 9: Phase 4 fundamentals (BFS variants, DFS, Dijkstra, Bellman-Ford, Floyd-Warshall, topo). Solve 30 graph problems. 2 graph labs.
• Week 10: Phase 4 advanced (SCCs, bridges/articulation, MST, bipartite, max flow basics, graph modeling). Solve 25. 3 graph labs.
• Week 11: Phase 5 categories: 1D, 2D, knapsack, LIS, edit distance, palindrome, string DP. Solve 25. 3 DP labs (full brute→memo→tab→space progression).
• Week 12: Phase 5 categories: tree DP, interval DP, bitmask DP, digit DP (intro), DP on DAGs, game DP. Solve 25. 3 DP labs.

End-of-month: all of Phase 4 + Phase 5 mastery checks. 4 mocks (Medium-Medium-Medium-Hard mix).

Volume: ~110 problems, 11 labs.

Month 4 — Greedy, Advanced DS, Practical Engineering (Weeks 13–16)

• Week 13: Phase 6 fully (greedy choice, exchange arg, cut property, invariants, monovariants, amortized analysis). 6 greedy labs (with proofs). 20 greedy problems.
• Week 14: Phase 3 (segment tree, Fenwick tree, sparse table, KMP, Z, rolling hash, trie variants, bit manipulation, bitmask DP, meet-in-the-middle). 20 problems. 3 advanced DS labs.
• Week 15: Phase 8 first half (LRU, LFU, rate limiter, task scheduler, thread pool, job queue, autocomplete, log parser, file dedup). 9 labs with full follow-up answers.
• Week 16: Phase 8 second half (consistent hashing, message dispatcher, pubsub, timer wheel, KV store, retry/backoff, circuit breaker, metrics, web crawler, in-memory FS). 10 labs.

End-of-month: Phase 3 + Phase 6 + Phase 8 (most of it) complete. 4 mocks including 1 Big Tech phone screen.

Volume: ~80 problems, 28 labs.

Month 5 — Hard Problems + Concurrency + Senior-Level Skills (Weeks 17–20)

• Week 17: Phase 8 final 4 labs + Phase 10 (testing/debugging concept docs). 5 testing/debugging labs. 15 problems.
• Week 18: Concurrency deep dive — re-read Phase 9 concurrency sections, solve 5 concurrency-flavored problems, do mock-11 twice. 15 problems.
• Week 19: Hard problem week — 25 LeetCode Hards across all patterns. 1 mock per day (5 mocks).
• Week 20: Phase 7 selectively (modular arithmetic, sieve, binary exponentiation, combinatorics, sweep line, coordinate compression — skip ICPC-only topics). 20 problems including 8 from Codeforces Div 3. 1 mock.

End-of-month: all of Phase 8, Phase 10, parts of Phase 7. 8 mocks total.

Volume: ~100 problems including ~25 hards.

Month 6 — Polish, Mock Marathon, Production Awareness (Weeks 21–24)

• Week 21: Mock-heavy week. 5 mocks (mix mock-05, 06, 07, 09, 11). Failure analysis on each. 15 problems focused on top failure category.
• Week 22: Phase 12 selective topics (only those relevant to your role) — for backend/platform: max flow modeling, advanced combinatorics inclusion-exclusion. For systems: nothing additional, focus on Phase 8 polish. 20 problems.
• Week 23: Re-solve marathon — re-solve all Tier 5 and Tier 6 problems. Verify READINESS_CHECKLIST.md honestly. 3 mocks.
• Week 24: Light week. 2 mocks. 10 problems. Rest. Final readiness check.

End-of-program: READINESS_CHECKLIST.md fully passed.

Volume: ~50 problems, 13 mocks across the month.

Aggregate Volume

Review / Spaced Repetition

Full 6-tier schedule from SPACED_REPETITION.md:

• Tier 1: same day
• Tier 2: 2 days
• Tier 3: 1 week
• Tier 4: 2 weeks
• Tier 5: 1 month
• Tier 6: 3 months

By Month 6 you should have ~50–80 Tier 6 graduates.

Mock Schedule

Required mocks across the program (see phase-11-mock-interviews/):

Revision Plan

Weekly: Friday evening — skim review log, identify the week’s failure pattern. Monthly: Last weekend — aggregate failures, identify top 3 categories, dedicate next month’s Sunday drilling to category #1. Bi-monthly: End of months 2, 4, 6 — do a “blind mock” with a problem you’ve never seen, no warmup. Score honestly.

What This Track Buys You

• ~600 deeply-owned problems
• All 28 patterns recognizable in <2 minutes
• ~35 production-style labs with full follow-up answers
• Strong concurrency + runtime depth in your primary language
• Genuine readiness for FAANG senior-level coding interviews
• 30+ mock interviews of practice — pressure tolerance is real

What It Does Not Buy You

• Codeforces Div 1 / AtCoder AGC level (you’d need Phase 7 + 12 fully)
• Quant/HFT-level math depth (math heavy, beyond Month 5 scope)
• Compiler/runtime team specialty (you’d need Phase 9 fully across multiple languages)

12-Month Elite Track

Audience: Top-tier targets. Senior/staff/principal practical, FAANG L6+, Jane Street / Citadel / Two Sigma, distributed systems specialty teams, compiler/runtime teams, or competitive programmers building toward Codeforces 2100+.

Commitment: 15–20 hours/week sustained for 12 months. Not a sprint.

This track will get you to:

• Phase 7 + Phase 12 substantial depth
• Codeforces Div 2 reliable, Div 1 attempt-capable
• Multi-language runtime fluency in primary + 1 secondary
• Production-system thinking comparable to a working senior/staff engineer
• The specific gap between “Big Tech ready” and “elite-tier ready”

Annual Phase Map

Daily Cadence

• Weekday: 2 hours
• Saturday: 5 hours (mock + problems + labs)
• Sunday: 3 hours (review + drilling)
• Total: 17–18 hours/week

You will scale up in Months 8–11 to 22 hours/week temporarily.

Monthly Detail

Month 1 — Phase 0 + Phase 1

Identical to Month 1 of 6-Month Serious, but with extra depth on runtime docs (read all 10) and an additional 30 Easy problems for fluency.

Volume: 130 problems, 12 labs, 1 mock.

Month 2 — Phase 2 (Patterns)

• All 28 pattern docs read in detail
• 8 problems per pattern (vs 5 in Serious track)
• Every pattern: write a personal template after solving the 8 problems
• 5 mocks across the month

Volume: 224 problems, 9 labs, 5 mocks.

Mastery check: Can derive each pattern’s template from memory in <5 minutes.

Month 3 — Phase 4 (Graphs)

• All 21 graph algorithms with implementation
• All 9 product-style labs
• 60 graph problems (mix of LeetCode + Codeforces Div 3 graph problems)
• 4 mocks

Volume: 60 problems, 9 labs, 4 mocks.

Mastery check: Can implement BFS / DFS / Dijkstra / Bellman-Ford / Floyd-Warshall / Kruskal / Prim / Kosaraju / Tarjan from scratch error-free in <12 minutes each.

Month 4 — Phase 5 (Dynamic Programming)

• All 22 DP concept + category docs
• All 10 DP labs with full progression (brute → memo → tab → space)
• 80 DP problems
• Every problem you solve: explicitly state recurrence + base case + evaluation order before coding
• 4 mocks (DP-heavy)

Volume: 80 problems, 10 labs, 4 mocks.

Mastery check: Can derive state + transition for unseen DP problems in <8 minutes.

Month 5 — Phase 3 (Advanced DS) + Phase 6 (Greedy/Proofs)

• All 24 advanced DS docs
• All 9 advanced DS labs
• All 7 greedy concept docs + all 6 labs (with proofs)
• 50 problems mixing advanced DS and greedy
• 4 mocks

Volume: 50 problems, 15 labs, 4 mocks.

Mastery check: Can implement segment tree (with lazy propagation), Fenwick tree, KMP, rolling hash, trie, treap from scratch.

Month 6 — Phase 8 (Practical Engineering) + Phase 10 (Testing/Debugging)

• All 23 practical engineering labs
• Every lab includes: working implementation + unit tests + smoke tests + concurrency tests where relevant + answers to all 13 standard follow-ups
• All 13 testing/debugging concept docs + all 5 labs
• Property-based test 5 implementations
• 30 problems
• 5 mocks (mix mock-08 staff practical, mock-10 system-heavy, mock-11 concurrency)

Volume: 30 problems, 28 labs, 5 mocks.

Mastery check: Can build any of (LRU, rate limiter, autocomplete, KV store, thread pool) from scratch in 45 minutes with tests.

Month 7 — Phase 9 (Language & Runtime)

• Primary language: read entire track end to end. Take written notes. Solve 5 problems per major topic targeting the gotchas.
• Secondary language: read 50%+ of the track. Solve 20 problems in this language to build fluency.
• 30 problems total in primary language (focused on runtime gotchas: overflow, recursion limits, hash adversarial, GC pressure, concurrency)
• 4 mocks including 2 mock-09 (runtime/language deep dives)

Volume: 50 problems, 0 labs (concept-heavy month), 4 mocks.

Mastery check: Can fluently explain stack vs heap, GC behavior, hashmap internals, concurrency model for both languages.

Month 8 — Phase 7 First Half

Competitive programming acceleration starts here. Move to Codeforces full-time for problem solving (LeetCode for review only).

• Topics: fast I/O, modular arithmetic, GCD/LCM, sieve, prime factorization, modular inverse, combinatorics, binary exponentiation, matrix exponentiation, geometry basics, coordinate compression
• Codeforces Div 3 → solve 6 contests (virtual or real). Goal: solve 4–5 problems per Div 3.
• AtCoder Beginner Contest: solve 4 contests. Goal: solve 5 of A–F.
• 1 mock per week (varied — competitive-flavored mock-13)

Volume: ~80 problems (Codeforces + AtCoder), 6 labs, 4 mocks.

Mastery check: Solve Codeforces 1500–1700 rated problems consistently within contest time.

Month 9 — Phase 7 Second Half

• Topics: sweep line, offline queries, Mo’s algorithm, parallel binary search (overview), randomized stress testing, interactive problems, game theory (Nim, Sprague-Grundy)
• Codeforces Div 2 → 6 virtual contests. Goal: solve A–C reliably, attempt D.
• AtCoder Regular Contest → 3 contests, attempt A–C.
• Implement a stress-testing harness for 5 problems
• 4 mocks including mock-13 (competitive hard) twice

Volume: ~70 problems, 4 mocks.

Mastery check: Codeforces Div 2 ABC reliable. D attempted and sometimes solved.

Month 10 — Phase 12 (Selective)

Pick topics by role:

Backend/platform:

• Max flow modeling, min-cost max-flow overview
• Advanced combinatorics + inclusion-exclusion
• Randomized algorithms

Distributed systems:

• Persistent data structures
• Consistent hashing deep
• Lockless / wait-free data structures (research)

Compiler/runtime:

• Suffix automaton
• Heavy-light decomposition
• Constraint solving / SAT-like reasoning

Quant/HFT:

• FFT/NTT
• Computational geometry
• Probability DP + expected value
• Game theory deep

Pure competitive:

• HLD, centroid decomposition, segment tree beats, FFT/NTT, suffix automaton

Pick 5–7 topics. Read deeply. Implement reference code. 3 labs from Phase 12.

Volume: 30 problems (very hard / CP-hard), 3+ labs, 4 mocks.

Mastery check: can articulate selected topics + implementation risks; have working reference implementations.

Month 11 — Mock Marathon

This is the highest-pressure month.

• 4 mocks per week (16 total)
• Mix all 14 mock types — including grandmaster final boss (mock-14) at least twice
• Failure analysis on every mock
• Every Sunday: aggregate failure pattern, drill the top category Mon–Wed
• 60 problems (almost entirely focused on weak areas surfaced by mocks)

Volume: 60 problems, 16 mocks.

Month 12 — Polish, Re-solve, Final Readiness

• Week 49: Re-solve all Tier 5 + Tier 6 problems. Aim for 80+ Tier 6 graduates.
• Week 50: 4 cold blind mocks (no warmup, varied difficulty). Score brutally honestly.
• Week 51: Address any remaining gaps. Light schedule (10 hours total).
• Week 52: Rest, sleep, exercise. 1 final readiness check via READINESS_CHECKLIST.md. Interview confidently.

Volume: 30 re-solves, 4 mocks, 1 readiness audit.

Aggregate Volume

Contest Practice (unique to this track)

By end of Month 9, you should have completed:

• 12+ Codeforces Div 3/4 contests
• 6+ Codeforces Div 2 contests
• 6+ AtCoder Beginner Contests
• 3+ AtCoder Regular Contests

Goal Codeforces rating after 12 months: 1700–1900 (Expert range).

What Distinguishes This Track

vs 6-month Serious:

• ~1.5× the problems
• 2× the labs (especially in Phase 7 / 12)
• 2× the mocks (mostly in Months 8–11)
• Real contest experience (vs 0 in 6-month track)
• Multi-language runtime depth
• Phase 12 awareness (selective implementation)

vs Competitive-only training:

• This track does NOT skip practical engineering, system thinking, communication, or runtime depth
• A candidate trained purely on competitive programming often struggles in mock-08 (staff practical) and mock-10 (system-heavy) — this track does not have that gap

Honest Limitations

Even after this track:

• You will not reach grandmaster (CF 2400+) — that requires sustained contest practice for years
• You will not be a domain expert in a specific area (e.g., compilers, distributed consensus) — that requires actual work on those systems
• 12 months of part-time prep cannot replicate 5 years of full-time engineering experience

What it can do is take you from intermediate to elite-candidate level — enough to interview confidently for very hard roles and have a fighting chance.

6-Month Serious Track — Implementation

This is the execution layer for schedules/6_MONTH_SERIOUS.md. The schedule tells you what to study and when. This folder is the actual substance — curated flagship problems, original company-sourced problems, graduated reading, proof-first solutions, and senior/staff/principal-level signal layers.

What This Is (And Is Not)

This IS:

• 91 hand-picked flagship problems across 20 active weeks
• 8–10 ORIGINAL problems sourced from real Amazon/AWS, Google, Meta, Microsoft interview intelligence (not on LeetCode)
• A graduated 15-section reading layout per problem: approach → hints → insight → company adversarial → level delta → follow-ups
• Python solutions with brute-force comparators and stress tests
• Above-FAANG difficulty content targeting senior, staff, and principal interviews

This is NOT:

• A duplicate of LeetCode Premium. You should have LC Premium. We never restate problem statements or constraints — those are one click away.
• Every problem from the 6-month schedule (~595). The other ~500 are listed as “Problem Bank” in each week’s README — work them on LC after you own the flagship.
• A passive read. Each problem has an Attempt Gate — you set a timer and try the problem cold before reading anything else.

Why This Exists

LeetCode editorials give you code. They do not give you:

1. The exchange argument that proves the greedy works
2. The invariant that the two-pointer maintains
3. The misleading example a Google interviewer will use to trap you on this exact problem
4. The scorecard language the interviewer writes when you do (or do not) ace it
5. The Level Delta: what a Mid vs Senior vs Staff vs Principal answer looks like for this same problem
6. The production reality: if this ran at 10M RPS, what would break first?
7. The Anti-pattern: the wrong-but-tempting approach that catches 70% of candidates, with exact bug location
8. The original problem Amazon will ask you that has never appeared on LeetCode

This track provides all of those.

How To Use

1. Read HOW_TO_USE.md — the graduated reading protocol
2. Read FRAMEWORK.md once if you have not — every “How to Approach” section here references its 16 steps
3. Start at month-01-foundations/, week 01, problem 01. Do not skip ahead.
4. For each problem: Attempt Gate first (20-min timer, cold), then graduate through the README sections
5. Stress-test your solution: python solution.py runs the brute-vs-optimal comparator
6. Log every solve in your tracking spreadsheet per SPACED_REPETITION.md

Problem Index (All 91)

Month 1 — Foundations (20 problems)

Month 2 — Patterns Mastery (20 problems)

Month 3 — Graphs + DP Deep (20 problems)

Month 4 — Greedy, Advanced DS, Practical Engineering (20 problems)

Month 5 — Hards + Concurrency + Above-FAANG (10 problems)

Month 6 — Polish + Mock Marathon

Cross-References to the Rest of the Workspace

• FRAMEWORK.md — universal 16-step problem-solving framework
• CODE_QUALITY.md — quality bar every solution.py must meet
• COMMUNICATION.md — what to say in interviews
• FAILURE_ANALYSIS.md — 16-category failure taxonomy
• SPACED_REPETITION.md — 6-tier review schedule
• READINESS_CHECKLIST.md — final binary checklist
• phase-02-patterns/ — concept docs for patterns (3Sum, sliding window, etc.)
• phase-04-graphs/ — graph algorithm concept docs
• phase-05-dp/ — DP concept docs and labs

Honest Promise

If you complete every problem in this track honestly — Attempt Gate respected, hints used sparingly, follow-ups answered before reading the answers, stress tests passing, every “When to Move On” checklist green — you will be in the top 5% of candidates entering senior, staff, and principal interview loops at Amazon, Google, Meta, Microsoft, Apple, and infrastructure-specialty companies.

If you skip the Attempt Gates, peek at hints early, or skim the Level Delta sections without honestly self-assessing — this is just a list of problems you’ve seen. Seen ≠ owned. Owned is what gets offers.

How To Use This Track — The Graduated Reading Protocol

Every problem folder has three files. They are meant to be read in a specific order with specific gates between them. Reading them out of order destroys the value.

The Three Files

pXX-problem-name/
  README.md       ← Graduated reading: 15 sections, each gated
  solution.py     ← Brute + optimal + stress test (Python, runnable)
  hints.md        ← 5 progressive hints (only opened when stuck)

The Per-Problem Reading Protocol

Phase 1 — Cold Attempt (mandatory)

1. Open README.md, read only sections 1–2 (Quick Context + LeetCode Link/Attempt Gate)
2. Click the LeetCode link, read the problem statement on LC
3. Set a 20-minute timer. Code on paper or in a scratch file. No IDE autocomplete that helps with the algorithm. No reading further in README.md. No hints.md.
4. If you solve it: write down your time and approach. Now jump to Phase 3.
5. If 20 min passes: write down where you got stuck. Move to Phase 2.

Why the gate? You cannot build pattern-recognition by reading approaches. You build it by failing to find approaches, then learning the gap. If you skip the cold attempt, you are training your recognition memory, not your derivation skill. Interviews test derivation.

Phase 2 — Hint Ladder (only if stuck)

Open hints.md. Read one hint. Set another 10-min timer. Try again.

• Solved after Hint 1 → write down which insight unlocked it. Move to Phase 3.
• Still stuck after 10 min → next hint.
• After Hint 5 without solving → you’ve hit the conceptual gap. Open README.md section 4 (“How to Approach”) and read straight through. Then Phase 3.

Rule: never read two hints back to back. Always 10 minutes between hints.

Phase 3 — The Real Learning

Now read README.md sections 3–15 in order. This is where the value is.

• Section 3 (Prerequisites): if any link goes to a phase lab you haven’t done, do that lab first
• Section 4 (How to Approach): compare to YOUR approach. Where did you diverge? Why?
• Section 6 (Deeper Insight): the proof or invariant. You must be able to restate this in your own words before moving on.
• Section 7 (Anti-Pattern): “did I almost do this?” — if yes, this is a flag for your weakness log
• Section 10 (Company Context): mental note of how the company you’re targeting twists this problem
• Section 12 (Level Delta): honestly: which level was your answer? Mid, Senior, Staff, or Principal?
• Section 13 (Follow-ups): cover the answer with your hand. Try each follow-up. Then read the answer.

Phase 4 — Code & Test

1. Open solution.py. Read the brute force. Read the optimal.
2. Close the file. Re-implement the optimal from scratch in your own scratch.
3. Diff your re-implementation against the reference. Identify every difference. Some differences are style (fine). Some are bugs (not fine).
4. Run the stress test: python solution.py. It must pass.
5. Now run your own implementation against the stress test. It must also pass.

Phase 5 — Move-On Gate

Walk through Section 9 (“When to Move On”) — the binary checklist. Every box must be honestly checked. If even one is no, you stay on this problem (re-do tomorrow). No exceptions.

Log the solve in your tracking spreadsheet:

• Date, problem, time-to-solve, hint depth used (0–5), follow-ups answered correctly (count/total), Level Delta self-assessment
• Schedule next review per SPACED_REPETITION.md

What Each README.md Section Is For

Common Mistakes (Do Not Do)

1. Reading README.md before the Attempt Gate. Destroys the entire training value.
2. Reading all hints at once. Same problem.
3. Skipping the “re-implement from scratch” step. Reading code ≠ writing code.
4. Skipping the Level Delta self-assessment. This is the single highest-signal section.
5. Skimming Section 10 (Company Context). This is where the differentiated content lives.
6. Marking “When to Move On” green without honestly checking each box. Calcifies bad habits.
7. Not stress-testing your own implementation. A solution that passes LC may have a bug a stress test catches.
8. Skipping originals (p75, p77, p79, p85, p87, p90). These are the highest-value problems in the track. They’re original because they don’t exist on LC — meaning your competition hasn’t seen them either.

Time Budget Per Problem

Plan accordingly when fitting problems into the weekly schedule.

The One Rule

If you remember nothing else: the Attempt Gate is not optional. Every other shortcut is recoverable. Skipping the cold attempt is not — it permanently degrades the training signal for that problem.

Month 1 — Foundations

Weeks 1–4 · 20 flagship problems · ~115 LC Bank problems · 1 mock

Goals

By end of month, you can:

• Execute the 16-step framework on every problem without thinking about it
• Solve any LC Easy in <12 min with full edge-case coverage
• Solve straightforward Mediums (array/string/hashmap/tree/basic-DP) in <30 min
• Explain hashmap collision handling, GC, stack vs heap in your primary language
• Pass mock-02 (Easy) at 7+/10

Weekly Map

End-of-Month Gate

• All 20 flagship problems: Section 9 (“When to Move On”) checklist green
• All Phase 1 mastery checks in phase-01-foundations/README.md pass
• mock-02 scored 7+/10
• Tracking spreadsheet has 20 entries with Level Delta self-assessment

If any item fails: do NOT enter Month 2. Repeat the weakest week’s drilling.

Why These 20 Problems

These are the 20 most-asked Easy-and-low-Medium problems in 2024–2025 Big Tech interview loops (cross-referenced against company tag data, real-time interview reports, and recruiter intel). They are the floor. If you cannot solve all 20 fluently, you will fail the phone screen — not because they are hard, but because failing an Easy in 12 minutes is an instant no-hire signal.

Week 1 — Execution Baseline + First Patterns

Days 1–7 · 5 flagship problems · ~25 LC Bank · 0 mocks

Goals

• Internalize the 16-step framework on trivial problems (so you can use it on hard ones)
• Two-pass over Phase 0 labs
• Acquire HashMap-1-pass, Stack-validation, Greedy-1-pass, Two-pointer-from-end, 1D-DP-intro patterns

Daily Schedule

LC Bank (Problems to solve on your own after flagship)

LC 217 (Contains Duplicate), 169 (Majority Element), 268 (Missing Number), 53 (Maximum Subarray), 136 (Single Number), 283 (Move Zeroes), 26 (Remove Duplicates from Sorted Array), 27 (Remove Element), 1 (Two Sum — variant), 9 (Palindrome Number), 14 (Longest Common Prefix), 28 (strStr — naive), 35 (Search Insert Position), 66 (Plus One), 67 (Add Binary), 69 (Sqrt(x) — binary search intro), 88 (Merge Sorted Array — variant), 100 (Same Tree), 101 (Symmetric Tree), 104 (Maximum Depth — preview), 108 (Sorted Array → BST), 112 (Path Sum), 118 (Pascal’s Triangle), 226 (Invert Binary Tree), 543 (Diameter of Binary Tree).

Readiness Gate

• All 5 flagship problems Section 9 checklists green
• 25+ Bank problems solved unaided
• Framework Steps 1–9 executed audibly (talk through) on at least 10 problems
• No off-by-one errors on 5 consecutive binary-search-flavored problems
• Honest self-assessment: Level Delta = Mid or above on at least 3 flagships

p01 — Two Sum

Source: LeetCode 1 · Easy · Topics: Array, Hash Table Companies (2024–2025 frequency): Amazon (very high), Google (high), Meta (high), Apple (medium), Microsoft (medium), Bloomberg (very high) Loop position: phone screen warmup, or first 10 min of onsite to calibrate

1. Quick Context

This is the most-asked Easy in Big Tech history. The interviewer is not testing whether you can solve it — they expect you to solve it in <8 minutes. They are testing whether you:

1. Clarify before coding (duplicates? multiple answers? sorted?)
2. State the brute force out loud before optimizing
3. Pick the right optimal (one-pass hash, not two-pass)
4. Handle the “what about the same element twice” edge case
5. Communicate cleanly through a problem you’ve obviously seen before

What it looks like it tests: array iteration. What it actually tests: disciplined communication under “I’ve done this a million times” complacency. Senior candidates fail this by going too fast and skipping clarifications. The interviewer is watching for the framework, not the answer.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/two-sum/

STOP. Set a 15-minute timer. Code it cold in a scratch file. Do not read past this section until you have either solved it or the timer expired.

If you’ve solved Two Sum before: do it again anyway, and time yourself. Target: 6 min including narration. If you’re over 8 min, you have a framework/communication gap, not an algorithm gap — and that gap will kill you on harder problems.

3. Prerequisite Concepts

• Hash table average O(1) lookup + the assumption that makes it true (phase-01 §3 HashMap Mastery)
• “Complement search” pattern: instead of looking for pairs, transform to lookup of (target − x)
• In your primary language: what hash collision behavior is, what hash resize cost is — see phase-09

4. How to Approach (FRAMEWORK Steps 1–9 applied)

Step 1 — Restate: “Given an integer array and a target integer, return the indices of two distinct elements that sum to target. Exactly one valid pair exists per problem statement.”

Step 2 — Clarify (ask out loud, do NOT skip even though it’s Easy):

• “Can the same element be used twice?” (No — indices must be distinct.)
• “If multiple pairs sum to target, which one do I return?” (Problem says exactly one solution — but in real interviews they may relax this; ask.)
• “Can the array be empty / size 1?” (Per constraints, N ≥ 2.)
• “Are values bounded? Can they be negative?” (Per LC, yes, both negative and positive in int32 range.)
• “Is the array sorted?” (No. If it were, you’d use two pointers — explicitly call this out; this is a senior signal.)
• “Return indices or values?” (Indices, in any order.)

Step 3 — Constraints: N up to 10^4 in classic statement. O(N²) brute fits, but O(N) is expected. With N up to 10^4, O(N²) = 10^8 — borderline, will get TLE on some servers.

Step 4 — Examples (build your own):

• [2,7,11,15], target=9 → [0,1] (the given one)
• [3,3], target=6 → [0,1] ← critical: the “same value, different indices” case
• [-3,4,3,90], target=0 → [0,2] (negative handling)
• [1,2,3,4], target=100 → does not occur per statement, but ask: “if no solution, what do I return?”

Step 5 — Brute Force: Nested loop. For each i, check every j > i. O(N²) time, O(1) space.

Step 6 — Brute Force Complexity: Time O(N²), space O(1). Trivially correct. State this out loud BEFORE optimizing.

Step 7 — Pattern Recognition: “Given an array, find a pair satisfying a property” + “complement is computable” + “order of result doesn’t matter” → HashMap complement search. (Sorted + ordered → two pointers. Unsorted + complement-computable → HashMap.)

Step 8 — Optimize: Walk the array once. For each x at index i, compute complement = target − x. If complement is in the map, return (map[complement], i). Else add x → i to the map. One pass, not two. Two-pass works but signals weaker intuition.

Step 9 — Prove correctness: Loop invariant: after processing index i, the map contains exactly {nums[0..i] : their indices} for every distinct value (or the latest index for duplicates, but since exactly one solution exists, duplicates can only be the answer pair — and at index j, the complement was stored at index i < j, so we find it).

5. Progressive Hints

If you’re stuck for more than 5 minutes, open hints.md and read one hint only. Set another 5-min timer between hints.

6. Deeper Insight — Why It Works

The transformation: “Find two numbers summing to T” is a 2D search (i, j pairs) → O(N²). By computing T − nums[i] for each i, we reduce to a 1D lookup (“does this value exist?”) which is O(1) amortized with a hash table. The hash table is the data structure that turns 2D pair-search into 1D existence-search. This is the master pattern for entire problem families: 3Sum, 4Sum, Subarray-Sum-K, etc., all reduce 1 dimension via complement-hashing.

The single-pass insight: You don’t need to load the full array into the map first. By the time you encounter the second element of the answer pair, the first one has already been stored. So insert AFTER you check — never before, or [3,3] breaks (you’d find 3 → 0 and return [0,0], two equal indices).

Order matters: check first, insert second. Reversing this is the single most common bug. The map state at step i represents “everything seen STRICTLY BEFORE i” — that’s the invariant.

7. Anti-Pattern Analysis

Wrong-but-tempting #1 — Two-pass with enumerate:

d = {x: i for i, x in enumerate(nums)}
for i, x in enumerate(nums):
    j = d.get(target - x)
    if j is not None and j != i:
        return [i, j]

This works but: (a) O(N) extra memory written then read again, (b) the j != i guard signals you didn’t think about why one-pass avoids the issue, (c) for duplicates [3,3], the dict only stores the last index — works only because j != i saves you. Two-pass is a code smell that says “I memorized the pattern but didn’t internalize the invariant.”

Wrong-but-tempting #2 — Sort then two-pointer:

sorted_nums = sorted(enumerate(nums), key=lambda p: p[1])
# ... two-pointer scan

Works, but O(N log N) when O(N) exists. Some candidates do this because two-pointer is their hammer. At Google in particular, choosing N log N when N exists is a signaled-down on the algorithmic complexity rubric.

Wrong-but-tempting #3 — Brute force “to be safe”: The brute force fits N ≤ 10⁴ barely. If the interviewer expands the constraint to 10⁵, brute force times out. They WILL expand the constraint to test you — be ready.

8. Skills & Takeaways

Generalizable pattern: Complement search via HashMap. Any time you see “find pair/triple/group summing or differing or relating to value V”, first ask: can I express the missing piece as a function of what I have? If yes, HashMap that function’s range.

Analogous problems (do these on LC after):

• LC 167 — Two Sum II (sorted input — uses two pointers instead; teaches when NOT to use hashmap)
• LC 653 — Two Sum IV BST (BFS + set; same complement pattern, different traversal)
• LC 1 vs LC 15 (3Sum) — the recursive extension; outer loop fixes one element, reduces to 2Sum
• LC 560 — Subarray Sum Equals K (the prefix-sum complement variant — same idea, applied to running sums)
• LC 454 — 4Sum II (split into two halves, hash one half, lookup complements of the other — meet-in-the-middle flavor)

When NOT to use this: Sorted input (two pointers is O(1) space, hashmap is O(N)). Streaming input where you can’t afford O(N) memory.

9. When to Move On (binary; must all be YES)

• I solved p01 unaided in <8 min including narration on the second attempt
• I can state the loop invariant of one-pass Two Sum without looking
• I can explain why “check first, insert second” matters, with the [3,3] example
• I can name when two-pointer is preferred over hashmap (sorted input, O(1) space requirement)
• I implemented this from scratch and my version passes stress_test() in solution.py
• I solved LC 167 (Two Sum II) and articulated why the optimal approach changed
• I solved LC 560 (Subarray Sum K) and recognized the same complement-hashing pattern

If any unchecked: redo tomorrow before moving to p02.

10. Company Context

Amazon (LP-heavy; coding bar = “are bugs going to ship?”)

• The framing: Often given as “given a list of Order objects with a price field, find two orders whose prices sum to the target promo discount.”
• Misleading example: They’ll give you [5, 5, 5, 5], target=10. Many candidates lock onto “return the first two indices that work” — but Amazon interviewers want you to ASK whether you should return any valid pair or the first in some defined order. Asking shows Customer Obsession (knowing the requirement).
• Adversarial extension: “Now there could be millions of orders streamed one at a time. How does your solution change?” → streaming with a HashSet, return the first matching pair.
• What they want to hear: “Let me clarify the requirements before I optimize.” Verbatim phrases like “Let me first state the brute force so we have a baseline” earn rubric points.

Google (algorithmic complexity is a hard rubric line)

• The framing: Often the cleanest, just the original problem.
• Misleading example: A small-N example where O(N²) clearly fits. Google interviewers do this to see if junior candidates will say “brute force is fine” and stop. The right move: “Brute force fits this size, but I want to do better as a habit — and to handle the extension where N is 10⁶.”
• Adversarial extension: “Return all pairs that sum to target.” Now it’s not 1 answer; you must dedupe pairs (3Sum-style logic).
• What they want to hear: Explicit complexity for brute and optimal, stated separately. “O(N²) brute → O(N) one-pass hashmap, O(N) extra space.”

Meta (heavy on follow-ups; expect 3–4 in 25 min)

• The framing: “Two Sum, then variants in rapid succession.”
• Misleading example: They start with the canonical example, then immediately follow up: “Now what if the array is sorted?” If you stayed on hashmap, you scored less than the candidate who pivots to two-pointers.
• Adversarial extension: “What if duplicates are allowed in input AND we want all unique pairs?” → 2Sum-with-duplicates → introduces dedup via sort or a counted-set.
• What they want to hear: Recognition that the optimal algorithm depends on input properties. The phrase “if the input were sorted, I’d use two pointers” wins them over.

Microsoft (clarity + cleanliness over speed)

• The framing: Phone screen warmup.
• Misleading example: None — Microsoft tends to be straightforward here.
• Adversarial extension: “Now make it work for any K-Sum” (K is a parameter).
• What they want to hear: Clean function decomposition, clear variable names, edge-case enumeration. Microsoft phone screens reward boring, correct code.

Bloomberg (financial framing — be ready)

• The framing: “Given a list of trade prices and a settlement amount, find two trades that exactly settle to the amount.”
• Misleading example: Includes negative prices (refunds). Candidates who hard-code i < j ordering may break on negatives if they switch to a sort approach mid-stream.
• What they want to hear: Explicit “I’m assuming negative values are allowed; my hash approach handles them naturally.”

11. Interviewer’s Lens

The scorecard line that gets you the offer: “Candidate demonstrated framework discipline on a trivial problem, suggesting it will scale to hard ones.”

The scorecard line that loses you: “Skipped clarifying questions; rushed to known answer; did not test [3,3]; missed senior signal opportunity.”

12. Level Delta

Honest self-assessment: Which level was YOUR answer? If “Mid”, you have 4 sections to add to your toolkit. If “Senior” — good baseline; aim for Staff on the next 5 problems.

13. Follow-up Questions & Full Answers

Follow-up 1: “What if the array is sorted?”

Signal sought: Do you recognize that input properties change the optimal algorithm?

Full answer: “If sorted, I’d switch to two pointers — left=0, right=N-1. If sum > target, decrement right; if sum < target, increment left; if equal, return. O(N) time, O(1) space (better than hashmap’s O(N) space). The correctness comes from monotonicity: incrementing left only increases the sum; decrementing right only decreases. We never miss the answer because at each step, the eliminated half cannot contain the answer.”

Follow-up 2: “What if there are multiple valid pairs and we want all unique ones?”

Signal sought: Can you handle dedup without explosive complexity?

Full answer: “Two approaches. (a) Sort + two pointers + skip duplicates on both sides — O(N log N) time, O(1) extra. (b) Hashmap + use a set of frozensets to dedup result pairs — O(N) time, O(N) extra. Approach (a) is preferred unless we cannot mutate input. The key insight: dedup happens by skipping equal adjacent values after sorting, not by post-filtering.”

Follow-up 3: “Now there are billions of integers streamed one at a time, infinite stream. Detect any sum-pair as fast as possible.”

Signal sought: Streaming / unbounded-input thinking.

Full answer: “Use a HashSet (not Map — we just need existence). For each incoming x: check (target − x) in set; if found, emit the pair; else add x to set. O(1) per element, O(N) total memory grows unboundedly. For unbounded memory: use a Bloom filter as a prefilter (false positives OK; we verify by querying upstream), bounded memory at cost of occasional false alarms. If we need bounded memory AND zero false positives, we accept that we may miss pairs — fundamentally we cannot remember an arbitrary stream. State this tradeoff explicitly.”

Follow-up 4 (Hard): “Distribute across 100 machines. Each holds 1% of the array. Find a pair summing to target.”

Signal sought: Distributed systems thinking, communication cost awareness.

Full answer: “Broadcast the target. Each machine builds a local set of its values. To find cross-machine pairs: each machine emits (target − x, x, machine_id) for each local x, hash-partitioned by (target − x) mod 100 to the responsible machine. That receiving machine checks if it holds the complement. Communication is O(N) total messages, O(N/100) per machine. Latency: 1 shuffle round. Correctness: every valid pair (x, y) where x + y = target is checked because x is hashed by y = target − x to y’s home machine. Caveat: if the array is so large that even local sets don’t fit in RAM, we partition further or stream from disk with external-sort-style processing.”

Follow-up 5 (Senior signal): “How would you test this code?”

Signal sought: Testing discipline, not just unit tests.

Full answer: “Four layers. (1) Unit: given example, [3,3], negatives, two valid pairs choosing one. (2) Edge: minimum N=2, maximum constraint. (3) Property test: random N, random ints, brute-force comparator — assert both find the same pair (modulo order). My solution.py does this via stress_test(). (4) Adversarial fuzz: hash-collision DoS inputs — known pathological inputs that cause O(N²) hashmap behavior. Production code would also include perf regression tests and memory profiling for large N.”

14. Full Solution Walkthrough

See solution.py.

The file has four sections:

1. two_sum_brute(nums, target) — nested loop, O(N²). This is your correctness oracle.
2. two_sum(nums, target) — the one-pass hashmap. Note the order: check first, insert after. The comment on line marking the invariant.
3. stress_test() — generates 1000 random arrays, runs both, asserts results sum to target equally. This is the bar: every flagship problem has a stress test.
4. __main__ — runs the given example, [3,3], negative case, then the stress test.

Decisions justified in the file:

• Why seen.get(complement) instead of if complement in seen: return [seen[complement], i]: one hash lookup instead of two.
• Why we return as a list [a, b] not a tuple: matches LC signature exactly.
• Why no input validation: per the framework, we validate at system boundaries — interview code assumes valid input per the problem statement.

15. Beyond the Problem — Production Reality

At 10M RPS:

• The hashmap allocation per request becomes a GC pressure point. In production, you’d pool the map or use a primitive-keyed map (e.g., Long2IntOpenHashMap in Java’s Eclipse Collections, or a dict allocated once and .clear()’d in Python).
• For very large N per request, the O(N) memory dominates. Spilling to off-heap or using a compact open-addressing hashmap would matter.

Real system this is the kernel of:

• Ad bid matching: given a target CPM, find two bids that sum to the publisher’s floor. Same algorithm, with bid-objects carrying metadata. Real ad exchanges (Google Ad Exchange, Meta Audience Network) do variants of this billions of times per second.
• Promo discount calculator: e-commerce platforms match “if customer buys X and Y, the bundle costs the promo target.”
• Settlement matching at exchanges: pair buy and sell orders that exactly clear.

Principal-engineer code review comment: “Why is this a one-off function? In our codebase, complement-search-against-hashmap is a building block. Extract find_pair_by_property(items, key_fn, target) so we can reuse for 3Sum, k-Sum, prefix-sum, and the promo-bundle code path. Also: thread safety? If this map is shared across requests, we have a race.”

p02 — Valid Parentheses

Source: LeetCode 20 · Easy · Topics: String, Stack Companies: Amazon (high), Google (medium), Meta (medium), Microsoft (high), Bloomberg (high), Salesforce (very high) Loop position: phone screen, sometimes paired with p80 (Basic Calculator II) at onsite

1. Quick Context

The canonical stack problem. Looks trivial; the trap is the early-return logic and the empty-stack-on-close case. Senior candidates lose points by writing 15 lines when 8 suffice, by forgetting to check the stack is non-empty at end, or by not asking whether non-bracket characters can appear.

What it tests: Disciplined use of the right data structure (stack), not loop-and-counter hacks. Anti-signal: counting opens and closes separately (“balanced count”) — that fails on "(]". If you proposed this and didn’t catch it yourself, you’ve failed the cognitive-trap check.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/valid-parentheses/

STOP. Set a 12-min timer. Solve cold. Do not read on until done or timed out.

3. Prerequisite Concepts

• LIFO semantics of a stack; why “matching last-opened” is intrinsically a stack property — phase-01 §5
• Mapping closed → open via a constant dict (O(1) lookup, more idiomatic than chained if)

4. How to Approach

Restate: “Given a string of ()[]{} characters, return true iff every opener has a matching closer of the right type, in the right nesting order.”

Clarify:

• “Can the string contain other characters?” (LC: no, only brackets — but ASK, real interviews vary.)
• “Empty string?” (LC: valid = true. Yes, common gotcha.)
• “Maximum length?” (Implies whether we care about stack overflow in recursive solutions; iterative + explicit stack avoids that anyway.)

Constraints: N up to 10⁴. O(N) expected.

Examples to build:

• "()[]{}" → true (sequential pairs)
• "([{}])" → true (full nesting)
• "(]" → false ← the counter-fail case
• "]" → false (close-first; empty-stack case)
• "((" → false (unmatched open at end; non-empty-stack-at-end case)
• "" → true (empty)

Brute force: Repeatedly scan and remove adjacent (), [], {} pairs until no change. If empty, valid. O(N²).

Pattern: “Match most recent unclosed thing” → stack. Period.

Optimal: One pass. For each char: if opener, push. If closer, pop and verify match. At end, stack must be empty.

Proof of correctness: Stack invariant — at any point, the stack contains exactly the unmatched openers in order of opening. A closer matches iff it pairs with the top (most recent opener). If a closer arrives with empty stack, it has no match → false. If non-closer remains at end → unmatched openers → false.

5. Progressive Hints

If stuck >5 min: hints.md. One at a time.

6. Deeper Insight — Why It Works

Why a stack and not a counter? A counter (opens - closes) is sufficient for a single bracket type — but it cannot detect "(]". The stack is necessary because we need to remember not just that a bracket is open, but which type. Each push commits the type; each pop verifies the type. The stack is the minimum data structure that captures both “how many open” and “which order/type.”

Why we check empty BEFORE popping: If we blindly pop an empty stack on a closer, we error out (or in some languages, get undefined behavior). The check if not stack: return False handles "]", "})", etc.

Why we check empty at END: The string "((" walks through pushing twice; loop ends; stack non-empty; without the final check, we’d return True. The end-check is the second necessary correctness step.

7. Anti-Pattern Analysis

Wrong-but-tempting #1 — Count-and-compare:

if s.count('(') == s.count(')') and s.count('[') == s.count(']') and ...:
    return True

Fails on "(]" (each count is 1, returns True). This is the single most common bug junior candidates ship. If you proposed this, you missed the type-ORDER requirement.

Wrong-but-tempting #2 — Regex / replace loop:

while '()' in s or '[]' in s or '{}' in s:
    s = s.replace('()','').replace('[]','').replace('{}','')
return s == ''

Works but O(N²) and signals you reached for a hammer. Interviewer’s note: “didn’t recognize stack pattern.”

Wrong-but-tempting #3 — Forgetting end-check:

for c in s:
    if c in '([{': stack.append(c)
    elif c in ')]}':
        if not stack or pairs[c] != stack.pop(): return False
return True   # ← BUG: returns True for "((" because stack non-empty but no closer caught it

The fix is return not stack. Forgetting this is the #2 bug here.

8. Skills & Takeaways

Generalizable pattern: “Match most recent unresolved item” → stack. Applies to:

• LC 32 — Longest Valid Parentheses (stack of indices, harder cousin)
• LC 84 — Largest Rectangle in Histogram (monotonic stack — same family)
• LC 739 — Daily Temperatures (monotonic stack — same family)
• LC 71 — Simplify Path (each segment as stack frame)
• LC 394 — Decode String (stack of (count, prefix) frames)
• LC 1249 — Minimum Remove to Make Parentheses Valid (stack of indices)

When NOT to use: Single bracket type, just balance counting → counter is sufficient and uses O(1) space.

9. When to Move On

• Solved unaided in <8 min on second attempt
• Tested "(]", "]", "((", "" without prompting
• Can articulate why a counter fails for multiple bracket types
• Implemented with constant closer → opener map (not chained ifs)
• Stress test in solution.py passes
• Solved LC 1249 and recognized the same pattern with index tracking

10. Company Context

Amazon

• The framing: Often paired with “and write the matched pairs as (open_idx, close_idx)” — extends to index-tracking variant.
• Misleading example: They give "{[()]}" and let you confirm true. Then sneak in "{[(])}" — looks balanced character-counts-wise; trips candidates who didn’t catch the type-order failure.
• Extension: “Now allow <> too.” → tests whether your code generalizes (constant dict makes it 1-line; chained ifs make it 4 new branches).

Salesforce (this is THEIR favorite)

• The framing: Often appears in onsite, not phone screen — they care about the cleanliness more than the algorithm.
• What they want to hear: “I’ll use a stack and a dictionary mapping closers to openers.” That sentence alone is a green check.
• Adversarial extension: “What if [ could match ) (mixed mode)?” → tests whether your code is data-driven enough to change one line of config.

Microsoft

• The framing: Phone screen warmup, sometimes followed by p80 (Basic Calculator).
• What they want to hear: Single-pass justification, end-of-loop empty-check stated out loud.

Bloomberg

• The framing: Often as part of a JSON/parser problem — “validate this serialized message structure”.
• Extension: “Parse the bracketed expression into an AST.”

11. Interviewer’s Lens

12. Level Delta

13. Follow-up Questions & Full Answers

Q1: “Return the index of the first invalid character instead of true/false.”

Signal: Can you adapt without rewriting? Answer: Track current index i; when popping mismatches or empty-pop happens, return i. At end if stack non-empty, return the index of the unmatched opener at stack top (so push (char, index) tuples, not just chars). One-pass O(N), no extra time cost.

Q2: “Mixed bracket modes: also accept [) and (] as valid in this protocol.”

Signal: Data-driven code awareness. Answer: Replace {')':'(', ']':'[', '}':'{'} with {')':'([', ']':'[(', '}':'{'} and change the match check from stack.pop() == pairs[c] to stack.pop() in pairs[c]. Zero algorithm change — only the config dict moves. Demonstrates extensibility.

Q3 (Hard): “Parse and evaluate the matched expression as a Lisp-like AST.”

Signal: Stack-of-frames extension. Answer: Each frame is a list of tokens accumulating between matching opens. On open: push current frame, start new. On close: pop, append the inner frame to the outer. Same stack discipline, now each entry is a list, not a char. This is the bridge from p02 to LC 394 (Decode String) and to p80 (Basic Calculator).

Q4: “Now there are millions of strings per second — same algorithm, but optimize for throughput.”

Signal: Production thinking. Answer: Three wins. (a) Replace Python list-as-stack with a fixed-size preallocated array + integer top pointer — eliminates allocation. (b) Use a 256-entry lookup table mapping char codes to (type, is_opener) instead of dict lookup — branch-free hot loop. (c) For truly hot path, write a SIMD-friendly state machine in C — but only after profiling shows this is the bottleneck.

Q5: “How would you test it?”

Signal: Testing discipline. Answer: (1) Unit: all 6 fail modes + valid + empty. (2) Property test: brute (replace-loop) vs optimal on random bracket strings, must agree. My solution.py does this. (3) Adversarial: deeply nested input (depth = 10⁵) — confirms iterative, not stack-overflowing. (4) Fuzz: random non-bracket chars to confirm the “ask about other characters” clarification.

14. Full Solution Walkthrough

See solution.py.

• is_valid_brute: repeated replace loop. Correct but O(N²). Used as oracle.
• is_valid: stack + closer→opener dict. Three correctness branches: (i) push on open, (ii) check-then-pop on close (empty + mismatch both → False), (iii) final stack-empty check.
• stress_test: generates random bracket strings (balanced and unbalanced), asserts brute and optimal agree.

15. Beyond the Problem

Real systems this is the kernel of:

• JSON / XML / YAML parsers — every structural parser uses this exact stack discipline. Errors in production parsers (e.g., “Unexpected end of input”) are the end-empty-check firing.
• IDE bracket matching — your editor’s “matching bracket” highlight runs this algorithm on every keystroke, scoped to a window around the cursor.
• Code linters — eslint’s no-unbalanced-brackets rule is this with position tracking.
• Network protocols with framing (e.g., BSON, MessagePack) use stack-based parsers.

Principal-engineer code review comment: “We have three places in the codebase that re-implement bracket matching (JSON parser, query parser, markdown renderer). They’ve each drifted to handle their edge cases differently. Extract a generic match_pairs(input, pair_table, on_unmatched) and centralize. The bug we hit last quarter was the JSON parser missing the end-check; the markdown one had the check but the wrong error message.”

p03 — Best Time to Buy and Sell Stock

Source: LeetCode 121 · Easy · Topics: Array, DP, Greedy Companies: Amazon (very high), Bloomberg (very high), Facebook (high), Apple (medium), Uber (medium) Loop position: phone screen, or first warmup before harder DP onsite

1. Quick Context

This is the “single-transaction maximum profit” problem and the entry door to a 6-problem ladder (LC 121, 122, 123, 188, 309, 714) that culminates in the hardest stock problems on LC. Mastering p03 properly — by recognizing it as “max forward-difference with constraint i < j” and NOT brute force — unlocks the whole family.

What it looks like it tests: array iteration. What it actually tests: Whether you see the invariant transformation: instead of trying all (buy, sell) pairs, track the minimum buy-price seen-so-far and compute profit-if-sold-today. This is a one-pass O(N), O(1) algorithm; the brute force is O(N²).

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

12-min timer. Cold attempt. No reading on.

3. Prerequisite Concepts

• “Running min/max” pattern — phase-02 §3 Prefix Sums (same family — running aggregate)
• Greedy correctness: why local-min + global-max-of-(today - min) is globally optimal

4. How to Approach

Restate: Given prices indexed by day, pick a buy-day i and a sell-day j > i to maximize prices[j] - prices[i]. If no profit possible, return 0. One transaction only.

Clarify:

• “Can I sell on the same day I buy?” (No — strict j > i.)
• “If prices monotonically decrease, return 0 or negative?” (Per LC: 0 — no transaction is valid.)
• “Multiple transactions allowed?” (No, this is LC 121. LC 122 is the multi-transaction version. ASK to confirm.)
• “Length bounds?” (LC: up to 10⁵ → O(N²) will TLE.)

Examples:

• [7,1,5,3,6,4] → 5 (buy at 1, sell at 6)
• [7,6,4,3,1] → 0 (no profit possible)
• [1] → 0 (no transaction possible — single price)
• [2,4,1] → 2 (buy at 2, sell at 4, NOT buy at 1; can’t sell after — common trap)

Brute force: All (i, j) pairs with j > i; track max diff. O(N²) time, O(1) space.

Pattern recognition: “Max value of a[j] - a[i] with i < j” → equivalent to “at each j, what’s the min of a[0..j-1]?” → running-min + per-element subtract → O(N).

Optimal:

min_so_far = +infinity
best = 0
for price in prices:
    best = max(best, price - min_so_far)
    min_so_far = min(min_so_far, price)
return best

Order matters: Compute best BEFORE updating min_so_far. Otherwise on a single day you’d allow “buy and sell same day” (price - price = 0, no harm here but ON LC 122 the equivalent bug causes phantom profits).

Correctness proof (greedy): For any optimal pair (i*, j*) with j* > i*, when the loop reaches j*, min_so_far ≤ prices[i*] (because i* ≤ j*-1, and min_so_far covers prices[0..j*-1]). So prices[j*] - min_so_far ≥ prices[j*] - prices[i*] = optimal. Since we take the max over all j, we capture this value.

5. Progressive Hints

hints.md — one at a time, 5-min timer.

6. Deeper Insight — Why It Works

The transformation: A 2D search “find (i, j) max difference” becomes 1D “at each j, what’s the best historical min?” by recognizing that for any fixed j, the optimal i is argmin(prices[0..j-1]). We don’t need to remember which i — just its value. This is the same compression that powers Kadane’s algorithm (maximum subarray): instead of trying all subarrays, track the best one ending here.

Why O(1) space: The running-min subsumes all history we need. We never look back; we only look at the current price vs. the cheapest ever.

Connection to Kadane’s algorithm: If you compute diffs[i] = prices[i+1] - prices[i], then LC 121 becomes “max sum subarray over diffs” — Kadane’s algorithm. This equivalence is a Staff-level observation.

7. Anti-Pattern Analysis

Wrong #1 — Two pointers from both ends: Some try left = 0, right = N-1, shrink to find max. Doesn’t work: the optimal pair isn’t necessarily at the extremes.

Wrong #2 — Sort: Sorting destroys the time-order constraint. The buy-day must come before the sell-day in original order.

Wrong #3 — Update min before max:

for p in prices:
    min_so_far = min(min_so_far, p)   # ← wrong order
    best = max(best, p - min_so_far)

On LC 121, gives same answer because max profit on day i if buy=sell=i is 0. But on the multi-tx variants this exact bug allows “buy and sell at same instant,” inflating profit.

Wrong #4 — Greedy “buy every local min”: Confuses LC 121 (single transaction) with LC 122 (multiple). Read the prompt.

8. Skills & Takeaways

Pattern: running-min/max + per-element decision. Direct applications:

• LC 122 — Buy/Sell II (multiple tx → sum positive diffs greedily)
• LC 123 — Buy/Sell III (at most 2 tx → DP over states)
• LC 188 — Buy/Sell IV (at most k tx → generalized DP)
• LC 309 — with cooldown (state machine DP)
• LC 714 — with fee (state machine DP)
• LC 53 — Maximum Subarray (Kadane — same family via diff transform)
• LC 152 — Maximum Product Subarray (track both running min and max because negatives)

9. When to Move On

• Solved unaided <8 min, O(N), O(1)
• Tested decreasing input, single-element, two-element
• Articulated the “running min + per-step profit” transformation
• Connected to Kadane’s algorithm via the diff trick
• Stress test passes
• Solved LC 122, LC 53; saw the family resemblance

10. Company Context

Amazon

• The framing: “You’re shown daily stock prices for a company. What’s the most an investor could have made with one buy and one sell?”
• Misleading example: They give [2, 4, 1] to bait the “buy at 1” mistake. The trap: 1 is the LAST day, no sell possible after.
• Adversarial extension: “Now they can do multiple transactions” (→ LC 122) immediately followed by “now there’s a $1 fee per transaction” (→ LC 714). Tests whether you generalize cleanly.

Bloomberg (terminal company — they LIVE on time-series)

• The framing: Often pure LC 121, sometimes with timestamps not indices (test if you read the order from the input).
• What they want: Recognition that this is a time-series invariant problem. The phrase “I’ll track the running minimum” is a green check.
• Extension: “What if prices stream in?” → same algorithm; the running-min works incrementally.

Meta

• The framing: Followed RAPIDLY by LC 122, then “at most k transactions” (LC 188).
• What they want: You finish LC 121 in 5 minutes so they get to LC 188. If you spend 15 min on LC 121, you’ll never reach the real interview question.

Uber

• Frame: “Surge pricing history — best moment to launch a promotional ride.”
• Extension: “What if some days are weekends and weekend buys are forbidden?” → tests masking, not algorithm.

11. Interviewer’s Lens

12. Level Delta

13. Follow-up Questions & Full Answers

Q1: “Now allow unlimited transactions.” → LC 122.

Answer: Sum every positive consecutive diff: sum(max(0, prices[i+1] - prices[i]) for i in range(N-1)). Proof: any concave-up segment between local min and local max contributes (max - min); the sum of positive diffs equals the sum of these contributions. O(N) one pass, O(1) space.

Q2: “At most k transactions.” → LC 188.

Answer: DP. State: dp[t][i] = max profit using ≤ t transactions through day i. Transition: dp[t][i] = max(dp[t][i-1], max over j<i of (dp[t-1][j-1] + prices[i] - prices[j])). Naively O(k·N²); optimize the inner max to O(1) by tracking max(dp[t-1][j-1] - prices[j]) as we scan, giving O(k·N). When k ≥ N/2, problem degenerates to unlimited tx (LC 122) — handle this case separately.

Q3: “What about transaction fee f per buy-sell pair?” → LC 714.

Answer: State machine. hold[i] = max profit ending day i holding a stock; cash[i] = max profit ending day i not holding. hold[i] = max(hold[i-1], cash[i-1] - prices[i]). cash[i] = max(cash[i-1], hold[i-1] + prices[i] - f). Pay the fee when selling. O(N), O(1) with two scalars.

Q4: “Streaming prices, infinite stream. Output the running best-possible-profit-so-far.”

Answer: Same algorithm, incremental. Maintain min_so_far and best. On each tick, update both. The answer is best at all times. O(1) per tick.

Q5: “How do you test it?”

Answer: (1) Edge: empty (or N=1) → 0, decreasing → 0, increasing → last - first. (2) Property: brute-force O(N²) vs optimal on random arrays. (3) Adversarial: arrays where the buy is on day 0 vs day N-2 — tests whether running-min update timing is right.

14. Full Solution Walkthrough

See solution.py.

Three solutions for didactic value:

• max_profit_brute: all pairs, O(N²). Oracle.
• max_profit: running-min one-pass, O(N), O(1).
• max_profit_kadane: Kadane on diffs, to demonstrate equivalence.

All three should agree under stress_test.

15. Beyond the Problem

Real systems this is the kernel of:

• Backtest engines (Zipline, Backtrader): the “perfect foresight” upper bound used to score strategies. A strategy can’t beat single-transaction-max-profit on a sequence; this is the benchmark.
• A/B test analysis: “what’s the largest sustained delta we observed?” — same running-min/max.
• Latency/throughput dashboards: “what’s the largest drop in throughput?” — running-max + per-point delta.

Principal-engineer code review comment: “This algorithm assumes prices is a value-typed array. In our pipeline, prices are timestamped events with possible gaps. Either resample to fixed-interval before feeding, or change the algorithm to work on (timestamp, price) tuples and handle missing intervals. Also: what’s the contract when prices contains NaN (market closed)? Define it explicitly.”

p04 — Merge Sorted Array

Source: LeetCode 88 · Easy · Topics: Array, Two Pointers, Sorting Companies: Facebook (high), Bloomberg (high), Microsoft (high), Adobe (medium), Apple (medium) Loop position: phone screen or onsite warmup; often paired with a follow-up to merge k arrays (LC 23 — Merge k Sorted Lists)

1. Quick Context

A deceptively simple problem with a sharp trick: you must merge in place in nums1 (which has extra trailing zeros). The naive approach (merge from the left) requires shifting → O(N²). The optimal approach (merge from the right, writing the largest elements into the back) is O(M+N), O(1) extra.

What it tests: in-place pointer manipulation and the recognition that writing backwards avoids the overwrite problem. The trap: candidates instinctively merge from the front and either get O(N²) or need an extra buffer (O(N) space) and forget that the prompt forbids it.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/merge-sorted-array/

12-min timer. Cold attempt. The “merge from the back” insight should be the first thing you reach for — if not, that’s a strong signal you need this rep.

3. Prerequisite Concepts

• Two-pointer technique — phase-02 §1
• “In-place transformation” pattern — when extra buffer is forbidden

4. How to Approach

Restate: nums1 has length m + n. Its first m entries are valid, sorted; the last n are placeholder zeros. nums2 has n valid sorted entries. Merge so that nums1 holds all m + n values sorted. Modify nums1 in place.

Clarify:

• “Can I use O(N) extra space?” (Usually no — the whole point is in-place. ASK.)
• “Are duplicates allowed?” (Yes; merge is stable.)
• “Can m or n be 0?” (Yes. Both edge cases.)
• “Are negative numbers allowed?” (Yes, per constraints.)

Examples:

• nums1=[1,2,3,0,0,0], m=3, nums2=[2,5,6], n=3 → [1,2,2,3,5,6]
• nums1=[1], m=1, nums2=[], n=0 → [1] (n=0 edge)
• nums1=[0], m=0, nums2=[1], n=1 → [1] (m=0 edge)
• nums1=[4,5,6,0,0,0], m=3, nums2=[1,2,3], n=3 → [1,2,3,4,5,6] (all of nums2 < all of nums1 — tests handling when nums2 isn’t exhausted)

Brute force: Copy nums2 into the tail of nums1, then sort. O((M+N) log (M+N)). Trivially correct but wastes the “already sorted” property.

Pattern: Two sorted sequences + in-place + extra room at the END → merge from the back, largest first.

Optimal:

i = m - 1            # pointer into nums1's valid part
j = n - 1            # pointer into nums2
write = m + n - 1    # pointer into nums1's tail (where to write next)
while j >= 0:        # only need to keep going while nums2 has elements
    if i >= 0 and nums1[i] > nums2[j]:
        nums1[write] = nums1[i]
        i -= 1
    else:
        nums1[write] = nums2[j]
        j -= 1
    write -= 1

Why we loop on j >= 0, not i >= 0: If nums2 is exhausted, the remaining nums1[0..i] is already in its final position (since we wrote bigger elements to the right). If nums1’s valid prefix is exhausted (i < 0), we must still copy remaining nums2 elements. The loop condition reflects which case requires action.

Correctness: At each step we write the larger of the two unprocessed maxima into the next free slot from the right. The slot is always at or past the “write frontier”, which is at index i + j + 1. Since write = i + j + 1 decreases monotonically and i + j is the count of unprocessed elements minus 2, the slot is never one we still need to read from. No overwrite.

5. Progressive Hints

hints.md. One at a time.

6. Deeper Insight — Why It Works

The reverse-merge insight: Merging from the front into nums1 would overwrite valid nums1 data before reading it (because the write pointer would catch up to the read pointer for nums1). Merging from the back writes into slots that are guaranteed unused (either they’re trailing zeros, or they’re slots holding values already moved).

The invariant: At any point, nums1[write+1 .. m+n-1] contains the largest (m+n-1 - write) elements of the final merged result, in sorted order. nums1[0..i] and nums2[0..j] are the unprocessed prefixes.

Why i+j+1 == write always: Initially i+j+1 = (m-1) + (n-1) + 1 = m+n-1 = write. Each iteration decrements write by 1 and decrements either i or j by 1, so the relation holds. Therefore write is always one past i+j, the position right after the unprocessed prefixes — guaranteed empty. This is the formal proof of “no overwrite.”

7. Anti-Pattern Analysis

Wrong #1 — Front merge with shift:

i, j = 0, 0
while j < n:
    if i < m and nums1[i] <= nums2[j]:
        i += 1
    else:
        # shift nums1[i..m-1] right to make room
        nums1.insert(i, nums2[j])  # O(M) shift!
        nums1.pop()                # O(M)
        i += 1
        m += 1
        j += 1

Correct but O((M+N) × M) — quadratic. Senior interviewers see this and ask “can you do better?” — if you can’t pivot to the reverse-merge, you’ve revealed a gap.

Wrong #2 — Copy nums1 valid prefix to an aux buffer:

aux = nums1[:m]
# then merge aux and nums2 into nums1 from the front

Correct and O(M+N) time but O(M) extra space. Violates the in-place spirit — passes LC but loses interview points.

Wrong #3 — Sort after concat:

nums1[m:] = nums2
nums1.sort()

O((M+N) log (M+N)). Passes LC. But: “you ignored the ‘sorted input’ property — what was the point of this problem?”

Wrong #4 — Forget the i >= 0 guard in the comparison:

while j >= 0:
    if nums1[i] > nums2[j]:   # IndexError when i goes negative

The guard if i >= 0 and nums1[i] > nums2[j] matters when nums1’s valid prefix is exhausted before nums2.

8. Skills & Takeaways

Pattern: write-backwards-to-avoid-overwrite. Direct applications:

• LC 26 / 27 / 80 — Remove Duplicates / Remove Element (write-forward variant)
• LC 283 — Move Zeroes
• LC 977 — Squares of a Sorted Array (write from back: largest absolute value at each end)
• LC 167 — Two Sum II (two-pointer from both ends; sibling family)

The “merge from back” trick generalizes: Any in-place merge where one container has trailing room becomes O(N) by writing backward. Used in some qsort partition tricks and in compaction passes of generational garbage collectors.

9. When to Move On

• Solved unaided <10 min using reverse-merge
• Tested m=0, n=0, all-of-nums2-smaller, equal elements
• Articulated why front-merge fails (overwrite) and back-merge succeeds (slot guaranteed free)
• Stress test passes
• Solved LC 977; saw the same write-backwards idea

10. Company Context

Facebook / Meta

• Frame: Often appears as a warmup before LC 23 (Merge k Sorted Lists). The interviewer expects you to do p04 in 5 min, then they ask “now generalize to k arrays.”
• What they want: Reverse-merge offered without prompting. The phrase “I’ll merge from the back to avoid shifting” is a green check.
• Trap: They give you nums1 with extra space already allocated. Candidates who treat nums1 as size-m and try to grow it don’t see the “trailing zeros” hint.

Bloomberg

• Frame: Often as merge of two sorted price-tick streams (“merge into a single time-ordered view”).
• Extension: “Now they may have duplicate timestamps — preserve order from stream A first.” Tests stable-merge awareness.

Microsoft

• Frame: Phone screen warmup. They watch your pointer manipulation cleanliness.
• What they want: Correct, no off-by-one, comment on the loop condition. Boring + correct = pass.

Adobe

• Frame: Often given with the explicit constraint “no extra memory”. Tests whether you internalize the in-place requirement.

11. Interviewer’s Lens

12. Level Delta

13. Follow-up Questions & Full Answers

Q1: “Now merge k sorted arrays into one.” → LC 23 family

Answer: Min-heap of (value, array_id, element_id). Pop smallest, append to output, push the next from the same array. O(N log k) where N is total elements. For very large k, consider tournament tree (same complexity, lower constant).

Q2: “What if nums1 doesn’t have extra room at the end — same length as valid data?”

Answer: No way to merge in place in O(M+N). You’d need O(min(M,N)) extra space minimum (proof: there must be storage for the merge frontier). Standard out-of-place merge.

Q3: “What if both arrays are huge and stored on disk?”

Answer: External merge sort’s merge phase. Read both arrays in buffered chunks; merge into output buffer; flush when full. Classical pattern. The key complexity unit becomes I/O, not comparisons.

Q4: “Merge two sorted linked lists in place.” → LC 21

Answer: Two-pointer with rewiring. Maintain a dummy head + a tail pointer. At each step, point tail.next to the smaller of a.val, b.val, advance that pointer. After the loop, append whatever remains. O(M+N), O(1) extra.

Q5: “How do you test?”

Answer: (1) Edge: m=0, n=0, all-A-smaller, all-A-larger, equal elements, single-element each. (2) Property: brute (sort after concat) vs optimal on random sorted inputs, must agree element-for-element. (3) Adversarial: very different sizes (m=1, n=10⁵) — confirms loop conditions handle imbalance.

14. Full Solution Walkthrough

See solution.py.

• merge_brute(nums1, m, nums2, n): append nums2 then sort. Oracle.
• merge(nums1, m, nums2, n): reverse-merge with three pointers. Mutates nums1 in place.
• stress_test: random sorted arrays of random sizes; brute vs optimal must produce identical nums1.

15. Beyond the Problem

Real systems this is the kernel of:

• Database compaction: LSM trees (LevelDB, RocksDB, Cassandra) periodically merge sorted SSTables. The merge phase is exactly this algorithm, scaled to disk-resident sorted runs with buffered I/O.
• Log merging: distributed tracing systems (Jaeger, Zipkin) merge per-shard time-sorted spans into a global view.
• External sort: when data exceeds RAM, sort runs in memory, write to disk, then merge runs — same algorithm.
• Generational garbage collectors: compaction passes merge live objects into a destination region; the “write backwards” idea appears in some collectors to avoid overwriting unmoved objects.

Principal-engineer code review: “If this is being called in a tight loop, the algorithm is fine but the API is wasteful — caller must allocate nums1 with extra capacity. Consider a builder pattern that allocates the output buffer once and reuses it, especially if M and N vary. Also: the function silently assumes nums1 has length m+n; add a precondition or a contract test, or someone will pass an under-sized array and you’ll get a confusing IndexError instead of a clear contract violation.”

p05 — Climbing Stairs

Source: LeetCode 70 · Easy · Topics: Math, DP, Memoization Companies: Adobe (high), Amazon (medium), Apple (medium) Loop position: the canonical “intro to DP” — almost always a warmup before a real DP question

1. Quick Context

The “Fibonacci in disguise” problem. It’s the cleanest possible 1D DP and exists to teach you the recipe: (1) define state, (2) write recurrence, (3) identify base cases, (4) decide order, (5) compress space. If you can’t articulate those 5 steps on p05, you can’t on p51 (House Robber), p55 (Jump Game), p60 (Longest Increasing Subsequence), or anywhere else.

What it looks like it tests: ability to recognize Fibonacci. What it actually tests: the DP recipe. Interviewers use this as a calibration — if you write recursion without memoization (O(2^N)), or memoization without realizing iteration is simpler, you’ve revealed your DP fluency level.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/climbing-stairs/

10-min timer. Cold attempt. If you reach for recursion-without-memo, that’s the signal you need this rep most.

3. Prerequisite Concepts

• Recursion + memoization basics — phase-01 §8
• “State + recurrence + base case” — the universal DP recipe
• Space compression: when only the last k states are needed, store only those

4. How to Approach

Restate: From step 0, reach step n, taking either 1 or 2 steps at a time. How many distinct ways?

Clarify:

• “Distinct sequences of moves, or distinct step sets?” (Sequences — 1+2 and 2+1 are different. ASK; some problems differ.)
• “n ≥ 1?” (Per LC: 1 ≤ n ≤ 45.)
• “Why n ≤ 45?” (Hints at int overflow in some languages; in Python no issue. Worth a verbal acknowledgment.)

Examples:

• n=1 → 1 (just [1])
• n=2 → 2 ([1,1], [2])
• n=3 → 3 ([1,1,1], [1,2], [2,1])
• n=4 → 5 (Fibonacci pattern starts to emerge: 1, 2, 3, 5)
• n=5 → 8

Brute force (recursive): f(n) = f(n-1) + f(n-2), base f(1)=1, f(2)=2. O(2^N) time without memo — exponential.

Pattern recognition: The recurrence is Fibonacci. Anywhere you see “ways to reach state N built from prior states” with overlapping subproblems → DP.

Optimal: Iterative DP, two scalars (prev1, prev2). O(N) time, O(1) space.

if n <= 2: return n
prev2, prev1 = 1, 2     # f(1), f(2)
for i in range(3, n+1):
    prev2, prev1 = prev1, prev1 + prev2
return prev1

Recurrence justification: To reach step n, the last move was either a 1-step (from step n-1) or a 2-step (from step n-2). These are disjoint sets of paths, so total = f(n-1) + f(n-2).

5. Progressive Hints

hints.md. One at a time.

6. Deeper Insight — Why It Works

The DP recipe applied:

1. State: f(n) = number of distinct ways to reach step n.
2. Recurrence: f(n) = f(n-1) + f(n-2) (last move was 1 or 2).
3. Base cases: f(1) = 1, f(2) = 2. (Why two base cases? Recurrence reaches back two steps; we need both grounded.)
4. Order: Bottom-up (iteratively i = 3 .. n) because f(n) depends only on smaller i.
5. Space compression: Only the last two values are needed, so two scalars suffice — O(1) space.

Why two base cases, not one? The recurrence f(n) = f(n-1) + f(n-2) requires f(n-2) to be defined when n=3, so we must specify both f(1) and f(2). Trying to derive f(2) from f(0) + f(1) requires defining f(0) = 1 (the empty path) — a valid alternative formulation, but the natural problem space starts at step 1.

Closed form (Staff signal): Fibonacci has a closed-form Φ^n / √5 (Binet’s formula). For interview purposes, mention it exists but don’t compute it — floating-point loses precision for n > ~70 and the problem caps at 45 anyway.

Matrix exponentiation (Staff signal): Fibonacci can be computed in O(log N) via [[1,1],[1,0]]^n. Overkill for n ≤ 45; useful when n is large or when the recurrence generalizes (e.g., f(n) = a·f(n-1) + b·f(n-2)).

7. Anti-Pattern Analysis

Wrong #1 — Plain recursion, no memo:

def climb(n):
    if n <= 2: return n
    return climb(n-1) + climb(n-2)

O(2^N). At n=45, ~35 billion calls. TLE for sure. Interviewer’s note: “didn’t recognize overlapping subproblems.”

Wrong #2 — Memo with dict overhead:

@lru_cache
def climb(n):
    if n <= 2: return n
    return climb(n-1) + climb(n-2)

Works in O(N) but uses O(N) call stack and dict memory. Iterative is strictly better — no recursion limit risk, O(1) space. Mention lru_cache exists but show why iterative wins.

Wrong #3 — DP table O(N) space:

dp = [0]*(n+1)
dp[1], dp[2] = 1, 2
for i in range(3, n+1): dp[i] = dp[i-1] + dp[i-2]
return dp[n]

Correct, O(N) time, O(N) space. Misses the O(1) compression. Senior signal: notice you only need the last 2 values, drop the array.

Wrong #4 — Off-by-one on base cases: Forgetting n==1 returns 1, not 2; or forgetting to handle n==2 directly and letting the loop run. Tests with n=1, 2, 3 catch these.

8. Skills & Takeaways

The DP recipe — burn it in:

1. State definition
2. Recurrence with justification
3. Base cases (one per step the recurrence reaches back)
4. Computation order
5. Space compression (only keep what’s referenced)

Generalizations — variants you’ll see:

• LC 746 — Min Cost Climbing Stairs (same structure, minimize cost instead of count)
• LC 198 — House Robber (same structure with “can’t be adjacent” constraint)
• LC 213 — House Robber II (circular variant)
• LC 91 — Decode Ways (Fibonacci with validity guards)
• LC 1137 — N-th Tribonacci (extend recurrence to 3 prior terms)
• LC 509 — Fibonacci Number (literal Fibonacci)

When you can take 1, 2, or 3 steps: f(n) = f(n-1) + f(n-2) + f(n-3) (Tribonacci). When you can take 1..k steps: f(n) = sum f(n-i) for i=1..k → can be O(N) with a sliding window.

9. When to Move On

• Solved iteratively, O(N) time, O(1) space, <8 min
• Tested n=1, n=2, n=3
• Articulated all 5 DP recipe steps without prompting
• Connected to House Robber (LC 198) as the same pattern with cost
• Stress test passes
• Mentioned closed-form / matrix exp exist (Staff signal)

10. Company Context

Adobe (this is their go-to DP warmup)

• Frame: Often given verbatim.
• What they want: Iterative O(1) space, articulated DP recipe. Recursion without memo is a near-instant fail.
• Extension: “What if you can take 1, 2, or 3 steps?” → Tribonacci. Tests generalization.

Amazon

• Frame: Sometimes as a paving / tiling problem (“ways to tile a 1×N corridor with 1×1 and 1×2 tiles”) — same Fibonacci underneath.
• Extension: “Now there’s a step you can’t land on (broken stair).” → DP with constraint: f(broken) = 0, recurrence unchanged otherwise.

Apple

• Frame: Often paired with LC 198 (House Robber) — they want to see if you generalize.

11. Interviewer’s Lens

12. Level Delta

13. Follow-up Questions & Full Answers

Q1: “What if you can take 1, 2, or 3 steps?”

Answer: Tribonacci. f(n) = f(n-1) + f(n-2) + f(n-3), base cases f(1)=1, f(2)=2, f(3)=4. O(N) time, O(1) space with three scalars.

Q2: “What if you can take 1..k steps?”

Answer: f(n) = sum f(n-i) for i in 1..k. Naive O(N·k). Optimize via sliding window: f(n) = f(n-1) + f(n-1) - f(n-1-k) (because consecutive windows overlap in k-1 terms). O(N), O(k) space.

Q3: “Now some steps are broken — you can’t land there.”

Answer: f(broken[i]) = 0. Recurrence unchanged. Still O(N), O(1) — just a guard inside the loop.

Q4: “Same problem but n can be up to 10^18.”

Answer: Matrix exponentiation. [f(n), f(n-1)]^T = M^(n-1) · [f(1), f(0)]^T where M = [[1,1],[1,0]]. Compute M^(n-1) via binary exponentiation in O(log N) matrix multiplications, each O(1) for a 2×2 matrix. Total O(log N). Use modular arithmetic to prevent overflow.

Q5: “How do you test it?”

Answer: (1) Small cases against hand-computed Fibonacci values (1, 2, 3, 5, 8, 13). (2) Property: brute recursive (with memoization) vs iterative agree on n in 1..30. (3) Stress on the boundary n=1 (off-by-one trap) and n=45 (max constraint).

14. Full Solution Walkthrough

See solution.py.

• climb_brute(n): plain recursion, no memo. Used as oracle for small n only (would TLE for large).
• climb(n): iterative two-scalar version. O(N) time, O(1) space.
• climb_memo(n): top-down memoization, included for comparison. O(N) time, O(N) space.
• stress_test: brute vs optimal vs memo on n ∈ [1, 25], all three agree.

15. Beyond the Problem

Real systems this is the kernel of:

• Path-counting in DAGs: number of distinct routes through a graph. The 1D variant generalizes to the topological order of a DAG.
• State-machine reachability: number of distinct token sequences leading to a state in a parser.
• Combinatorial enumeration in recommender systems: counting compatible item sequences under constraints.
• Probabilistic state aggregation: when transition probabilities are uniform, counts and probabilities differ only by a normalizing constant.

Principal-engineer code review: “This function is correct but its name climb_stairs is so specific that it won’t be reused. The underlying primitive — counting paths under additive recurrence — appears in three other places in our codebase, each reimplemented. Extract count_paths(n, allowed_step_sizes) and use it everywhere. Also: cache the result if called repeatedly with the same n — but for n ≤ 45 the compute cost is negligible, so probably not worth the cache complexity.”

Phase 0 — Interview Execution Baseline

Target level: Beginner → Easy Expected duration: 1 week (12-week track) / 1–2 weeks (6-month) / 2 weeks (12-month) Weekly cadence: 7 labs + 25 Easy problems applying the framework rigorously

Why This Phase Exists

Most candidates fail interviews not because they lack algorithms knowledge, but because of execution failures: they jump to coding before understanding the problem, panic when stuck, miss obvious edge cases, or communicate so poorly that the interviewer can’t tell whether they actually solved it.

Phase 0 fixes execution. It does not teach algorithms. It teaches you how to use what you already know.

Concepts To Master

1. How Coding Interviews Are Evaluated

Every modern coding interview at Big Tech uses a multi-dimensional rubric. The dimensions are roughly:

• Problem understanding — did you grasp what was asked?
• Approach quality — did you find a reasonable solution?
• Optimality — did you reach the optimal complexity?
• Implementation correctness — does your code actually work?
• Code quality — would your code pass code review?
• Testing — did you verify your solution?
• Communication — could the interviewer follow your thinking?
• Tradeoff awareness — do you understand what you chose and why?

Each is scored ~independently. A “hire” decision typically requires strong scores on most dimensions, not perfect on one. Code that works but is uncommunicated is often a no-hire.

2. How To Communicate While Solving

See ../COMMUNICATION.md in full. The summary: narrate your intent, not your typing. Pause at decision points. Ask before assuming.

3. How To Ask Clarifying Questions

Good questions:

• “Can the input be empty?”
• “Are there duplicates allowed?”
• “What’s the expected size of N — is 10^5 reasonable?”
• “Does the order of output matter?”
• “What should happen on invalid input?”
• “If multiple valid answers exist, can I return any one?”

Bad questions:

• Re-asking what’s already in the problem statement (signals poor reading)
• “What’s the optimal complexity?” (this is your job to derive)
• 15 questions in a row (drip them as relevant)

4. How To Derive Constraints

Constraints dictate the algorithm. Memorize this table:

Rule of thumb: in modern judges, 10^8 simple operations per second is safe; 10^9 is risky.

5. How To Create Examples

The given examples are minimum-coverage. You should construct:

• Trivial: size 0, size 1.
• Boundary: all duplicates, all negatives, all sorted, all reversed.
• Adversarial: max-constraint values, edge of integer range.
• Multi-answer: if multiple valid outputs exist, pick a specific one.

Working through your own examples often reveals the pattern faster than reading the problem 5 more times.

6. How To Identify Edge Cases

Universal checklist (run through this every problem):

• Empty input
• Null input (where applicable)
• Single element
• Two elements
• Duplicates
• Negative numbers
• Maximum constraint values (overflow risk)
• Sorted input
• Reversed input
• Disconnected graph
• Cycle in graph
• Multiple valid answers
• All identical values
• Off-by-one at boundaries

7. How To Start With Brute Force

The brute force is mandatory. Even when you “see” the optimal:

• It anchors correctness — you have a working oracle.
• It’s a starting point to optimize from.
• It’s a fallback if optimization fails.
• It demonstrates you understand the problem at all.

State the brute force in pseudocode within the first 3 minutes.

8. How To Optimize

Optimization checklist:

• Pattern recognition — does this match a known pattern? See Phase 2.
• Repeated work — what does the brute force recompute? That’s your DP / memo target.
• Sortedness — would sorting help? Two pointers, binary search, sweep line.
• Monotonicity — is the answer monotonic in some parameter? Binary search on answer.
• State compression — can the state space be made smaller? Bitmask, prefix sum.
• Math — closed form, modular arithmetic, combinatorics.
• Data structure — would a heap / BST / segment tree change the complexity?

9. How To Prove Correctness

• Greedy: exchange argument — show that any optimal solution can be modified to use the greedy choice without losing optimality.
• DP: state definition, transition, base cases, evaluation order.
• Two-pointer / sliding window: loop invariant.
• Graph algorithms: cite the algorithm’s correctness theorem and verify preconditions hold.
• Math: induction or direct calculation.

10. How To Explain Complexity

State time and space. Mention:

• Whether the bound is tight.
• Amortized vs worst case (e.g., dynamic array push is O(1) amortized, O(N) worst case).
• Assumptions (hash table O(1) average requires non-adversarial input).
• Constants when they matter (e.g., bitset gives 64× speedup over bool array).

11. How To Write Clean Code Under Time Pressure

See ../CODE_QUALITY.md. Quick rules:

• Meaningful names.
• Helper functions for distinct units.
• Validate at the boundary, not in hot loops.
• No globals.
• Standard library used idiomatically.

12. How To Test Manually

1. Walk through given example by hand. Record intermediate state.
2. Walk through one trivial case (empty / size 1).
3. Walk through one adversarial case.
4. Find at least one bug before submitting.

13. How To Recover When Stuck

Use the stuck protocol. Restate, brute force, examine constraints, try smaller examples, look for repeated work, look for monotonicity, look for graph modeling, ask for a hint.

14. How To Use Hints Without Failing The Interview

A hint is not a failure. Frozen silence is. Sample phrasing:

“I’ve explored two pointers and sliding window, but I’m having trouble seeing how to handle duplicates without O(N^2). Could you nudge me toward the right family of approach?”

Receive the hint, restate it, commit out loud, resume.

Why These Concepts Matter In Interviews

Algorithms are necessary but not sufficient. Of all rejected candidates with strong algorithm knowledge, the most common failure modes are:

• “Could not communicate clearly” (60%+)
• “Did not test their code” (40%+)
• “Could not articulate complexity” (30%+)
• “Got stuck and couldn’t recover” (30%+)
• “Misunderstood the problem” (20%+)

(Percentages are approximate, based on common interviewer feedback patterns.)

Phase 0 fixes all of these.

Required Problem Categories

Phase 0 problems are not algorithmically hard. The challenge is execution. Use only Easy problems:

• Two Sum
• Reverse String
• Valid Palindrome
• Maximum Subarray (Kadane’s)
• Best Time To Buy And Sell Stock
• Single Number
• Merge Two Sorted Lists
• Linked List Cycle
• Binary Tree Inorder Traversal
• Symmetric Tree
• Maximum Depth Of Binary Tree
• Climbing Stairs
• Move Zeros
• Contains Duplicate
• Intersection Of Two Arrays
• Reverse Linked List
• Valid Parentheses
• Implement Stack Using Queues
• First Bad Version
• Squares Of A Sorted Array

Solve each one applying the full framework. The point is not the answer; it’s the execution discipline.

Recommended Resources

• This curriculum’s FRAMEWORK.md, COMMUNICATION.md, CODE_QUALITY.md
• LeetCode Easy tier (filter by Easy)
• “Cracking the Coding Interview” (Gayle Laakmann McDowell) — chapters 1, 2, 6, 7 (the soft-skills chapters; skip the rest until later)

Hands-On Labs

Complete in order. Each lab uses the strict lab format from the curriculum spec.

1. Lab 01 — Problem Statement Reading
2. Lab 02 — Constraints Extraction
3. Lab 03 — Brute Force First
4. Lab 04 — Optimization Pathway
5. Lab 05 — Manual Testing
6. Lab 06 — Communication
7. Lab 07 — Stuck Recovery

Common Mistakes In Phase 0

• Skipping Phase 0 thinking “I already know this stuff” — execution skills are different from knowledge
• Solving Easy problems silently — the whole point is communication practice
• Skipping the brute force because the optimal is obvious
• Skipping the testing step because the code “looks right”
• Not timing yourself — you don’t know your real solving speed until you measure
• Treating clarifying questions as a checklist — they should feel natural and motivated, not robotic

Mastery Checklist

• Solve any LeetCode Easy in 12 minutes including brute force, optimization, testing, complexity
• Restate every problem in your own words without re-reading the prompt
• Ask 3+ relevant clarifying questions on every problem
• Always state the brute force first (even if 10 seconds long)
• Walk through at least one example by hand before submitting
• Explain complexity correctly on every problem
• Find at least one bug pre-submission on at least 30% of problems (this is good!)
• Never go silent for >60 seconds when working a problem
• Recover from being stuck using the stuck protocol within 3 minutes

Exit Criteria

Move to Phase 1 only when:

1. Mastery checklist 100% checked
2. Completed all 7 labs
3. Solved 25 Easy problems applying the full framework
4. Recorded yourself solving 3 problems and reviewed the playback for communication quality
5. Run a self-mock with one Easy problem you’ve never seen — pass with full framework execution

If any item fails, repeat Phase 0 with another 25 problems. Do not move forward with a weak baseline.

Lab 01 — Problem Statement Reading

Goal

Train the discipline of reading a problem statement deliberately — extracting structure, constraints, examples, and ambiguity — before any solving begins. Most candidate failures begin in the first 60 seconds when the candidate reads superficially and locks in a wrong mental model.

Background Concepts

• Active reading vs passive reading
• Structural parsing of a problem (input shape, output shape, constraints, examples, follow-ups)
• Identifying ambiguity vs underspecification
• Restating in your own words as a comprehension test

Interview Context

In a real interview, the prompt is often delivered verbally with a brief written version. You have ~3 minutes to load the entire problem into working memory before you start engaging. If you misunderstand something here, every subsequent step is wasted. Strong candidates always restate the problem out loud and ask 2–4 clarifying questions before touching anything.

Problem Statement

Given the problem statement below, in 5 minutes:

1. Read it twice.
2. Restate it in your own words.
3. List all constraints (explicit + implicit).
4. List 3 ambiguities you’d ask the interviewer about.
5. Construct 3 examples beyond the one given.

The problem (use as a fixed text for this lab):

“Given a list of meeting time intervals, determine if a single person could attend all meetings.”

Example: [[0,30],[5,10],[15,20]] → false.

Constraints

The problem deliberately omits constraint specification. That’s the point.

Clarifying Questions (you should generate)

Examples of good questions to surface from the prompt above:

• Are intervals inclusive on both ends, or [start, end)?
• Can intervals be zero-duration ([5,5])?
• Is the input pre-sorted?
• Are negative times possible?
• What are the realistic bounds on N and on the time values?
• Can two meetings sharing an endpoint be attended (e.g. one ends at 10, next starts at 10)?
• Are there any null or invalid intervals to validate?

Examples (you should generate)

Beyond the given:

• [] → true (empty)
• [[1,5]] → true (single)
• [[1,5],[5,10]] → endpoint-sharing case (depends on inclusivity)
• [[1,5],[2,3]] → fully nested overlap
• [[10,20],[1,5]] → unsorted, non-overlapping
• [[1,1],[1,1]] → zero-duration duplicates

Initial Brute Force

Compare every pair: O(N^2). For each pair, check if intervals overlap (max(a.start, b.start) < min(a.end, b.end) for half-open).

Brute Force Complexity

Time O(N^2), space O(1).

Optimization Path

Sort by start time, then walk through and check intervals[i].start >= intervals[i-1].end. Two thoughts emerge during sorting: ties on start, and the inclusivity semantics — both surface back to the clarifying questions. Optimal after the clarification.

Final Expected Approach

Sort + linear scan. O(N log N) time, O(1) extra space (or O(N) if sorting requires a copy).

Data Structures Used

• The interval array (input)
• Sort comparator on start time

Correctness Argument

After sorting by start, two meetings overlap ↔ some adjacent pair overlaps. Proof: if intervals i < j overlap, then for all k with i ≤ k < j, since intervals[k].start ≤ intervals[j].start < intervals[i].end ≤ intervals[k].end (after sort), k and k+1 overlap somewhere too. By induction, adjacent pairs cover all overlap detection.

Complexity

• Time: O(N log N) (sort dominates)
• Space: O(1) auxiliary if in-place sort, else O(N)

Implementation Requirements

For this lab, do NOT implement. Instead produce a written deliverable (described below).

Tests

Not applicable for this lab — written exercise only.

Follow-up Questions

• “What if instead of yes/no, we wanted the number of conflicts?”
• “What if we had to schedule N people across M rooms?” (becomes Meeting Rooms II)
• “What if the meetings stream in one at a time and we want online detection?”

Product Extension

This is “calendar conflict detection” — a real product feature. Ask yourself: what would Google Calendar do for 10,000 events? (Hint: indexed by day → small per-day scan, or interval tree for general queries.)

Language/Runtime Follow-ups

• In Python, sort is O(N log N) Timsort, stable. Beware of key=lambda x: x[0] — closure overhead vs operator.itemgetter(0).
• In Java, sort uses dual-pivot quicksort for primitives, Timsort for objects. Comparator allocation can dominate small inputs.
• In Go, sort.Slice is reflection-based and slow; prefer sort.Slice only when convenient or use sort.Sort with a typed slice.
• In C++, std::sort is introsort; comparator must be strict-weak-order or behavior is UB.

Common Bugs

• Using <= instead of < (or vice versa) due to misreading inclusivity
• Mutating input when interviewer expects pure function
• Off-by-one on boundary cases ([1,5] and [5,9])
• Not handling empty input

Debugging Strategy

If a test fails:

1. Print pairs where the algorithm decided “overlap” or “no overlap”
2. Walk through the smallest failing case by hand
3. Check inclusivity assumption — single source of most bugs here

Deliverable For This Lab

In your notebook (or a markdown file beside this lab), write:

1. Restatement. A 1–2 sentence paraphrase of the problem in your own words.
2. Clarifying questions list. 6+ questions, prioritized.
3. Implicit constraints list. What did the prompt fail to specify? (Inclusivity, sortedness, N bounds, etc.)
4. Examples list. 8+ examples covering: trivial, boundary, adversarial, multi-answer.
5. Brute force pseudocode. O(N^2) approach.
6. Optimization sketch. Just one paragraph.
7. Self-critique. Where in your reading did you make assumptions that the prompt didn’t justify?

Mastery Criteria

You complete this lab to mastery when:

• You restated the problem without re-reading the prompt
• You produced 6+ clarifying questions, none of which were answered by the prompt
• You found 3+ implicit constraints
• You produced 8+ examples spanning all category types
• You can articulate which of your assumptions were wrong (everyone makes some — the skill is noticing)

Repeat this lab with 3 different problem statements (pick any from LeetCode Easy) before declaring mastery.

Lab 02 — Constraints Extraction

Goal

Train the discipline of converting written constraints into algorithmic targets. Given 1 ≤ N ≤ 10^5, you should immediately think “O(N log N) is the budget, O(N^2) will TLE”.

Background Concepts

• The constraint-to-complexity mapping (FRAMEWORK.md)
• Operations-per-second budget on competitive judges (~10^8 simple ops/sec safe)
• Implicit constraints (memory, integer overflow, recursion depth)

Interview Context

In live interviews, the interviewer often omits explicit constraints, expecting you to ask. Constraints discipline the algorithm choice. Candidates who skip this step often write an O(N^2) algorithm that the interviewer was hoping they’d avoid.

Problem Statement

For each of the 10 problem prompts below, derive:

1. The complexity budget
2. At least one algorithm family that fits
3. At least one approach that does not fit and why

Prompts:

1. 1 ≤ N ≤ 20 — count subsets satisfying property X
2. 1 ≤ N ≤ 200 — shortest path in weighted graph with up to N^2 edges
3. 1 ≤ N ≤ 10^4, queries ≤ 10^5 — range sum
4. 1 ≤ N ≤ 10^5 — find duplicate
5. 1 ≤ N ≤ 5 × 10^5 — kth smallest in array
6. 1 ≤ N ≤ 10^6, integers up to 10^9 — count of pairs with sum ≤ K
7. N ≤ 10^9, queries Q ≤ 10^5 — count of integers in [1,N] divisible by K
8. T test cases, T ≤ 10^4, each with N ≤ 10^3 — pairwise XOR maximum
9. 1 ≤ a, b ≤ 10^18 — compute a^b mod p
10. Stream of up to 10^7 elements — top-K running

Constraints

The point of this lab is constraints. Treat each prompt as separate.

Clarifying Questions

For each prompt, list:

• What’s the operation budget?
• Is the time limit explicit (e.g., 1 sec, 2 sec)?
• Is there a memory limit (e.g., 256 MB)?
• Are values within int32 / int64 range?

Examples

Worked example for prompt #4 (N ≤ 10^5, find duplicate):

• Budget: ~10^7–10^8 ops → O(N), O(N log N), O(N · log_max) all fit
• Fits: hashset O(N), sort+scan O(N log N), Floyd’s cycle if input ∈ [1,N]
• Doesn’t fit: O(N^2) brute force (10^10 ops)

Initial Brute Force

Not applicable — meta-lab.

Brute Force Complexity

N/A.

Optimization Path

The optimization path here is constraint-to-algorithm mapping. Memorize the table from FRAMEWORK.md.

Final Expected Approach

For each prompt, write your final answer as:

Prompt #K:
  Budget: O(...)
  Fitting algorithm family: ...
  Disqualified approach: ... because budget / memory / overflow / etc.

Data Structures Used

The point is to map N range → DS choice:

• N ≤ 20: bitmask, recursion (no DS needed)
• N ≤ 200: 2D arrays (Floyd, etc.)
• N ≤ 10^4: O(N^2) DP arrays, simple sort
• N ≤ 10^5: hashmap, heap, sorted set, segment tree, Fenwick
• N ≤ 10^6: array + linear scan, two pointers, hash, no log factors
• N ≤ 10^9: math, binary search on answer, sieve segment

Correctness Argument

The argument here is budget: justify why your chosen algorithm fits within ~10^8 ops/sec * time-limit. Be explicit: N · log N = 10^5 · 17 ≈ 1.7 × 10^6 — comfortably fits 1-second limit.

Complexity

For each prompt, you produce both:

• The budget
• The justification per the table

Implementation Requirements

Written deliverable. No code.

Tests

Not applicable for this lab.

Follow-up Questions

For prompt #6 (10^6 elements, pairs with sum ≤ K):

• “What if values can be negative?” → may need different sort + two-pointer logic
• “What if we want to enumerate the pairs, not just count?” → output limit changes everything
• “What if the array streams in?” → online algorithm needed

For prompt #9 (a, b ≤ 10^18):

• “What if p is not prime?” → can’t use Fermat’s little theorem inverse
• “What if we need a^b exactly (no mod)?” → impossible for these sizes

Product Extension

In production, “constraint” often means “expected QPS × max payload size × peak time”. A request handler that’s O(payload_size^2) is fine for size 10 but catastrophic for size 10^4. Same intuition as competitive judges, just different vocabulary.

Language/Runtime Follow-ups

• Python: constant factor ~30–100× slower than C++. Halve your effective budget. N=10^5 with O(N^2) is risky in Python.
• Java: ~2–4× slower than C++. Beware autoboxing in hot loops.
• Go: ~2× slower than C++. Map operations have higher constants than unordered_map.
• C++: baseline. Use ios_base::sync_with_stdio(false) for fast I/O.
• JavaScript: ~3–10× slower than C++. Avoid object lookups in hot loops; prefer typed arrays.

Common Bugs

• Forgetting Q queries multiplies your budget (10^5 queries × 10^5 per-query = 10^10!)
• Forgetting T test cases (e.g., T = 10^4 with O(N^2) per test, N = 10^3 → 10^10)
• Underestimating constants in Python/JS
• Forgetting recursion depth limits (Python default 1000)
• Forgetting integer overflow at int32 boundary (~2 × 10^9)

Debugging Strategy

When code TLEs:

1. Recompute total operations: outer loops × inner work × test cases × queries
2. Check the constant factor (string concat in a loop is a classic disaster)
3. Profile to find the actual hotspot (often I/O, not algorithm)

Deliverable

For each of the 10 prompts above, write the structured answer block. Compare yours to the table at FRAMEWORK.md.

Mastery Criteria

• Correctly mapped 10/10 prompts to budget within 30 seconds each
• Identified at least one disqualifying approach for each (per query / total ops)
• Recognized the multiplier effect of T test cases / Q queries
• Identified at least 2 prompts where Python/JS would need extra care

Lab 03 — Brute Force First

Goal

Internalize the discipline of always producing a brute force before optimizing — even when the optimal is obvious. The brute force is your correctness oracle, your fallback, and your communication anchor.

Background Concepts

• Brute force as a baseline: it must be correct, even if slow
• Brute force as oracle: cross-check optimal output with brute on random small inputs
• Brute force as recovery: when stuck, you have something to deliver

Interview Context

Many candidates hear a problem, immediately recognize the optimal pattern, and start coding. The interviewer can’t tell whether they understand the problem or just memorized the answer. State the brute force first, even if it takes 30 seconds. Then, “I see this can be optimized to O(N log N) using … — would you like me to go straight to that, or step through a middle approach?”

Problem Statement

For each of the 5 problems below, in 10 minutes total:

1. State the brute force in pseudocode
2. State its complexity
3. State the optimization path (one or two sentences)

Problems:

1. Two Sum: find indices i, j such that a[i] + a[j] == target
2. Maximum Subarray: maximum sum contiguous subarray
3. Longest Substring Without Repeating Characters
4. Trapping Rain Water: given heights, total water trapped
5. Median Of Two Sorted Arrays

Constraints

For each problem, assume N ≤ 10^5 for sizing.

Clarifying Questions

For each problem, ask: “Are we returning the value or the actual subarray/indices?” — this affects implementation but not the brute-force complexity.

Examples

For Two Sum, brute is for i: for j > i: if a[i] + a[j] == target: return [i,j]. Test on [2,7,11,15], target=9 → [0,1].

Initial Brute Force

Per problem:

1. Two Sum: O(N^2) double loop
2. Maximum Subarray: O(N^3) — three nested loops (i, j, sum) — or O(N^2) with running sum
3. Longest Substring No Repeat: O(N^2) or O(N^3) — for each pair (i, j), check if substring has duplicates (set construction is O(N) per pair, so O(N^3))
4. Trapping Rain Water: O(N^2) — for each index, find max-left and max-right by scanning
5. Median Of Two Sorted Arrays: O(N+M) — merge then take median; even simpler O((N+M) log(N+M)) — concatenate + sort

Brute Force Complexity

As listed above. Be explicit about which O(N^k) you mean.

Optimization Path

1. Two Sum: Hashmap of seen values → O(N).
2. Maximum Subarray: Kadane’s running sum, reset to 0 if negative → O(N).
3. Longest Substring No Repeat: Sliding window with hashset → O(N).
4. Trapping Rain Water: Two-pointer with running max-left, max-right → O(N); or precompute prefix/suffix max → O(N) space.
5. Median Of Two Sorted Arrays: Binary search on partition → O(log min(N,M)).

Final Expected Approach

In the deliverable, write:

Problem K:
  Brute force pseudocode: ...
  Brute complexity: O(...)
  Optimization sketch: <pattern> → O(...)
  Why the optimization works (1 sentence)

Data Structures Used

For each problem, identify the diff between brute force DS and optimized DS — that diff is usually where the optimization lives.

Correctness Argument

For brute force, correctness is by exhaustive enumeration — usually trivial. For the optimized version, the correctness lives in why exhaustive enumeration is unnecessary (e.g., “if a[i] is the answer’s left half, then target - a[i] must be in the seen set”).

Complexity

Stated per problem above.

Implementation Requirements

For this lab, write the brute force only for problems 1, 2, 3 in your preferred language. Run on the given examples. Do not write the optimal version. The exercise is to make the brute force a habit.

Tests

For each implemented brute force:

• Smoke: 1 given example
• Edge: empty / single
• Random: 10 random small inputs (N ≤ 20), check no crash, plausible output

Follow-up Questions

• For Two Sum: what if there can be multiple valid pairs? Return all? First found?
• For Trapping Rain Water: what about 2D version (Trapping Rain Water II)? — different algorithm (heap-based BFS).
• For Median: what if K-th smallest instead of median? — same binary-search-on-partition idea.

Product Extension

In production code review, the brute force is often the only defensible code if you can’t justify the optimal. Reviewers prefer “obviously correct slow code” over “supposedly fast code with a subtle bug” — until the optimization is properly tested.

Language/Runtime Follow-ups

• Python: brute force should still complete for N ≤ 10^3 in <1s. Use it as oracle.
• Java: beware of Integer boxing in HashMap<Integer, Integer> for Two Sum — measurable slowdown.
• C++: brute force in C++ for N ≤ 5 · 10^3 finishes in well under 1s, useful for stress testing.

Common Bugs

• Off-by-one: for j = i+1 vs for j = i (Two Sum: must j > i unless duplicates allowed)
• Maximum Subarray: starting max_so_far = 0 instead of -infinity fails on all-negative arrays
• Sliding Window No-Repeat: not removing characters from the set when shrinking the window
• Trapping Rain Water: using < vs <= when comparing left and right pointers

Debugging Strategy

When the optimal disagrees with the brute on a small input: trust the brute. The brute is by construction correct. Your optimized version has the bug.

This is the stress testing pattern:

1. Write brute (slow, correct)
2. Write optimal (fast, suspicious)
3. Generate random small inputs
4. Compare outputs; on mismatch, print the input and inspect

Deliverable

In a notebook:

1. For each of the 5 problems, the structured block (brute pseudocode, complexity, optimization sketch).
2. For problems 1, 2, 3: real code for the brute force, with smoke + edge + random tests.
3. A 3-sentence reflection: which problem was hardest to resist writing the optimal first?

Mastery Criteria

• Wrote a brute force for all 5 in <2 minutes each (verbally or on paper)
• Stated the brute force complexity correctly
• Stated the optimization path in one sentence
• Resisted the urge to write the optimal first
• Used the brute force as oracle in at least one stress test

Lab 04 — Optimization Pathway

Goal

Train the explicit transition from brute force to optimal: identify what the brute force wastes (repeated work, missed monotonicity, overlooked sortedness), then close that gap with a specific technique.

Background Concepts

The optimization checklist (canonical):

1. Repeated work → memoize / DP
2. Sortedness → two pointers, binary search, sweep line
3. Monotonicity → binary search on answer
4. Local + global structure → sliding window, prefix sums
5. Pattern match to known DS → heap, monotonic stack/queue, segment tree, trie, union find
6. State compression → bitmask, hash of state
7. Math closed form → combinatorics, modular arithmetic, geometry
8. Graph modeling → BFS/DFS/Dijkstra/topo even on non-graph problems
9. Randomization / hashing → reservoir sampling, rolling hash
10. Approximation / amortization → when exact O(N) is hard, amortize

Interview Context

The interviewer wants to see your thinking process during optimization, not just the answer. Narrate: “The brute is O(N^2) because we recompute the prefix sum on every iteration. If we precompute prefix sums once, each query is O(1) and total is O(N).”

Problem Statement

For each of the 7 brute force descriptions below, identify which optimization checklist item applies, and produce a one-paragraph optimized approach.

Problems:

1. Brute: for each i, sum a[i..j] for all j; O(N^2). Goal: answer multiple range-sum queries.
2. Brute: for each pair (i, j), check if a[i] + a[j] = target; O(N^2). Goal: find pair sum.
3. Brute: generate all subsets, count those with sum K; O(2^N). N up to 30. Goal: count.
4. Brute: for each query (l, r), find min in a[l..r]; O(N) per query, N queries → O(N^2). Goal: range min queries on static array.
5. Brute: simulate game state recursively; many overlapping subproblems; O(2^depth). Goal: optimal game value.
6. Brute: for each i, find next j > i with a[j] > a[i]; O(N^2). Goal: next-greater-element array.
7. Brute: binary search would work if we knew the answer was in [L, R]. The answer is monotonic in some parameter. O(N · K) brute. Goal: find min K satisfying property.

Constraints

Assume N ≤ 10^5 for #1, #2, #4, #6, #7. N ≤ 30 for #3, allowing 2^N/2 meet-in-the-middle. N is the state-space size for #5.

Clarifying Questions

• “Are queries online or offline?” — offline allows different algorithms (Mo’s, offline BIT)
• “Is the array static or updated?” — static allows sparse table, dynamic needs Fenwick / segment tree

Examples

#1: prefix sums → query in O(1). #7: monotonic predicate → binary search the answer in O(log range).

Initial Brute Force

As stated above per problem.

Brute Force Complexity

As stated.

Optimization Path

For each problem, write the checklist item that applies and the optimized approach:

1. Sortedness / static structure: prefix sums → O(N) preprocess, O(1) query
2. Sortedness / hashing: hashmap of target - a[i] → O(N)
3. State compression: subset-sum DP O(N · K), or meet-in-the-middle O(2^(N/2)) → fits N=30
4. Pattern → known DS: sparse table O(N log N) preprocess, O(1) query (static); segment tree if dynamic
5. Repeated work: memoization → O(unique states)
6. Pattern → monotonic stack: O(N)
7. Monotonicity: binary search on answer → O(log range × verify)

Final Expected Approach

For your deliverable: each of the 7 problems gets:

• Checklist item identified
• Optimized algorithm
• Final complexity
• One-line reasoning

Data Structures Used

• Prefix sum array
• Hashmap
• DP table / memo dict
• Sparse table (immutable RMQ) / segment tree
• Monotonic stack
• (Binary search needs no DS)

Correctness Argument

For each optimization, the correctness argument is “the brute force result is preserved because X”:

• Prefix sums: sum(l..r) = prefix[r+1] - prefix[l] — algebraic identity
• Hashmap pair sum: every pair (i, j) with i < j is examined exactly once when we process j and look up target - a[j]
• Subset-sum DP: state (i, sum) covers all subsets of a[0..i] with given sum
• Sparse table: range min over a range of length L is min(table[k][l], table[k][r - 2^k + 1]) where k = log2(L) — overlap is fine because min is idempotent
• Memoization: same input → same output → cached
• Monotonic stack: pop while top is not greater than current; top after popping is the next-greater for popped elements
• Binary search on answer: predicate is monotonic by problem assumption

Complexity

Stated per problem.

Implementation Requirements

Implement #1, #2, #6 in your preferred language. Verify against brute force on random small inputs.

Tests

• Smoke: given example
• Edge: empty, single
• Random: 50 random tests against brute force; on mismatch, dump input
• Large: stress test at constraint maximum, time it

Follow-up Questions

• For #1: what if the array is updated? → Fenwick tree
• For #2: what if k-sum (k > 2)? → recurse to (k-1)-sum with target adjustment, or sort + multi-pointer
• For #4: what about range max? Range gcd? Range sum? → which are idempotent (sparse table) vs which need segment tree
• For #6: what about previous greater? Next smaller? → mirror the stack
• For #7: what about minimum fractional answer? → binary search on real numbers with precision

Product Extension

The optimization checklist is a real code-review tool. When reviewing a colleague’s PR with O(N^2) in a hot path, run through this checklist mentally. 80% of N^2 → N transitions are one of: prefix sum, hashmap, sort + two-pointer, monotonic stack.

Language/Runtime Follow-ups

• Python: prefix-sum approach gets a 5–10× speedup if you use NumPy np.cumsum instead of Python list.
• Java: monotonic stack with Deque<Integer> (autoboxing) is slower than a plain int[] with manual top index.
• C++: std::lower_bound / upper_bound give log-N binary search on sorted vectors with no manual implementation.
• JavaScript: Map is generally faster than plain object for hashmap when keys are non-string.

Common Bugs

• Prefix sum: off-by-one in prefix[r+1] - prefix[l]
• Two-pointer: forgetting to advance one pointer
• DP: wrong base case or wrong evaluation order
• Sparse table: log table off-by-one
• Monotonic stack: comparing > vs >= for the next-greater-or-equal variant
• Binary search on answer: monotonicity direction reversed

Debugging Strategy

For each optimization, do stress testing: write brute, write optimal, run on 100 random small inputs, compare outputs. This catches off-by-one bugs that survive the given tests.

Deliverable

1. The 7-problem structured analysis
2. Real implementation + tests for #1, #2, #6
3. A reflection paragraph: for which problem was the optimization checklist most useful? Was there a problem where you’d’ve gone the wrong direction without it?

Mastery Criteria

• Correctly identified the optimization checklist item for all 7
• Implemented #1, #2, #6 with passing tests including stress
• Can explain why each optimization preserves correctness, not just that it’s faster
• Found at least 1 bug via stress testing (good — that’s the point)

Lab 05 — Manual Testing

Goal

Train the discipline of manually walking through your code before claiming it’s done — and finding bugs before the interviewer does.

Background Concepts

• Trace tables: writing variable state row-by-row through a loop
• Edge cases as a reflex
• The “rubber duck” verbalization while tracing
• Pre-submission checklist

Interview Context

Strong candidates always test their code by walking through at least one example by hand, vocalizing variable state. The interviewer learns whether you can verify your own work — a critical engineering signal.

Weak candidates write the code and say “I think this works” without verification, then submit and the interviewer finds the bug. Even when the candidate would have caught the bug if they’d traced.

Problem Statement

You are given 4 small functions below, each with at least one bug. For each:

1. Construct a trace table for one input
2. Identify the bug
3. State a fix
4. Construct a test case that exposes the bug

Function 1 — is_palindrome(s: str) -> bool:

def is_palindrome(s):
    i, j = 0, len(s)
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

Function 2 — binary_search(a: list[int], target: int) -> int:

def binary_search(a, target):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        elif a[mid] < target:
            lo = mid
        else:
            hi = mid
    return -1

Function 3 — reverse_linked_list(head):

def reverse_linked_list(head):
    prev = None
    curr = head
    while curr.next is not None:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

Function 4 — max_subarray(a: list[int]) -> int:

def max_subarray(a):
    best = 0
    cur = 0
    for x in a:
        cur += x
        if cur < 0:
            cur = 0
        if cur > best:
            best = cur
    return best

Constraints

Standard.

Clarifying Questions

• For palindrome: case-sensitive? Treat as is.
• For binary search: input is sorted ascending, no duplicates.
• For reverse linked list: input may be empty.
• For max subarray: input may be all negative.

Examples

For each function, work a non-trivial input by trace table.

Initial Brute Force

N/A — debugging lab.

Brute Force Complexity

N/A.

Optimization Path

N/A.

Final Expected Approach

For each function, identify:

• The bug
• The minimal fix
• The triggering input

Reference answers (DON’T peek until you’ve tried):

1. is_palindrome: j = len(s) should be len(s) - 1 (or change loop to i < j and use s[i] == s[j-1] style — but as written, immediate IndexError on non-empty input). Trigger: any non-empty string.

2. binary_search: lo = mid should be lo = mid + 1, otherwise infinite loop. Trigger: target larger than a[lo] but smaller than a[hi-1], e.g., a=[1,2,3], target=3. Actually wait — let’s check: lo=0, hi=3, mid=1, a[1]=2 < 3, lo=1 (correct in the buggy version; mid would still advance). Try a=[1,3], target=3: lo=0, hi=2, mid=1, a[1]=3 → return 1. OK that works. Try a=[1,2], target=2: lo=0, hi=2, mid=1, a[1]=2 → return 1. Try a=[1], target=2: lo=0, hi=1, mid=0, a[0]=1<2, lo=0 → infinite loop. Trigger: target greater than max element.

3. reverse_linked_list: loop condition while curr.next is not None skips reversing the last node. Should be while curr is not None. Also crashes on empty input (head = None).

4. max_subarray: initializing best = 0 fails on all-negative input — returns 0 instead of the largest (least negative) element. Should be best = -infinity or best = a[0].

Data Structures Used

• Trace table: a small ASCII grid of variable values per loop iteration

Correctness Argument

A function is correct iff for every valid input it produces the right output. Manual tracing on edge cases is a cheap, reliable way to falsify “I think it works”.

Complexity

N/A.

Implementation Requirements

For each function:

1. Build a trace table on paper
2. Identify the bug
3. Write the fix
4. Write 4 unit tests covering the bug and adjacent cases

Tests

For function 1:

assert is_palindrome("") == True
assert is_palindrome("a") == True
assert is_palindrome("aa") == True
assert is_palindrome("ab") == False
assert is_palindrome("racecar") == True

For function 2:

assert binary_search([], 5) == -1
assert binary_search([5], 5) == 0
assert binary_search([1,2,3], 0) == -1
assert binary_search([1,2,3], 4) == -1   # the trigger
assert binary_search([1,3,5,7], 5) == 2

(Build similar for #3, #4.)

Follow-up Questions

• “How would you find this bug in production?” — logs, test failure, customer report
• “How would you prevent this class of bug?” — property-based testing, fuzz testing
• “What’s your debugging strategy when you can’t reproduce locally?” — see phase-10-testing-debugging/

Product Extension

These four bugs are real bug archetypes:

• Off-by-one (#1, #2)
• Loop termination (#2, #3)
• Initialization (#4)

In code review, scan specifically for: array bounds, loop conditions, accumulator initial values, null inputs.

Language/Runtime Follow-ups

• Python: index s[len(s)] raises IndexError immediately — defensive crash
• C/C++: would silently read garbage and possibly continue. Always be more defensive
• Java: ArrayIndexOutOfBoundsException like Python
• Go: panic with clear message

Common Bugs

The four bugs themselves are the common bugs:

• Off-by-one in array bounds
• Off-by-one in binary search update
• Loop terminates one iteration early
• Wrong initial accumulator value

Debugging Strategy

1. Trace table for the smallest failing input
2. Print state every iteration (the printf approach)
3. Verbalize the loop invariant — does the code uphold it?
4. Step through with a debugger (last resort, not first — debugger usage is slower than tracing for small problems)

Deliverable

1. Trace tables for all 4 functions (one per function)
2. Bug identification + fix + test suite for each
3. A “trace table template” you’ll reuse going forward

Mastery Criteria

• Found all 4 bugs via tracing (without peeking at answers)
• Wrote correct fixes
• Wrote tests that exposed each bug
• Can construct a trace table for an unseen function in <2 minutes
• Adopted “always trace one example before submitting” as a permanent habit

Lab 06 — Communication

Goal

Train explicit, structured communication during a coding interview: narrate intent, signpost transitions, ask before assuming, summarize at decision points.

Background Concepts

• The 6-phase communication structure (see COMMUNICATION.md)
• “Signposting” — short phrases that tell the listener which phase you’re in
• “Thinking out loud” without rambling
• Pause-points and decision-points

Interview Context

In a real interview, silence is your enemy. After ~30 seconds of silence, the interviewer becomes uncertain about your progress. After 90 seconds, they may interrupt — disrupting your thinking. Skilled candidates fill the time with structured narration that costs them little extra cognitive load.

Problem Statement

Record yourself solving 3 problems out loud, applying explicit communication scaffolding. Then transcribe and grade.

Recommended problems (Easy to keep cognitive load low):

1. Two Sum
2. Valid Parentheses
3. Linked List Cycle

For each, follow this script structure:

Phase 1 — Restatement (60–90 sec)

• “Let me restate to make sure I have it: …”
• Ask 2–3 clarifying questions explicitly

Phase 2 — Examples (60 sec)

• “Let me work through an example by hand: …”
• Construct one trivial and one adversarial example

Phase 3 — Brute Force (60–90 sec)

• “The simplest approach would be …”
• “That’s O(…) — clearly not optimal because …”

Phase 4 — Optimization Discussion (90 sec)

• “I notice ; that suggests …”
• Explicitly mention the checklist item you matched

Phase 5 — Coding (5–10 min)

• Narrate intent at each block: “Now I’ll initialize the hashmap, then iterate…”
• Pause and verify after each block

Phase 6 — Testing & Closing (2–3 min)

• “Let me trace through the given example…”
• “Edge cases I should check: …”
• “Final complexity: …”

Constraints

Time-box yourself: 12 minutes total per problem. If you’re going over, cut narration first, not coding.

Clarifying Questions

For Two Sum:

• “Can the input be empty?”
• “Can there be duplicates?”
• “Is exactly one valid pair guaranteed?”
• “Can I assume integers, or could they be floats?”

For Valid Parentheses:

• “Are only () [] {} allowed, or other characters?”
• “Does an empty string count as valid?”

For Linked List Cycle:

• “Should I detect the cycle’s start, or just whether it exists?”
• “Can I modify the list?”

Examples

For each problem, narrate one example by hand before coding.

Initial Brute Force

State and narrate.

Brute Force Complexity

State out loud.

Optimization Path

Narrate the transition: “The brute is O(N^2) because we compare every pair. If I use a hashmap, I can check in O(1) whether target - a[i] is already seen, giving O(N).”

Final Expected Approach

State the final approach as a single sentence before coding.

Data Structures Used

State the data structure explicitly: “I’ll use a hashmap from value → index.”

Correctness Argument

State the loop invariant: “After processing index i, the map contains every (value, index) pair from a[0..i].”

Complexity

State at end: time + space + amortized vs worst case.

Implementation Requirements

You must produce:

1. Three audio recordings (or written transcripts) of yourself solving the 3 problems with the script structure
2. Working code for all three (the bar is correct + clean, not optimal at first try)

Tests

For each problem, state aloud:

• “Smoke test: given example”
• “Edge: empty input”
• “Edge: single element / smallest non-trivial”
• “Adversarial: all duplicates / all negatives / max constraint”

Then trace through at least one example.

Follow-up Questions

After your solution, narrate:

• “If we wanted all pairs instead of one, we’d …”
• “If the input were a stream, we’d …”
• “If memory were tight, we could …”

Product Extension

These same communication patterns scale to design interviews, on-call discussions, and code reviews. The skill is permanent.

Language/Runtime Follow-ups

When narrating, mention language-specific notes:

• “In Python I’m using dict which is O(1) average; with adversarial input collisions it degrades to O(N).”
• “I’m using enumerate for index + value to keep the code clean.”

Common Bugs (in communication)

• Going silent for >60 seconds. Even saying “I’m trying to figure out the right invariant for the inner loop” is enough.
• Narrating typing instead of intent. “Now I’m typing for i in range(n)…” — bad. “Now I’ll iterate forward to maintain the prefix…” — good.
• Asking too many questions at once. Drip them; ask after motivation appears.
• Restating the prompt verbatim. Paraphrase, demonstrate comprehension.
• Refusing hints when stuck. Frozen silence is far worse than asking for a nudge.
• Forgetting to summarize at the end. “So the final approach is X with O(N) time and O(N) space; tested on the given example and edge cases.”

Debugging Strategy

After recording, listen back and grade yourself on:

• Did I signpost each phase?
• Did I ever go silent for >60 seconds?
• Did I narrate intent or just typing?
• Did I summarize at decision points?
• Did I sound confident or apologetic?
• Was my code-talk congruent with my code? (i.e., did I narrate one thing while coding another?)

Deliverable

1. 3 recordings or transcripts (12 minutes each)
2. Self-grading rubric per recording (the 6 questions above + score 0–10 per phase)
3. A list of 3 phrases / patterns you’ll reuse next time, and 3 you’ll avoid

Mastery Criteria

• Recorded all 3 problems
• Self-graded honestly (most candidates score 4–6/10 on first attempt — that’s expected)
• Identified at least 3 specific things to improve
• On a re-recording of one problem, scored at least 2 points higher
• No silent gaps > 30 seconds in your final recording
• Narration tracked code 90%+ of the time (no divergence)

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?”

Phase 1 — Programming & Data Structure Foundations

Target level: Easy → low-Medium Expected duration: 2 weeks (12-week track) / 4 weeks (6-month track) / 4 weeks (12-month track) Weekly cadence: ~5 labs/week + 30–50 problems applying every data structure under the framework

Why This Phase Exists

Phase 0 fixed your execution — how to read, communicate, derive constraints, brute force, optimize, test, and recover. Phase 1 fixes your vocabulary: the data structures and language-runtime concepts that 95% of every coding interview rests on.

If you cannot, on demand, state the amortized cost of a dynamic-array push, the worst-case behavior of a hash map under adversarial keys, why s += c in a Python loop is O(N²), what happens to your for-loop when you mutate the collection it iterates, and the difference between deep and shallow copy in your language — you do not have a foundation. You have a list of words.

This phase makes the foundation real. Every concept comes with: internal representation, complexity table, memory behavior, language-specific gotchas (Python, Java, Go, C++, JS/TS), interview traps, common bugs, and testing strategy.

What You Will Be Able To Do After This Phase

• Pick the correct data structure for any Easy/Medium problem in under 60 seconds.
• State the worst-case, average-case, and amortized complexity of every operation on every fundamental DS.
• Predict your code’s memory and cache behavior, not just its asymptotic time.
• Write idiomatic code in your interview language without falling into language-specific traps.
• Recognize when a problem is really a hash map / heap / monotonic stack problem in disguise.
• Implement, from scratch, every data structure listed below — without notes — in under 20 minutes each.

Concepts To Master

You must master every item below before moving to Phase 2. Pattern problems in Phase 2 assume fluency with these primitives.

Data Structures

1. Arrays — operations, complexity, memory layout, cache behavior, dynamic resizing amortization, gotchas per language
2. Strings — immutability, encoding pitfalls, concat-in-loop blowup, substring complexity
3. Hash Maps — hashing, collisions, load factor, adversarial inputs, ordered vs unordered, custom hash for tuples
4. Hash Sets — operations, set algebra, when to use vs map
5. Linked Lists — singly/doubly, sentinels, tail pointer, common manipulation patterns
6. Stacks — array-backed vs linked, monotonic stack preview
7. Queues — deque, ring buffer, priority queue preview
8. Heaps — binary heap, sift up/down, complexity, top-K pattern
9. Sorted arrays / sorted sets — binary search, bisect, sorted-set complexity per language
10. Trees — binary, BST, traversals iterative + recursive, balanced vs unbalanced
11. Tries — operations, space cost, alphabet size considerations
12. Graphs — adjacency list, matrix, edge list, when each
13. Disjoint Set Union — path compression + union by rank
14. Bitsets / Bit Manipulation — set/clear/popcount, common idioms
15. Counters / Multisets — Counter, HashMap+counter pattern, multiset alternatives

Runtime Concepts

1. Stack vs heap memory
2. Scope and lifetime
3. Value vs reference semantics
4. Mutable vs immutable
5. Hash collisions and adversarial keys
6. Iterator invalidation
7. Garbage collection basics (refcount vs tracing)
8. Memory leaks (especially in GC’d languages)
9. Deep vs shallow copy
10. Recursion depth and stack overflow

Why These Concepts Matter In Interviews

Most “I knew the algorithm but couldn’t get it to pass” failures aren’t algorithmic. They are foundation failures:

• “My hash map is slow” → adversarial collision pattern in the input.
• “My recursion crashed” → no idea Python’s default recursion limit is 1000.
• “I edited the list while iterating and got weird output” → iterator invalidation.
• “My BFS queue is slow” → using list.pop(0) instead of deque.popleft.
• “Java said ConcurrentModificationException” → the JDK’s fail-fast iterator policy.
• “Go map iteration ordered differently every run” → intentional non-determinism for hash-flooding defense.
• “C++ vector reference invalidated after push_back” → reallocation moved the storage.
• “JS object stringified my int keys to strings” → all object keys are strings; use Map.

Every one of these is on the rubric somewhere as “implementation correctness” or “language fluency.” Phase 1 closes them.

Inline Data Structure Reference

The remainder of this README is a data-structure and runtime reference manual. Read it linearly the first time. Skim it as a reference any time you forget a complexity, language API, or gotcha.

1. Arrays

Internal Representation

A contiguous block of memory holding fixed-size elements indexed by offset. Static arrays have fixed size; dynamic arrays (Python list, Java ArrayList, Go slice, C++ vector, JS Array) wrap a static array and grow it geometrically.

Operations and Complexity

Memory Layout & Cache Behavior

Contiguous memory means the CPU prefetcher can stream elements predictively, giving arrays the best cache locality of any data structure. A linear scan over an int[] is typically 5–20× faster than the same scan over a linked list of the same length, even though both are O(N). When constants matter (HFT, hot loops), this difference dominates.

Dynamic Resizing Amortization

Geometric growth (typically 2× or 1.5×) gives O(1) amortized append: doubling means total work to grow from 1 to N is 1 + 2 + 4 + … + N = 2N - 1, amortized to O(1) per push. Linear growth (+1) gives O(N) amortized — never use it.

Language-Specific Gotchas

• Python: list overallocates with growth factor ~1.125; arr.pop(0) is O(N); use collections.deque for queue. Lists are heterogeneous (each slot is a PyObject*), defeating cache locality. Use array.array or NumPy for primitive-typed storage.
• Java: ArrayList is Object[] — boxing for primitives. Use int[] for hot paths. ArrayList.remove(0) is O(N). Arrays.asList(arr) returns a fixed-size view, not a real ArrayList.
• Go: Slices are a 3-tuple (ptr, len, cap). append may or may not reallocate — appending to one slice can silently mutate another sharing storage. Always check capacity. s = s[:0] reuses storage; s = nil releases it.
• C++: std::vector<T> reallocates on push_back past capacity, invalidating all iterators and references. Reserve up front when you know the size. vector<bool> is a packed bitset, not bool[] — its operator[] returns a proxy.
• JS/TS: Arrays are dense or sparse; sparse arrays (a[1000000] = 1) have terrible perf. arr.shift() is O(N). Holes (new Array(10)) skip during forEach but not during for.

Common Interview Traps

• “Insert in the middle” — be sure they don’t actually want a different DS.
• “In-place” — explicitly disallows the cheap copy-to-new-array solution.
• Off-by-one at boundaries: [l, r) vs [l, r].

2. Strings

Internal Representation

An array of code units (bytes for char[], UTF-16 code units in Java/JS, variable-width in Python 3 with PEP 393 latin-1/UCS-2/UCS-4). In most languages, strings are immutable — every “modification” allocates a new string.

Operations and Complexity

Immutability

Java/Python/JS strings are immutable. So this loop:

s = ""
for c in chars:
    s += c   # O(N) per iteration → O(N²) total

This bug shows up in real interviews and gets candidates dinged for not knowing language internals. Use "".join(chars) (Python), StringBuilder (Java), [].join('') (JS), strings.Builder (Go).

Encoding Pitfalls

• “String length” in characters vs bytes vs grapheme clusters can all differ. "é" may be 1 codepoint or 2 (e + combining accent) → 2 codepoints, 1 grapheme.
• Python len("😀") == 1; Java "😀".length() == 2 (UTF-16 surrogate pair).
• JS "😀".length === 2 for the same reason; iterate with for…of to get codepoints.
• Always clarify: “Are inputs ASCII?” — if no, ask whether the unit of “character” is byte, codepoint, or grapheme.

Substring Complexity

Substring extraction copies the underlying chars in most modern languages. Go strings are immutable byte slices and substring is O(1) view (but converting to/from []byte is O(N)).

Language-Specific Gotchas

• Python: strings are immutable; use lists of chars and "".join() for building. s[::-1] is idiomatic reverse.
• Java: String s += c → quadratic. Use StringBuilder. String.intern() exists but rarely needed in interviews.
• Go: string is immutable bytes; []byte(s) and string(b) each allocate. Range over a string yields (i, rune), not (i, byte).
• C++: std::string is mutable; SSO (small string optimization) keeps short strings on the stack. s.c_str() is null-terminated.
• JS/TS: strings are UTF-16 code units; emoji and non-BMP chars are 2 units long.

3. Hash Maps

Internal Representation

A bucket array, indexed by hash(key) % capacity. Collisions resolved by either separate chaining (linked list / tree per bucket — Java since 8 promotes long chains to red-black trees) or open addressing (Python, Ruby — probe sequence in the same array).

Operations and Complexity

Load Factor

The capacity / size ratio. When load factor exceeds a threshold (~0.75 typical), the table doubles and rehashes — this is amortized O(1) per insert but O(N) for the resize itself.

Adversarial Inputs

A static, public hash function lets an attacker craft N keys that all hash to the same bucket → O(N²) insertion. Real-world history: this brought down Java web servers in 2003 and PHP in 2011. Modern languages (Python PYTHONHASHSEED, Go map randomization, Java tree fallback) defend against this.

In an interview, if the problem says “the input may be adversarial,” do not rely on hash maps for worst-case bounds — use sorting + binary search or a balanced BST.

Ordered vs Unordered

• Insertion-ordered: Python 3.7+ dict, Java LinkedHashMap, JS Map.
• Sorted (by key): Java TreeMap, C++ std::map, Python sortedcontainers.SortedDict.
• Hash, no order guarantee: C++ std::unordered_map, Java HashMap (unordered as of 8+), Go map (intentionally randomized).

If the problem requires ordered iteration, do not use a plain hash map.

Custom Hash for Tuples / Composite Keys

• Python: tuples of hashable items are hashable for free.
• Java: must implement both equals and hashCode for any custom key class. Forgetting one is a top-10 interview bug.
• Go: map keys must be “comparable types” — structs of comparables work, slices/maps don’t.
• C++: must specialize std::hash<T> or pass a custom hasher to unordered_map.
• JS: object keys are coerced to strings; use Map for object-keyed maps.

Common Interview Traps

• Mutating a key after insertion (its hash changes; the map can’t find it).
• Iterating while mutating → ConcurrentModificationException (Java) / RuntimeError (Python).
• Assuming O(1) without acknowledging worst case.

4. Hash Sets

Operations and Complexity

Same as hash map (a hash set is conceptually a hash map with null values).

Set Algebra

• Union: A ∪ B — Python A | B, Java A.addAll(B), C++ manual.
• Intersection: A ∩ B — iterate the smaller, lookup in the larger.
• Difference: A \ B — iterate A, skip if in B.
• Symmetric difference: A △ B — (A ∪ B) \ (A ∩ B).

Set vs Map: When To Choose

Use a set when you only need presence; use a map when you need associated value (count, index, parent, etc.). Many “use a set” problems become trivially easier with a map (e.g., Two Sum needs a value → index map, not a set).

Language-Specific Gotchas

• Python: set and frozenset; tuples are hashable, lists are not.
• Java: HashSet, LinkedHashSet, TreeSet.
• Go: no built-in set — use map[T]struct{} (zero-byte value).
• C++: std::unordered_set, std::set (sorted).
• JS/TS: Set preserves insertion order; objects are reference-equal.

5. Linked Lists

Singly vs Doubly

• Singly: each node has next. Reverse, cycle detection, two-pointer dance.
• Doubly: each node has next and prev. Required for O(1) erase given an iterator (LRU cache pattern).

Sentinels (Dummy Nodes)

A dummy head node simplifies edge cases: “what if the list is empty?” “what if we delete the first node?” become non-special. Always use a dummy when you have to return a head pointer that may change.

dummy = ListNode(0)
dummy.next = head
prev = dummy
# … operations on prev.next …
return dummy.next

Tail Pointer

Maintaining a tail pointer makes append O(1) (otherwise O(N)). Always-mark whether your manipulation invalidates the tail.

Common Manipulation Patterns

• Reverse iteratively: three pointers prev, curr, next.
• Reverse recursively: reverse(head.next) then head.next.next = head; head.next = None.
• Find middle: slow/fast pointers; fast moves 2× slow.
• Detect cycle: Floyd’s tortoise and hare.
• Merge two sorted lists: dummy head + zip pattern.
• Remove Nth from end: lead pointer ahead by N.

Operations and Complexity

*Singly: O(N) because you need the previous node; O(1) if you have the previous pointer.

Language-Specific Gotchas

• Python: define class ListNode: __slots__ = ('val', 'next') for memory; default uses a __dict__.
• Java: LinkedList<T> exists but is rarely the right choice; ArrayDeque beats it on most operations.
• Go: standard library has container/list (doubly linked, generic-erased before Go 1.18).
• C++: std::list (doubly), std::forward_list (singly).
• JS: typically write class Node { constructor(v) { this.val = v; this.next = null; } }.

6. Stacks

Implementations

Array-backed (dynamic array, push/pop end) or linked (push/pop head). Array-backed is faster in practice due to cache locality.

Operations and Complexity

Monotonic Stack Preview

A monotonic stack maintains elements in increasing or decreasing order. Used for next-greater / next-smaller / largest rectangle in histogram. Preview only — full pattern in Phase 2.

for x in arr:
    while stack and stack[-1] < x:
        # process element being popped: x is its next-greater
        stack.pop()
    stack.append(x)

Language-Specific Gotchas

• Python: use list directly with append/pop. Don’t use queue.LifoQueue (locks).
• Java: prefer ArrayDeque over the legacy Stack (synchronized, slow).
• Go: slice with s = append(s, x) and s[len(s)-1] / s = s[:len(s)-1].
• C++: std::stack<T> adapter on std::deque; or just use vector.
• JS: array push/pop.

7. Queues

Variants

• Plain queue (FIFO): enqueue rear, dequeue front.
• Deque (double-ended): push/pop both ends in O(1).
• Ring buffer / circular buffer: fixed-capacity deque on a static array.
• Priority queue: see Heaps.

Operations and Complexity

Language-Specific Gotchas

• Python: collections.deque for queue; never use list.pop(0) (O(N)).
• Java: ArrayDeque<T> for both stack and queue. LinkedList works but slower. Avoid java.util.Queue<T> q = new LinkedList<>(); for hot paths.
• Go: no built-in deque; container/list exists. Most CP code uses a slice as a queue with q[head:] (lazy popfront).
• C++: std::deque (random-access amortized O(1)) or std::queue adapter.
• JS: array push/shift works but shift is O(N); use a custom ring buffer for large queues.

8. Heaps

Binary Heap

A complete binary tree where each parent ≤ children (min-heap) or ≥ (max-heap). Stored in an array: parent of i is (i-1)/2, children are 2i+1 and 2i+2.

Operations and Complexity

Top-K Pattern (Preview)

• “Top K largest” → min-heap of size K. Push every element; if size > K, pop. Final heap = top K.
• “Stream median” → max-heap (lower half) + min-heap (upper half), balanced.

Language-Specific Gotchas

• Python: heapq is a min-heap of any orderable; for max-heap, push -x. Tuples break ties lexicographically — careful with non-orderable secondary keys.
• Java: PriorityQueue<T> is a min-heap by default; pass Comparator.reverseOrder() for max. peek() may return null on empty.
• Go: container/heap requires you to implement the heap.Interface. Significant boilerplate.
• C++: std::priority_queue<T> is a max-heap by default. Use std::priority_queue<T, vector<T>, greater<T>> for min-heap. Or use make_heap + push_heap + pop_heap on a vector.
• JS: no built-in; write your own or use a library.

9. Sorted Arrays / Sorted Sets

Binary Search

On a sorted array, find a target or its insertion point in O(log N). Three canonical variants:

• Lower bound: smallest index where a[i] >= target.
• Upper bound: smallest index where a[i] > target.
• Exact match: lower bound + check a[i] == target.

Operations on Sorted Set / Multiset