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 4521719 · 2026-07-13 02:17 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.”

p01 Two Sum — Progressive Hints

Rule: Read ONE hint. Set a 5-minute timer. Try again. Only read the next hint if the timer expires.

Hint 1 — Pattern family

You don’t need to compare every pair. Think about what information you’d want to have already seen by the time you reach element nums[i].

Hint 2 — Data structure family

For each element x you encounter, there is exactly one “partner value” that would solve the problem. What data structure lets you check in O(1) whether you’ve seen a specific value already?

Hint 3 — The key insight

For each x at index i, the value you need to find is target − x. If you’ve stored every previously seen value with its index, you can ask the question “have I seen target − x before?” in O(1).

Hint 4 — Pseudocode skeleton

seen = empty map (value → index)
for i in 0 to N-1:
    let x = nums[i]
    let complement = target - x
    if complement is in seen:
        return [seen[complement], i]
    add x → i to seen

Pay close attention to the order of the check and the insert. There is exactly one correct order.

Hint 5 — Full algorithm in words

Walk the array left to right with a hashmap seen that grows as you go. For each element x at index i:

1. First, check if target − x is already a key in seen. If yes, return [seen[target − x], i] — you’ve found the pair, with the earlier index first.
2. Then, insert x → i into seen.

Why check before insert? If you insert first, then for input [3, 3] with target = 6, at index 0 you’d insert 3 → 0, then check for complement 3 and find it — but the only index satisfying it is 0 itself, returning [0, 0], which violates “two distinct indices”. Checking before inserting guarantees the complement was found at a strictly earlier index.

The loop invariant: at the start of iteration i, seen contains exactly the values nums[0..i-1] mapped to their indices.

Time: O(N) — one pass, O(1) per element. Space: O(N) — the map can hold up to N entries.

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.”

p02 Valid Parentheses — Progressive Hints

One hint, 5-min timer, retry. Repeat.

Hint 1 — Pattern family

The string is processed left to right. At any point, you have unresolved openers. The closer you read needs to match the most recent unresolved opener — not just any opener. What property does “most recent” have?

Hint 2 — Data structure

LIFO — last-in-first-out. There is exactly one data structure for this.

Hint 3 — Key insight

Push every opener onto a stack. When you see a closer, the top of the stack must be the matching opener — pop and compare types. If it isn’t, or the stack is empty, the string is invalid. At the end of the string, the stack must be empty.

Hint 4 — Pseudocode

stack = []
pairs = { ')':'(', ']':'[', '}':'{' }
for c in s:
    if c is an opener:
        push c
    else if c is a closer:
        if stack is empty: return false
        if pop() != pairs[c]: return false
return stack is empty

There are exactly three failure branches. Make sure you have all three.

Hint 5 — Full algorithm with the three correctness branches

Three places the answer becomes False — miss any one and you have a bug:

1. Mid-loop, empty-stack on close: A closer arrived with no unmatched opener to match. Example: "]".
2. Mid-loop, top-mismatch on close: The top of the stack is an opener of the wrong type. Example: "(]" — top is (, closer is ], mismatch.
3. End of loop, non-empty stack: Openers remain unmatched. Example: "((".

Use a constant dict {')':'(', ']':'[', '}':'{'} so the match check is one line, not six. This is what the interviewer flags as “data-driven code” — it generalizes when they add <> as a follow-up.

Time O(N), Space O(N) worst case (all openers, no closers).

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.”

p03 Best Time to Buy/Sell Stock — Progressive Hints

One hint at a time. 5-min timer between hints.

Hint 1 — Reframe the problem

You’re searching for the maximum of prices[j] - prices[i] over all valid (i, j) with i < j. That’s a 2D search. Can you reduce one dimension by asking: “for a fixed j, what is the best i?”

Hint 2 — What helps at each j

For each candidate sell-day j, the most profitable buy-day is whichever earlier day had the lowest price. So at each j, you only need to know one thing about the past: the minimum price among days 0..j-1.

Hint 3 — The key insight

Walk left to right. Maintain min_so_far = minimum of all prices seen before today. For each price today: candidate profit is price - min_so_far; update the running best. Then update min_so_far with today’s price.

This makes the algorithm O(N) time and O(1) space.

Hint 4 — Pseudocode

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

Pay attention to the order of those two updates inside the loop. One order is right, the other has a subtle bug visible only on harder follow-ups.

Hint 5 — Full algorithm + order rationale

Initialize min_so_far = +∞ (so the first iteration’s price - min_so_far is very negative and doesn’t pollute best, which starts at 0). For each price:

1. First: compute best = max(best, price - min_so_far). This uses the min from STRICTLY BEFORE today — we cannot sell on the same day we buy.
2. Then: update min_so_far = min(min_so_far, price). Now today’s price becomes available for future sell-days.

If you reverse the order (update min first, then compute best), you’d compute price - price = 0 on the day a new min appears, which is harmless here but causes phantom self-trades on the multi-transaction variants. Get the discipline right now.

The correctness proof: for any optimal pair (i*, j*), when the loop reaches j*, min_so_far ≤ prices[i*] (because i* < j*). So the algorithm sees at least the optimal profit, and we take the max, so we capture it.

Time O(N), Space O(1).

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.”

p04 Merge Sorted Array — Progressive Hints

One hint. 5-min timer. Retry. Repeat.

Hint 1 — Why front-merge fails

If you merge from the front (smallest first) and write into nums1[0], you overwrite valid nums1[0] data before reading it. To avoid this, you’d need to shift nums1’s data right — that’s O(M) per insert, total O(M·N).

What part of nums1 is guaranteed safe to write into without overwriting valid data?

Hint 2 — The free space

The trailing zeros in nums1 are a hint. Those positions are reserved for the merge output. If you write the largest unprocessed element into the rightmost free slot, you’re writing into space that’s guaranteed not to contain valid data.

Hint 3 — Three pointers

Use:

• i = m - 1 — pointer into the valid part of nums1 (largest unprocessed value)
• j = n - 1 — pointer into nums2
• write = m + n - 1 — where the next-largest goes

At each step: compare nums1[i] and nums2[j]. The larger one goes to nums1[write]. Decrement the source pointer and write.

Hint 4 — Pseudocode

i = m - 1
j = n - 1
write = m + n - 1
while j >= 0:
    if i >= 0 and nums1[i] > nums2[j]:
        nums1[write] = nums1[i]
        i -= 1
    else:
        nums1[write] = nums2[j]
        j -= 1
    write -= 1

Two non-obvious choices:

• Loop condition is j >= 0, not i >= 0. Why?
• The comparison guards i >= 0 explicitly. Why?

Hint 5 — Full reasoning

Why loop on j >= 0 (not i >= 0)? When nums2 runs out, the remaining nums1[0..i] is already where it needs to be — sorted, and to the left of all written slots. No work needed. But if nums1’s valid prefix runs out first (i < 0), we must keep copying from nums2. So j >= 0 is the condition that captures “still work to do.”

Why the i >= 0 guard in the comparison? Once i < 0, accessing nums1[i] is reading from index -1 — in Python that wraps to the last element (a written slot), corrupting comparisons. The i >= 0 and ... short-circuits to the else branch (copy from nums2), correctly handling the case.

The invariant that makes it work: At every step, write == i + j + 1. That means nums1[write] is the position immediately AFTER the unprocessed prefixes — guaranteed empty/safe to overwrite. This invariant is the formal proof of “no overwrite.”

Time O(M+N), Space O(1).

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.”

p05 Climbing Stairs — Progressive Hints

One hint. 5-min timer. Retry.

Hint 1 — Decompose by last move

To reach step n, what was your last move? Only two possibilities. Each leads to a sub-problem of the same shape.

Hint 2 — Recurrence

Let f(n) = number of distinct ways to reach step n. The last move was either a 1-step (so the previous state was step n-1) or a 2-step (so the previous state was step n-2). These are disjoint sets of paths.

What does this give you?

Hint 3 — Recognize the pattern

f(n) = f(n-1) + f(n-2) — Fibonacci. You only need to track the last two values, so you don’t need an array.

Hint 4 — Pseudocode

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

Make sure you handle n == 1 and n == 2 as base cases — the loop doesn’t execute for them, so they need explicit returns.

Hint 5 — The full DP recipe (apply this to EVERY DP problem from now on)

1. State: f(k) = number of distinct ways to reach step k.
2. Recurrence: f(k) = f(k-1) + f(k-2) — justified by case-split on the last move.
3. Base cases: f(1) = 1, f(2) = 2. (Two base cases because the recurrence reaches back 2.)
4. Order: Bottom-up, smaller k first.
5. Space: Only last two values referenced → two scalars, O(1) space.

The most common interview mistakes:

• Plain recursion without memo (O(2^N) — TLE).
• DP array of size N+1 (works, but signals you didn’t see the compression).
• Forgetting one base case (off-by-one on n=1 or n=2).
• Confusing this with “distinct step sets” instead of “distinct sequences” — 1+2 and 2+1 are different here.

Time O(N), Space O(1).

Week 2 — Linked Lists + Kadane Intro

Days 8–14 · 5 flagship problems · ~25 LC Bank · 0 mocks

Theme

Pointer mechanics + your first non-trivial DP pattern. The linked-list problems exist almost entirely so the interviewer can watch you draw boxes and arrows on a whiteboard without panicking. Kadane is your first taste of “the DP recurrence hides inside a single scan.”

Goals

• Pointer manipulation without losing nodes (reverse, merge, cycle-detect)
• The three-pointer dance for in-place reversal (prev / curr / next)
• Floyd’s tortoise-and-hare and why it provably terminates
• Kadane’s algorithm as a 1D DP with two-state collapse to scalars
• HashSet as the brute-force baseline for duplicate detection — then trade off

Daily Schedule

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

LC 234 (Palindrome Linked List), 876 (Middle of Linked List), 83 (Remove Duplicates from Sorted List), 203 (Remove Linked List Elements), 160 (Intersection of Two Linked Lists), 92 (Reverse Linked List II — Medium), 19 (Remove Nth Node from End), 142 (Linked List Cycle II — Medium), 121 (Best Time, again, for muscle memory), 122 (Best Time II — greedy), 53 (Maximum Subarray — your flagship), 152 (Maximum Product Subarray — Medium, the “hidden two-state” follow-up), 198 (House Robber), 70 (Climbing Stairs, again), 746 (Min Cost Climbing Stairs), 217 (Contains Duplicate — your flagship), 219 (Contains Duplicate II — sliding-window preview), 268 (Missing Number), 136 (Single Number — XOR trick), 387 (First Unique Character), 242 (Valid Anagram), 49 (Group Anagrams — preview), 599 (Minimum Index Sum of Two Lists), 350 (Intersection of Two Arrays II), 202 (Happy Number — Floyd on integers).

Readiness Gate

• All 5 flagship problems Section 9 checklists green
• 25+ Bank problems solved unaided
• Can draw the three-pointer reverse on a whiteboard from memory in <60 seconds
• Can explain why tortoise-and-hare must meet inside a cycle (modular arithmetic argument)
• Can state Kadane’s recurrence as dp[i] = max(nums[i], dp[i-1] + nums[i]) and the two-scalar collapse
• Honest self-assessment: Level Delta = Senior or above on at least 2 flagships (Kadane is the hard one)

What’s intentionally NOT here yet

• Doubly linked lists — Phase 1 has it; flagship coverage is in Month 2 (LRU Cache).
• Reverse Linked List II (range reverse) — in the Bank; flagship treatment comes in Month 3.
• Cycle II (find the start of the cycle) — Bank only; the math derivation is Month 3 flagship.
• Kadane variants (max product, circular subarray) — Bank previews; flagship treatment in Month 5 DP block.

p06 — Reverse Linked List

Source: LeetCode 206 · Easy · Topics: Linked List, Recursion Companies (2024–2025 frequency): Microsoft (very high), Amazon (very high), Meta (high), Apple (high), Google (medium), Bloomberg (high) Loop position: phone screen warmup; also the “first 5 min” of harder list problems (LC 25, LC 92, LC 234)

1. Quick Context

The linked-list version of FizzBuzz. The interviewer is not testing whether you can do it — they are testing whether you can do it without losing a node. The signature failure mode is curr = curr.next AFTER you’ve already overwritten curr.next to point backward — now you have no way to advance. Every “reverse in place” problem in interview lore (groups of K, reverse-between-indices, palindrome-check-by-reversing-half) reuses this kernel.

What it looks like it tests: linked list manipulation. What it actually tests: can you hold three references in your head at once and execute the swap in the right order under pressure? Many candidates know “use prev / curr / next” but write the four lines in the wrong order and silently produce a list of length 1.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/reverse-linked-list/

STOP. Set a 12-minute timer. Code BOTH the iterative and recursive versions in a scratch file. Do not read past this section until either is solved or the timer expired.

If you’ve done this before: do it again, and time only the iterative version. Target: 4 min, zero scratch paper, written correctly first try. The recursive version should follow in another 4 min. If iterative takes >6 min, you don’t have the three-pointer dance memorized — fix that before moving on.

3. Prerequisite Concepts

• Singly linked list node model: next pointer, sentinel None (phase-01 §4 Linked List Pointers)
• In-place mutation vs. allocation tradeoff: this problem can be solved by building a new list (O(N) extra space) OR by pointer rewiring (O(1) extra). Interviewers expect O(1).
• Recursion stack frame cost: the recursive version uses O(N) stack space; on real production systems this stack-overflows around N=10^4 in CPython without sys.setrecursionlimit bump.

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

Step 1 — Restate: “Given the head of a singly linked list, return the head of the same list with all next pointers reversed.”

Step 2 — Clarify:

• “Is the list empty? Single node?” (Both possible; handle separately.)
• “Should I mutate the input or return a new list?” (Mutate in-place is the expected answer; ask anyway.)
• “Doubly linked or singly?” (Singly per LC; doubly is a trivially different rewrite.)
• “Is there a risk of cycles in the input?” (No per LC, but in real production code this is a question worth asking.)

Step 3 — Constraints: N up to 5000 per LC. Both O(N) iterative and O(N) recursive fit. Iterative is preferred for space.

Step 4 — Examples:

• 1 → 2 → 3 → 4 → 5 → 5 → 4 → 3 → 2 → 1
• 1 → 2 → 2 → 1 (the smallest non-trivial case)
• 1 → 1 (single node — does your code crash on this?)
• None → None (empty list — does your code crash on this?)

Step 5 — Brute Force: Build a Python list of all values, walk it in reverse, build a new linked list. O(N) time, O(N) space. State this aloud, then propose the in-place version.

Step 6 — Brute Force Complexity: Time O(N), space O(N). Correct but rejects the “in-place” implicit requirement.

Step 7 — Pattern Recognition: “Mutate linked list pointers without losing nodes” → three-pointer dance (prev, curr, next_node). This is the kernel pattern; every harder linked-list problem reuses it.

Step 8 — Optimize: Three pointers. Initialize prev = None, curr = head. Loop: save next_node = curr.next BEFORE overwriting; rewrite curr.next = prev; advance prev = curr and curr = next_node. Stop when curr is None. Return prev.

Step 9 — Prove correctness: Loop invariant: after iteration k, the first k nodes of the original list have been reversed and form a sublist rooted at prev. The remaining N − k nodes form the original tail rooted at curr. When curr becomes None, all N nodes have been processed and prev is the new head.

5. Progressive Hints

If stuck for 5 minutes, open hints.md. One hint, 5-min timer, retry.

6. Deeper Insight — Why It Works

The fundamental constraint: a singly linked list only lets you traverse forward. To reverse, you need to remember the forward direction before destroying it. The next_node = curr.next save is not optional — it’s the entire trick. Without it, you overwrite curr.next to point backward, and then curr = curr.next walks you backward instead of forward, into infinite loop or off the tail.

Why exactly three pointers: you need prev (where to point backward to), curr (which node am I rewriting), and next_node (where to go after rewriting). Two pointers leaves you with the “lost the rest of the list” bug. Four pointers is overengineering.

Recursion’s elegance vs. cost: the recursive version is a one-liner expression: “reverse the rest, then make my old next point to me, then set my next to None.” It’s a clean expression of the invariant: reverse(head) returns the new head of the reversed sublist starting at head. The cost is O(N) stack frames — and the system stack is not a debugger-friendly place to be at N=10^5.

Why O(1) space matters in interviews: the iterative version proves you understand that linked lists are already using O(N) memory; allocating O(N) more is a doubling. The interviewer’s brain registers this as “this person thinks about memory.”

7. Anti-Pattern Analysis

Wrong-but-tempting #1 — Forget to save next_node first:

prev, curr = None, head
while curr:
    curr.next = prev      # we just lost access to the rest of the list
    prev = curr
    curr = curr.next      # this is now prev, infinite loop or crash

The single most common bug. Write the lines in the order: SAVE → REWIRE → ADVANCE-PREV → ADVANCE-CURR. Memorize this sequence.

Wrong-but-tempting #2 — Build a stack of values, then rebuild the list:

vals = []
while head:
    vals.append(head.val)
    head = head.next
# rebuild
dummy = ListNode()
curr = dummy
for v in reversed(vals):
    curr.next = ListNode(v)
    curr = curr.next
return dummy.next

Works, but: (a) O(N) extra space, (b) allocates N new nodes, doubling memory traffic, (c) telegraphs to the interviewer “I don’t know how to mutate pointers.” For a phone screen, you fail the “demonstrate pointer competence” signal.

Wrong-but-tempting #3 — Recursive without base case for empty:

def reverse(head):
    if head.next is None:    # crashes on head = None
        return head
    new_head = reverse(head.next)
    head.next.next = head
    head.next = None
    return new_head

Must guard if head is None or head.next is None. Many candidates write only the latter and crash on empty input.

Wrong-but-tempting #4 — Recursive but forget head.next = None: After head.next.next = head, the old tail still has head.next pointing forward, creating a cycle of length 2 at the tail. The result list has a cycle and every subsequent operation (length, traversal) hangs. This is a classic silent bug — the function returns, but the structure is corrupt.

8. Skills & Takeaways

Generalizable pattern: “Three-pointer in-place pointer rewrite.” Whenever you mutate a pointer that you also need to follow, save the destination FIRST. This pattern reappears in:

• LC 92 — Reverse Linked List II (reverse between indices)
• LC 25 — Reverse Nodes in k-Group (Hard; reuse this kernel inside a loop)
• LC 234 — Palindrome Linked List (reverse second half, compare)
• LC 143 — Reorder List (split, reverse second half, weave)
• LC 24 — Swap Nodes in Pairs (degenerate k=2 case)
• LC 86 — Partition List (rewires by partition; same caution about lost references)

When NOT to use this: Doubly linked list (you have prev pointers already, swap them in one step). Immutable / persistent list (build new structure; O(N) space is required).

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

• I wrote the iterative version in <5 min with zero pointer-loss bugs on the second attempt
• I wrote the recursive version and handled both empty and single-node bases
• I can recite the line order (SAVE → REWIRE → ADVANCE-PREV → ADVANCE-CURR) without looking
• I can explain why the recursive version sets head.next = None at the end (cycle prevention)
• My stress_test() in solution.py passes 1000 iterations on both versions
• I solved LC 92 (Reverse Linked List II) and recognized this kernel inside it
• I solved LC 234 (Palindrome Linked List) and saw why “reverse the second half” is the right move

If any unchecked: redo before moving to p07.

10. Company Context

Microsoft (loves this problem — phone-screen mainstay)

• The framing: “Reverse a singly linked list. Both iterative and recursive, please.”
• Misleading example: They show you 1 → 2 → 3 and you smash out the iterative version in 90 seconds. They then say: “Now do it recursively.” If you can’t, you lose senior signal.
• Adversarial extension: “Now reverse only the first K nodes” (LC 25 lead-in). Then “now in groups of K with the remainder left in original order.”
• What they want to hear: Verbal walkthrough of the three pointers BEFORE coding. Microsoft phone screens use this as a calibration tool — if you can’t articulate the dance, the loop position never opens.

Amazon (Leadership Principles + correctness)

• The framing: Often inside a story problem: “Given a list of order processing steps in reverse, return them in forward order.”
• Misleading example: [A, B, C] where you might be tempted to use a Python reversed() builtin. Amazon expects you to demonstrate the algorithm, not a one-liner.
• Adversarial extension: “What if the list is too large to fit in memory and we’re streaming it from disk?” → split into chunks, reverse each, then reverse the chunk order (external-sort-style thinking).
• What they want to hear: “Let me handle empty input first.” Amazon weights Customer Obsession heavily — and customers send empty inputs.

Meta (rapid-fire follow-ups)

• The framing: Reverse → palindrome check → reorder → reverse-in-K-groups, all in 25 minutes.
• Misleading example: Often starts with “given the head of a list, return it in reverse order” — ambiguous between “return values reversed” (O(N) space, trivial) and “reverse the structure in place.” Ask.
• Adversarial extension: “Reverse just the alternating nodes.” Now you maintain two interleaved sublists.
• What they want to hear: “Let me trace through a length-2 example to verify my pointer updates” — explicit dry-run before submission. Meta interviewers love the dry-run signal.

Google (recursive elegance matters here)

• The framing: Iterative is acceptable, but the follow-up is always “now do it recursively, and explain the stack-depth tradeoff.”
• Misleading example: They might give you a generic Node type with children: List[Node] (LC 116, 117 territory) — listen carefully whether it’s singly linked or n-ary.
• What they want to hear: Big-O analysis of stack depth. Phrase: “Recursive uses O(N) stack space; for N > 10^4 in production we’d switch to iterative or trampoline.”

Apple / Bloomberg (clarity above all)

• The framing: Often combined with “now print the list reversed without modifying it” — to test whether you can use a stack, OR walk and recurse, vs. mutate.
• What they want to hear: Clear distinction between “reverse the structure” and “iterate in reverse order.” Many candidates conflate these.

11. Interviewer’s Lens

The scorecard line that gets you the offer: “Demonstrated mastery of the three-pointer rewrite kernel; would pass it down to junior engineers.”

The scorecard line that loses you: “Lost a pointer mid-loop; required interviewer to debug; suggests inattention to detail.”

12. Level Delta

Honest self-assessment: Did you lose a pointer? If yes, you’re Mid. Did you handle empty without prompting? If yes, Senior floor. Did you mention the recursive cycle bug unprompted? Staff signal.

13. Follow-up Questions & Full Answers

Follow-up 1: “Now reverse the list recursively. What’s the space cost?”

Signal sought: Comfort with recursion + complexity literacy.

Full answer: “Base case: if head is None or head.next is None, return head. Recursive: new_head = reverse(head.next); this returns the new head of the reversed sublist starting from the second node. Then head.next.next = head makes the old second node point back to head, and head.next = None cuts the forward link to prevent a 2-cycle at the tail. Return new_head. Time O(N), space O(N) for the call stack. In CPython that stack-overflows around N=1000 by default; we’d raise sys.setrecursionlimit(10_000) or rewrite iteratively in production.”

Follow-up 2: “What if it’s a doubly linked list?”

Signal sought: Adaptation, not just memorization.

Full answer: “For each node, swap its prev and next pointers. After processing all nodes, the original tail is the new head — return it. Single pass, O(1) extra space, no save-then-rewire needed because we have prev access already. The code is dramatically simpler — which is the point: data structure shape determines algorithm shape.”

Follow-up 3: “What if I want to reverse only the middle K elements?” (LC 92)

Signal sought: Can you reuse the kernel inside a more complex algorithm?

Full answer: “Two phases. (1) Walk to the (left-1)th node, save it as before. (2) From the leftth node, reverse exactly right - left + 1 nodes using the same three-pointer dance. (3) Stitch: before.next.next = curr (the first reversed node’s next now points to what’s after the reversed segment); before.next = prev (the new head of the reversed segment). Use a dummy node before head to handle left = 1 uniformly. O(N) time, O(1) space.”

Follow-up 4 (Hard): “Reverse the list in groups of K. If the last group has fewer than K nodes, leave it in original order.” (LC 25)

Signal sought: Composition of the kernel under bookkeeping pressure.

Full answer: “Outer loop: at each group start, walk K nodes ahead to check there are at least K; if not, break and leave the rest alone. Inner loop: reverse exactly K nodes using the kernel. Stitch each reversed group to the previous group’s tail using a group_prev pointer. The whole algorithm is O(N) — each node is touched at most twice (once for the K-check, once for reversal). Edge cases: K=1 (no-op), K=N (full reverse), N % K != 0 (last partial group untouched).”

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

Signal sought: Testing as engineering discipline.

Full answer: “Four layers. (1) Unit: empty, single, two-node, length-N (small and large). (2) Round-trip property: reverse twice equals identity — strongest invariant test for any reversal. (3) Cycle detection on output: walk the result with Floyd’s; should terminate at None. This catches the head.next = None bug in the recursive version. (4) Memory profile under large N: confirm no node allocation in the iterative version. My solution.py includes the round-trip property test.”

14. Full Solution Walkthrough

See solution.py.

The file has five sections:

1. ListNode — minimal node class with __repr__ for debugging.
2. reverse_iterative(head) — the three-pointer dance with INVARIANT comment. This is the production-grade answer.
3. reverse_recursive(head) — for didactic comparison; bumps sys.setrecursionlimit for stress test.
4. stress_test() — generates 1000 random lists, runs both implementations, asserts round-trip property (reverse(reverse(x)) == x) and that values match expected reversal.
5. edge_cases() — empty, single, two-node, all-same-value, large.

Decisions justified in the file:

• Why we return prev not curr: at loop exit, curr is None and prev is the last node visited, which is the new head.
• Why iterative is preferred: O(1) space, no stack-overflow risk.
• Why next_node is a local variable per iteration, not a class field: scope discipline; only the inner loop needs it.

15. Beyond the Problem — Production Reality

At scale:

• In a network stack (Linux sk_buff chains, packet queues), reversing a packet list is real — e.g., for retransmission ordering. The iterative kernel is exactly what’s used; the kernel doesn’t tolerate stack-blowing recursion.
• In garbage collectors using Cheney’s algorithm, you walk and rewire pointers in-place as you copy — same “save the destination before overwriting” discipline.

Real systems this is the kernel of:

• Undo stacks: many text editors store edits as a linked list; “redo all undones” reverses the list.
• Compiler IR transformations: SSA phi-node reordering rewires successor lists in-place.
• Database transaction logs: replay order sometimes requires walking the WAL in reverse; if it’s a forward-only list on disk, you read it all, reverse the records list, and replay.

Principal-engineer code review comment: “The recursive version is elegant but I’d reject it in our codebase. Our linked lists can hit 10^5 elements in production payloads — we’ve seen stack overflows in similar code. The iterative version is what ships. Also: please add a debug assertion that the returned list has the same length as the input — we had a production incident where a reversal silently dropped a node due to a refactor of the loop guard.”

p06 Reverse Linked List — Progressive Hints

Rule: Read ONE hint. Set a 5-minute timer. Try again. Only read the next hint if the timer expires.

Hint 1 — Pattern family

You’re going to rewrite next pointers in place. Before you overwrite a pointer, ask: “do I still need it?” If yes, save it somewhere first.

Hint 2 — Data structure / state

You need to track THREE things at every step: where you came from (so the current node can point there), where you are (the node being rewired), and where you were about to go (so you don’t lose the rest of the list).

Hint 3 — The key insight

Walk left to right. At each node, the previously-seen node becomes its new next. But before you set curr.next = prev, you must remember the old curr.next because that’s the only way to advance.

Hint 4 — Pseudocode skeleton

prev = None
curr = head
while curr is not None:
    next_node = curr.next       # SAVE
    curr.next = prev            # REWIRE
    prev = curr                 # ADVANCE prev
    curr = next_node            # ADVANCE curr
return prev

Memorize this order: SAVE → REWIRE → ADVANCE-PREV → ADVANCE-CURR. Swapping any two breaks it.

Hint 5 — Full algorithm + recursive variant

Iterative: as in Hint 4. The loop invariant: at the top of each iteration, prev is the head of the already-reversed prefix, curr points to the next unprocessed node of the original list. When curr is None, all nodes have been processed and prev is the new head.

Recursive: the elegant one-liner expression of the same invariant.

def reverse(head):
    if head is None or head.next is None:
        return head
    new_head = reverse(head.next)   # reverse the rest first
    head.next.next = head           # old second node now points back to head
    head.next = None                # CRITICAL — cut forward link, prevent 2-cycle
    return new_head

Two base cases: empty (head is None) and single node (head.next is None). Forget either and you crash or recurse forever. The line head.next = None is non-obvious; without it you create a cycle and the next traversal hangs.

Time O(N) both versions. Iterative space O(1), recursive space O(N) — and Python’s default recursion limit (1000) makes recursive risky for long lists; use sys.setrecursionlimit(10_000) if you must.

p07 — Merge Two Sorted Lists

Source: LeetCode 21 · Easy · Topics: Linked List, Recursion Companies (2024–2025 frequency): Amazon (very high), Microsoft (very high), Apple (high), Google (high), Meta (medium), Bloomberg (high) Loop position: phone screen warmup; the kernel of merge-sort (LC 148), K-way merge (LC 23), and external sort

1. Quick Context

The “merge” of merge sort, on linked lists. The interviewer is testing whether you reach for the dummy/sentinel node pattern without prompting, because dummy nodes are how senior engineers eliminate special cases. The candidate who writes if result is None: result = ...; tail = ... four times has not internalized the pattern. The one who writes dummy = ListNode(); tail = dummy and never special-cases anything has.

What it looks like it tests: merging two sorted lists. What it actually tests: do you use the dummy-node pattern reflexively? Can you stitch the leftover tail in O(1) instead of walking it node-by-node?

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/merge-two-sorted-lists/

STOP. Set a 12-minute timer. Code it cold. Do not read past this section until solved or expired.

If repeat: target 5 min including narration. Iterative + dummy node. If you wrote any if head is None branches inside the loop, you’ve missed the lesson — redo with a sentinel.

3. Prerequisite Concepts

• Linked list node basics (phase-01 §4)
• Sentinel / dummy node pattern: allocate one throwaway node at the start so the “first node” of the output isn’t a special case. This pattern reappears in every list/tree problem where insertion at head differs from insertion anywhere else.
• The “leftover tail” optimization: when one list is exhausted, the other’s remaining suffix is already sorted — just point at it; don’t iterate.

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

Step 1 — Restate: “Given two sorted (non-decreasing) singly linked lists, return a single sorted list formed by splicing their nodes.”

Step 2 — Clarify:

• “Splice (reuse input nodes) or allocate new nodes?” (Splice is expected — O(1) extra space. Ask anyway.)
• “Either list empty? Both empty?” (Yes, both possible.)
• “Stable for equal values? Does order within a value matter?” (Usually no; ask if data has meaning beyond val.)
• “Sorted ascending or descending?” (Ascending per LC.)

Step 3 — Constraints: N1 + N2 up to 100 per LC, but real production sizes are unbounded. O(N1+N2) is the bar.

Step 4 — Examples:

• [1,2,4] + [1,3,4] → [1,1,2,3,4,4]
• [] + [] → []
• [] + [0] → [0]
• [5] + [1] → [1,5] (a < b throughout — leftover tail kicks in immediately)
• [1,1,1] + [1,1,1] → [1,1,1,1,1,1] (all equal — tie-breaking)

Step 5 — Brute Force: Walk both lists, push all values into a Python list, sort, rebuild a linked list. O((N1+N2) log (N1+N2)) time, O(N1+N2) space. Throws away the sortedness — explicitly inferior. State this aloud to anchor that you know it’s wrong.

Step 6 — Brute Force Complexity: O(N log N) time, O(N) space. Misses the linear opportunity.

Step 7 — Pattern Recognition: “Two sorted sequences → one merged sorted sequence” → two-pointer merge (the inner loop of merge sort). On linked lists this also requires dummy node for clean output construction.

Step 8 — Optimize: Dummy node + tail pointer. While both l1 and l2 are non-None, append the smaller (l1 if l1.val <= l2.val else l2) to tail.next, advance that list and tail. After the loop, attach whichever is non-None (the “leftover tail” — point, don’t walk). Return dummy.next.

Step 9 — Prove correctness: Loop invariant: after each iteration, dummy.next ... tail is a sorted list containing exactly the consumed nodes from l1 and l2, and both l1 and l2 still point to sorted remainders whose first elements are ≥ tail.val. When one becomes None, the other’s remainder is sorted and ≥ tail — attaching it preserves sortedness.

5. Progressive Hints

If stuck for 5 minutes, open hints.md. One hint, 5-min timer, retry.

6. Deeper Insight — Why It Works

Why dummy node: without it, the first append is a special case (if result is None: result = node; tail = node). With it, the first append is identical to every other (tail.next = node; tail = tail.next). One pattern, zero special cases. This is the entire reason senior code looks cleaner than junior code on linked list problems — the senior reaches for sentinels without thinking.

Why <= not < for stability: if you write <, ties from l1 get placed AFTER ties from l2, breaking stability with respect to input order. For pure numerical merge it doesn’t matter, but for sorted lists of objects (rows, records) with equal keys, stability is a real correctness property. The Pythonic principle: write the version that generalizes.

Why “leftover tail” matters: after one list exhausts, the other is already a sorted linked list. Walking it node-by-node to append each is O(remainder) wasted work AND extra pointer writes. Just doing tail.next = whichever_is_not_none is O(1) and is the move that makes the algorithm exactly O(N1+N2), not “amortized” or “approximately”.

Why this is merge-sort’s inner loop: merge sort on a linked list (LC 148) recursively splits and then calls THIS exact function on each pair. Merging K sorted lists (LC 23) uses this repeatedly inside a min-heap. The kernel is small and gets reused; learn it cleanly.

7. Anti-Pattern Analysis

Wrong-but-tempting #1 — No dummy node, special-case the first append:

result = None; tail = None
while l1 and l2:
    if l1.val <= l2.val:
        if result is None: result = l1; tail = l1
        else: tail.next = l1; tail = l1
        l1 = l1.next
    else:
        if result is None: result = l2; tail = l2
        else: tail.next = l2; tail = l2
        l2 = l2.next
# ... and you need similar special-casing for the leftover

Works but it’s a code smell. The dummy node version is half the lines and zero branches in the loop. Senior interviewers see this and write “didn’t use idiomatic sentinel” on the scorecard.

Wrong-but-tempting #2 — Allocate new nodes:

while l1 and l2:
    if l1.val <= l2.val:
        tail.next = ListNode(l1.val); l1 = l1.next
    else:
        tail.next = ListNode(l2.val); l2 = l2.next
    tail = tail.next

Allocates N new nodes, doubling memory. Splicing existing nodes is O(1) extra space. For interview, this is a “didn’t optimize space” mark. For production with 10M nodes, it’s a memory pressure incident.

Wrong-but-tempting #3 — Walk the leftover tail node by node:

while l1: tail.next = l1; tail = tail.next; l1 = l1.next
while l2: tail.next = l2; tail = tail.next; l2 = l2.next

Works, but the second loop is unnecessary — exactly one of l1, l2 is non-None after the merge loop, and you can attach the whole remainder with tail.next = l1 or l2. The over-engineered version wastes pointer writes and obscures that the leftover is already sorted.

Wrong-but-tempting #4 — Recursive without the splice:

def merge(a, b):
    if not a: return b
    if not b: return a
    if a.val <= b.val:
        a.next = merge(a.next, b); return a
    b.next = merge(a, b.next); return b

This is actually GOOD — clean, elegant, and demonstrates recursion. But: O(N1+N2) stack depth, which stack-overflows in Python around N=1000. Iterative is the production choice; recursive is the “show off elegance, then mention the stack cost” choice. Both should be in your repertoire.

8. Skills & Takeaways

Generalizable patterns:

• Dummy/sentinel node: use whenever the “first” element is structurally different from the rest. Reappears in every list mutation problem.
• Two-pointer merge: the inner loop of merge sort, of streaming joins in databases, of timeline-merge in log aggregation systems.
• Leftover tail attachment: any merge of two already-sorted sequences leaves one as a prepared suffix; attach in O(1).

Analogous problems:

• LC 23 — Merge K Sorted Lists (Hard; min-heap of heads, call this kernel K-1 times)
• LC 148 — Sort List (merge sort on a linked list; this is the merge step)
• LC 88 — Merge Sorted Array (the array version, with the in-place-from-end trick — your p04)
• LC 1019 — Next Greater Node In Linked List (different problem, but reuses the dummy-node-for-result pattern)
• LC 86 — Partition List (two dummy nodes, splice into two lists, then merge)

When NOT to use this: unsorted inputs (sort first, OR use a different algorithm). Streaming inputs of unbounded size where you can’t hold both heads.

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

• I solved the iterative version in <5 min on the second attempt
• I used a dummy node and have ZERO if tail is None checks inside the loop
• I attached the leftover tail in O(1) (not by walking)
• I can explain why <= matters for stability
• I can write the recursive version and state its O(N) stack cost
• My stress_test() passes 1000 iterations against a sorted-Python-list oracle
• I solved LC 23 (Merge K Sorted Lists) and recognized this kernel called K-1 times

If any unchecked: redo before moving to p08.

10. Company Context

Amazon (warehouse / fulfillment narratives common)

• The framing: “You have two sorted shipment-arrival queues from different warehouses; merge them into one timeline.”
• Misleading example: Empty input from one queue. Many candidates’ code crashes on None.val.
• Adversarial extension: “Now there are M warehouses.” (LC 23 — K-way merge.) Followed by: “And each can be 10TB on disk.” (External merge sort.)
• What they want to hear: “Let me handle the empty-list cases first.” Amazon weighs defensive coding heavily.

Microsoft (loves linked-list problems — phone screen battery)

• The framing: Often paired with reverse-linked-list as a back-to-back battery.
• Misleading example: They give you [1,1,1] and [1,1,1] — testing whether you correctly use <= and don’t introduce bugs around ties.
• Adversarial extension: “Sort a linked list using merge sort.” (LC 148.) Now you split the list with slow/fast pointers and call this function on the halves.
• What they want to hear: Verbalize the dummy-node decision out loud. “I’ll use a sentinel to avoid special-casing the first node.”

Apple (clean code expected)

• The framing: Often the straight problem.
• Misleading example: None — Apple tends to be straightforward but watches for code aesthetics.
• Adversarial extension: “Merge them in descending order instead.” (Flip the comparator, but watch for the leftover-tail still being attached without re-sorting — it’s already descending if input was descending.)
• What they want to hear: Idiomatic, dummy-node, leftover-attached-in-O(1) code. Apple interviewers will literally say “looks like production code” when they see it.

Google (algorithm composition)

• The framing: Straight problem, then “What’s the K-way version?”, then “What if K=10^6?”
• What they want to hear: Progression from this kernel → min-heap of K heads → external merge with limited memory. The Google bar is articulating the algorithmic family tree.

Meta / Bloomberg (data-processing scenarios)

• The framing: “Merge two sorted streams of events / orders / quotes by timestamp.”
• What they want to hear: Recognition that this is the inner loop of every streaming-join algorithm. Bloomberg in particular loves merge-by-timestamp scenarios.

11. Interviewer’s Lens

The scorecard line that gets you the offer: “Used dummy node naturally, attached leftover tail in O(1) — code reads like internal library code.”

The scorecard line that loses you: “Multiple branches in main loop; allocated new nodes unnecessarily; walked leftover.”

12. Level Delta

13. Follow-up Questions & Full Answers

Follow-up 1: “Now merge K sorted lists.” (LC 23)

Signal sought: Composition of this kernel.

Full answer: “Two approaches. (a) Min-heap of K heads: push the head of each list into a min-heap keyed by val. Pop the smallest, append to result, push its next if any. O(N log K) time, O(K) extra space. (b) Pairwise merge: merge in K/2 pairs, then K/4, … O(N log K) same complexity but better cache behavior because each merge is sequential. For very large K, (a); for moderate K with cache-sensitive workloads, (b). The kernel I just wrote is what’s called inside both.”

Follow-up 2: “What if the lists are descending?”

Signal sought: Adaptation, comparator awareness.

Full answer: “Flip the comparison: l1.val >= l2.val picks the larger first. The leftover-tail attach still works — it’s still a sorted suffix, just descending. Single character change. If I expected either order at runtime, I’d parameterize with a comparator function: merge(l1, l2, cmp=lambda a,b: a <= b).”

Follow-up 3: “Stability — explain when <= vs < matters.”

Signal sought: Do you understand the property name?

Full answer: “Stability means equal elements preserve their original relative order. For pure numbers it’s invisible. For objects with payloads (e.g., trading orders with same price but different timestamps), it’s a correctness property — a stable merge keeps earlier-timestamp orders first. Using <= (pick from l1 on ties) achieves stability when l1 is the ‘first’ list by convention. Using < (pick from l2 on ties) reverses tie order. Always state which list is ‘first’ when you claim stability.”

Follow-up 4 (Hard): “Sort a linked list.” (LC 148)

Signal sought: Algorithm composition.

Full answer: “Merge sort. (1) Find the middle with slow/fast pointers; split into two halves (set middle.next = None to terminate the first half). (2) Recursively sort each half. (3) Merge with this kernel. O(N log N) time. Space: O(log N) for recursion stack (vs. O(1) for the merge step itself). Why not quicksort? Linked list random access is O(N), so quicksort’s partition step is awful. Merge sort is the natural fit because its access pattern is sequential.”

Follow-up 5 (Senior signal): “How would you handle this for billion-node lists across multiple machines?”

Signal sought: Distributed thinking.

Full answer: “External merge. Each machine holds a sorted shard; we want one globally sorted output. Use a tournament tree (loser tree) with K = number of shards, each shard streams its head value. The tree picks the global minimum in O(log K) per element. Each machine reads sequentially from disk; the coordinator emits the merged stream. This is exactly how Spark’s sort-merge join works, and how HBase compactions merge sorted SSTables. The two-list kernel I just wrote generalizes via tournament-tree to N-way.”

14. Full Solution Walkthrough

See solution.py.

The file has five sections:

1. ListNode — minimal class with __repr__.
2. merge_two_lists(l1, l2) — iterative, dummy-node, splice-in-place. The production version.
3. merge_two_lists_recursive(l1, l2) — for didactic comparison; bumps recursion limit.
4. stress_test() — generates 1000 random sorted-list pairs, runs both implementations, compares to a sorted Python list oracle.
5. edge_cases() — empty+empty, empty+nonempty, single+single, all-equal-values, large.

Decisions justified:

• Why <= not <: stability (per Section 13.3).
• Why tail.next = l1 or l2 after the loop: Python truthy idiom, both Pythonic and O(1).
• Why we splice nodes rather than copy: O(1) extra space, no allocation pressure.

15. Beyond the Problem — Production Reality

At scale:

• Database query execution: SORT MERGE JOIN reads two sorted child operators and merges by join key. This is the kernel — Postgres, Oracle, MySQL, BigQuery all have this code path.
• Log aggregation: Kafka log compaction, Loki/Tempo segment merging, ClickHouse part-merging — all are timestamp-keyed merges of sorted segments.
• LSM trees (RocksDB, LevelDB, Cassandra): compaction merges multiple sorted SSTables into one. Same kernel, lifted to disk-resident files.

Real systems this is the kernel of:

• Polyphase merge sort in external sort utilities (sort command on Unix when input doesn’t fit in RAM).
• Spark’s sort-merge join: each executor holds a sorted partition; the merge is precisely this kernel.
• Time-series database compaction: InfluxDB, Prometheus, TimescaleDB all merge time-ordered chunks.

Principal-engineer code review comment: “I’d add a debug assertion that asserts both inputs are sorted on the way in. We’ve had subtle bugs where a caller passed an unsorted list (a different list type assumed by mistake) and this function silently produced garbage. A assert is_sorted(l1) and is_sorted(l2) under if __debug__ is cheap insurance. Also: please version the comparator — for our timestamp lists, we sometimes pass nanosecond ints and sometimes datetime objects; the lambda makes the contract explicit at the call site.”

p07 Merge Two Sorted Lists — Progressive Hints

Rule: Read ONE hint. Set a 5-minute timer. Try again. Only read the next hint if the timer expires.

Hint 1 — Pattern family

The first node of your output isn’t special — except your code probably treats it that way. There’s a single allocation trick that makes “first append” identical to every other append. Reach for it.

Hint 2 — Data structure / state

You walk both lists simultaneously, always advancing the one whose current value is smaller. You need a way to append to your output without re-finding its end every time. So: keep a pointer to the output’s tail.

Hint 3 — The key insight

Use a dummy (sentinel) node before the real output head. Then tail = dummy initially. Every append is tail.next = chosen; tail = tail.next. No special case for the first node. Return dummy.next (skip the dummy).

When one list is exhausted, the other’s remainder is already sorted. Just point at it. Don’t iterate.

Hint 4 — Pseudocode skeleton

dummy = new ListNode()
tail = dummy
while l1 and l2:
    if l1.val <= l2.val:        # <= for stability
        tail.next = l1
        l1 = l1.next
    else:
        tail.next = l2
        l2 = l2.next
    tail = tail.next
tail.next = l1 if l1 else l2    # leftover tail — O(1) attach
return dummy.next

Two things to check yourself: (a) you wrote <=, not <; (b) the leftover attach is ONE line, not a second while loop.

Hint 5 — Full algorithm

The iterative version is as in Hint 4. Loop invariant: at the top of each iteration, dummy.next ... tail is a sorted list of all consumed nodes, and the remaining l1 and l2 are sorted suffixes whose first elements are ≥ tail.val. When one becomes None, the other’s entire remainder is sorted and ≥ tail, so attaching it preserves the sorted property.

Why dummy node: without it, you’d write if result is None: result = chosen; tail = chosen for the first append, creating a branch in your hot loop. With it, every iteration is identical. This is the “sentinel removes the special case” pattern — it reappears in every list mutation problem.

Recursive variant (Google likes this):

def merge(l1, l2):
    if l1 is None: return l2
    if l2 is None: return l1
    if l1.val <= l2.val:
        l1.next = merge(l1.next, l2); return l1
    l2.next = merge(l1, l2.next); return l2

Elegant but O(N1+N2) stack — risky in Python past N=1000.

Time O(N1+N2). Space O(1) iterative, O(N1+N2) recursive.

p08 — Linked List Cycle

Source: LeetCode 141 · Easy · Topics: Linked List, Two Pointers, Hash Table Companies (2024–2025 frequency): Amazon (high), Microsoft (high), Google (very high), Meta (high), Bloomberg (medium), Apple (medium) Loop position: phone screen; the lead-in to LC 142 (find cycle start), LC 287 (Find Duplicate Number), LC 202 (Happy Number)

1. Quick Context

The interviewer’s real question is: “Do you know Floyd’s tortoise-and-hare, and can you prove it terminates?” The HashSet solution gets you Mid-level credit. The two-pointer solution with a verbal correctness sketch gets you Senior. Articulating the modular-arithmetic proof gets you Staff. This is one of the rare problems where the justification matters as much as the code.

What it looks like it tests: detect a cycle in a linked list. What it actually tests: can you reason about an algorithm whose correctness is non-obvious? Can you explain why a slow and fast pointer must meet inside any cycle, instead of just asserting it?

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/linked-list-cycle/

STOP. Set a 12-minute timer. Code BOTH the HashSet version and Floyd’s. Do not read past this section until solved or expired.

If repeat: target 4 min for Floyd’s. If you reach for HashSet first reflexively, that’s a Mid signal — practice Floyd’s until it’s your reflex.

3. Prerequisite Concepts

• Linked list traversal, the None terminator (phase-01 §4)
• Two-pointer / fast-slow pattern (phase-02 §1 Two Pointers)
• HashSet O(1) average membership; identity (id()) vs value as the set key — for nodes, identity is correct because two distinct nodes can have equal values
• Modular arithmetic intuition: if two runners on a circular track move at different speeds, they will eventually be at the same point (gap closes by 1 each step in tortoise-and-hare)

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

Step 1 — Restate: “Given the head of a singly linked list, return True if any node’s next reaches a previously-visited node (a cycle), else False.”

Step 2 — Clarify:

• “Empty or single-node input?” (Both possible; cycle requires at least 2 nodes including the self-loop edge case.)
• “Can the cycle start at the head itself (entire list is a cycle)?” (Yes.)
• “Is the cycle always reachable from head?” (Yes by definition — we only follow next from head.)
• “Allowed to modify the list?” (Discuss; the in-place “mark with sentinel” approach exists but mutates input. Floyd’s doesn’t need it.)

Step 3 — Constraints: N up to 10^4 in LC. Both HashSet O(N) space and Floyd’s O(1) space fit; production prefers O(1).

Step 4 — Examples:

• [3, 2, 0, -4] with tail → node at index 1 (3→2→0→-4→2→…) → True
• [1, 2] with tail → head (1→2→1→…) → True
• [1] no cycle → False
• [1] self-loop (1→1) → True (single-node cycle — does Floyd’s handle it? Yes if you advance correctly.)
• [] → False

Step 5 — Brute Force: HashSet of visited node IDs. Walk; if current node already in set → cycle; else add and advance. O(N) time, O(N) space. Use id(node), not node.val, to avoid collisions on equal values.

Step 6 — Brute Force Complexity: Time O(N), space O(N). Correct, but uses heap memory for what can be done in O(1).

Step 7 — Pattern Recognition: “Cycle detection in a sequence with O(1) memory” → Floyd’s tortoise and hare (slow/fast pointer). Generalizes to: cycle in iterated function f (LC 202, LC 287); duplicate detection in number sequences; Pollard’s rho factorization.

Step 8 — Optimize: Floyd’s. slow = head, fast = head. Loop: advance slow by 1, fast by 2. If fast or fast.next becomes None, no cycle → False. If slow == fast, cycle → True.

Step 9 — Prove correctness: If no cycle, fast reaches None in at most N/2 steps. If cycle exists, both pointers enter the cycle eventually. Once both are in the cycle of length C, the gap between them (measured as (fast - slow) mod C) increases by exactly 1 each iteration (fast gains 2, slow gains 1, net +1). Since the gap is bounded in [0, C-1], it must take the value 0 within C iterations — that’s when they meet.

5. Progressive Hints

If stuck for 5 minutes, open hints.md. One hint, 5-min timer, retry.

6. Deeper Insight — Why It Works

The pigeonhole / modular argument: consider only the cycle phase (after both pointers are inside the cycle of length C). Each step, slow advances by 1 mod C, fast by 2 mod C. Their relative position is (fast_pos - slow_pos) mod C, which changes by +1 mod C each step. Over C iterations, it takes every value in {0, 1, …, C-1} — so it hits 0 (collision) within C steps. There is no input that escapes detection.

Why 1 and 2 specifically: any pair of speeds (a, b) with gcd(b - a, C) = 1 would also work, but (1, 2) is the simplest: gap increment is always 1, gcd is always 1 (any C). Using (1, 3) would have a gap increment of 2; on even-length cycles, the gap might be permanently odd, never zero. The choice of speeds is not arbitrary.

Why fast and fast.next: fast moves 2, so we check BOTH that fast exists and that fast.next exists before doing fast = fast.next.next. Forgetting fast.next is the classic NoneType crash.

Why HashSet uses id(): the question is structural (same node visited twice), not value-based. Two distinct nodes can have equal val. Using node as the key works in Python (default __hash__ is identity-based), but id(node) is explicit and unambiguous.

Why this generalizes to numerical cycles: treat x → f(x) as a “next pointer” on integers. Then LC 202 (Happy Number — cycle in repeated digit-square-sum) and LC 287 (Find Duplicate Number — cycle in nums[nums[i]]) become structurally identical. The kernel is “Floyd’s on any iterated function.”

7. Anti-Pattern Analysis

Wrong-but-tempting #1 — HashSet on node.val:

seen = set()
while head:
    if head.val in seen: return True
    seen.add(head.val)
    head = head.next

Wrong. Two distinct nodes with the same value would falsely trigger “cycle detected”. For [1, 1, 1, 1] with no cycle (just repeating values), this returns True. Use id(head) or head directly as the set key.

Wrong-but-tempting #2 — Counter / step limit:

count = 0
while head:
    if count > MAX: return True
    head = head.next; count += 1

Heuristic: “if I walk more than 10^4 nodes, must be a cycle.” Fails on inputs that are legitimately longer than your bound and falsely flags. Doesn’t prove anything — interviewers reject as “didn’t think about correctness.”

Wrong-but-tempting #3 — Mutate the list with sentinel values:

while head:
    if head.val == SENTINEL: return True
    head.val = SENTINEL
    head = head.next

Destroys input. Some interviewers tolerate this if you ask permission first; many don’t. And in production, the input might be shared (immutable contract), so this corrupts state. Never the default choice.

Wrong-but-tempting #4 — fast = fast.next.next without null guard:

while slow != fast:
    slow = slow.next
    fast = fast.next.next   # crashes when fast or fast.next is None

Classic NoneType crash. Always guard while fast is not None and fast.next is not None BEFORE advancing fast by 2.

Wrong-but-tempting #5 — Start slow = head, fast = head.next: Off-by-one. The standard formulation is slow = fast = head, advance both at the top of each iteration, then compare. Starting fast ahead introduces an asymmetric first iteration and causes the meeting-point math (used in LC 142) to be wrong.

8. Skills & Takeaways

Generalizable patterns:

• Floyd’s cycle detection: on linked lists, on iterated integer functions, on any sequence where you have f(x) = next. Examples: LC 142, 202, 287, 457.
• Modular arithmetic for terminat ion proofs: when you can’t enumerate states, model the state space modulo cycle length.
• id() for identity-based hashing: when the question is “same object?” not “same value?”

Analogous problems:

• LC 142 — Linked List Cycle II (find the start of the cycle — the math gets beautiful)
• LC 202 — Happy Number (Floyd’s on digit-square-sum iteration)
• LC 287 — Find the Duplicate Number (Floyd’s on nums[nums[i]] — Hard, the constraint of O(1) extra space is what forces Floyd’s)
• LC 457 — Circular Array Loop (Floyd’s with directional constraints)
• LC 234 — Palindrome Linked List (uses slow/fast to find the middle — same kernel, different goal)
• LC 876 — Middle of Linked List (the simplest fast-slow use)

When NOT to use this: if you can read the list twice (then a counter + walk-N/2 finds the middle). If the cycle’s start matters and you don’t want the math (then HashSet to find the first repeat). If input is mutable AND interviewer permits (sentinel marking is fastest in wall-clock).

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

• I wrote Floyd’s in <5 min on the second attempt with correct null guards
• I can state aloud why the slow and fast pointers MUST meet inside any cycle (gap+1 mod C argument)
• I can explain why speeds (1, 2) and not (1, 3) — even-length cycle hazard
• I can implement the HashSet version and articulate why id() matters over val
• My stress_test() covers both no-cycle and cycle inputs and passes 1000 iterations
• I solved LC 142 (Cycle II) and can derive the meeting-point math
• I solved LC 202 (Happy Number) and saw Floyd’s apply to integer iteration

If any unchecked: redo before moving to p09.

10. Company Context

Google (loves the proof — Staff-bar problem)

• The framing: Standard problem, then “prove it terminates.”
• Misleading example: A no-cycle list that’s long enough to be uncomfortable but not infinite. Some candidates assume “long = cycle” and false-positive.
• Adversarial extension: “Now find the START of the cycle.” (LC 142.) Then “What if the cycle exists but the head is NOT inside it?” (e.g., 1→2→3→4→3, cycle starts at 3 — head is not in cycle.)
• What they want to hear: Modular arithmetic proof, not “I trust it.” Verbatim phrases like “the gap grows by 1 modulo cycle length each step, so it must reach 0 within C iterations” earn Staff signal.

Amazon (defensive coding)

• The framing: Often in a story: “Detect if a workflow has a self-referential dependency.”
• Misleading example: Single-node self-loop. Many naive Floyd’s implementations skip this because of how they initialize.
• Adversarial extension: “What if the input could already be partially corrupted (cyclic) and we need to safely traverse just the acyclic prefix?” → returns the prefix length AND cycle detection.
• What they want to hear: “Let me handle empty and single-node first.” Then proceed.

Microsoft (phone screen mainstay)

• The framing: Often back-to-back with reverse and merge.
• What they want to hear: Both HashSet and Floyd’s solutions, with explicit tradeoff statement: “HashSet is O(N) space but simpler; Floyd’s is O(1) space, which is the production preference.”

Meta (fast follow-ups)

• The framing: Linked List Cycle → Cycle II → Happy Number, in rapid sequence. They use this to test whether you generalize.
• What they want to hear: Naming the pattern: “this is Floyd’s cycle detection; it applies to any iterated function, not just linked lists. Happy Number is the same algorithm on integer→integer iteration.”

Bloomberg / Apple

• The framing: Standard. Bloomberg sometimes adds: “If detected, return the cycle length too.”
• What they want to hear: Awareness that once Floyd’s detects, you can count cycle length by walking one pointer until they re-meet.

11. Interviewer’s Lens

The scorecard line that gets you the offer: “Implemented Floyd’s correctly with correct null guards; articulated termination proof using modular arithmetic; generalized to integer iteration.”

The scorecard line that loses you: “Used HashSet on values not identity; crashed on self-loop; could not explain why the algorithm works.”

12. Level Delta

13. Follow-up Questions & Full Answers

Follow-up 1: “Find the start of the cycle.” (LC 142)

Signal sought: Can you do the math?

Full answer: “After Floyd’s detects the meet, reset one pointer to head. Advance both by 1 step. They meet at the cycle start. Proof: let L = length of non-cycle prefix, C = cycle length, k = distance from cycle start to the meet point. When slow has moved L+k steps, fast has moved 2(L+k) and is at the same node, so 2(L+k) − (L+k) = L+k is a multiple of C: L+k ≡ 0 (mod C), so L ≡ −k ≡ C−k (mod C). That means walking L more steps from the meet point lands exactly at the cycle start. Reset one pointer to head, advance both by 1, they meet there. O(N) time, O(1) space.”

Follow-up 2: “What’s the largest input where HashSet would be cheaper than Floyd’s in wall-clock?”

Signal sought: Engineering pragmatism, not just asymptotics.

Full answer: “HashSet does ~1 hash + 1 compare per node, but allocates a hash table that grows. Floyd’s does 3 pointer-derefs per slow-step (slow advance + fast.next + fast.next.next). For tiny N (under ~100) and cycle absent, HashSet is sometimes marginally faster due to fewer pointer hops, but allocates memory. For any meaningful N or when allocations matter (real-time systems, embedded), Floyd’s wins. The space difference (O(N) vs O(1)) almost always dominates the decision.”

Follow-up 3: “What if speeds were (1, 3) instead of (1, 2)?”

Signal sought: Did you actually understand the proof?

Full answer: “The gap closes by 2 each step (modulo C). If C is odd, gcd(2, C) = 1 and the gap eventually hits 0. If C is even, the gap stays at the same parity forever — if it starts odd, it never reaches 0. So (1, 3) fails on even cycle lengths. The choice of (1, 2) is what guarantees gcd(speed difference, C) = 1 for every C ≥ 2.”

Follow-up 4: “Apply Floyd’s to find a duplicate in an array of N+1 integers, each in [1, N].” (LC 287)

Signal sought: Generalization to non-list inputs.

Full answer: “Treat the array as a function: f(i) = nums[i]. Start at i=0 (or N, any value never produced as output works as a sentinel; here 0 works because nums values are in [1,N]). Define next(x) = nums[x]. Since there’s a duplicate value d, two indices map to d, so the iteration x → nums[x] must form a cycle at d. Apply Floyd’s: slow advances by slow = nums[slow], fast by fast = nums[nums[fast]]. Detect meet, then find cycle start using the LC 142 trick. The cycle start IS the duplicate. O(N) time, O(1) extra space — beats sort and HashSet.”

Follow-up 5 (Senior signal): “How would you test cycle detection without modifying production data?”

Signal sought: Testing discipline.

Full answer: “Three layers. (1) Build a builder utility that constructs a list AND injects an optional cycle at index k — separate the test scaffolding from the algorithm. (2) Property tests: (a) any acyclic list returns False, (b) any cyclic list returns True, (c) cycle length 1 (self-loop) returns True, (d) entire list is the cycle returns True. (3) Memory profile: assert Floyd’s allocates zero new nodes (vs HashSet’s O(N)). My solution.py uses a build_with_cycle(values, cycle_at) helper precisely for layered testing.”

14. Full Solution Walkthrough

See solution.py.

The file has six sections:

1. ListNode — minimal class.
2. has_cycle_hashset(head) — the brute force using id() as key.
3. has_cycle(head) — Floyd’s, with INVARIANT comment. Guards fast and fast.next before advancing.
4. build_with_cycle(values, cycle_at) — helper to construct test inputs with controlled cycle start (or -1 for no cycle).
5. stress_test() — generates 1000 random cases, half with cycles, asserts both implementations agree.
6. edge_cases() — empty, single (no cycle), single self-loop, two-node cycle, entire-list cycle, cycle at tail.

Decisions justified:

• Why id(node) not node: explicit identity contract; works in any language port.
• Why slow = fast = head not fast = head.next: symmetric initialization is what makes the LC 142 math work.

15. Beyond the Problem — Production Reality

Real-world cycle detection:

• Garbage collectors (Python’s reference-cycle collector, JVM’s old-generation tracer): cycle detection is critical for reclaiming memory. The algorithms are richer than Floyd’s (they use tri-color marking) but Floyd’s is the conceptual ancestor.
• Distributed deadlock detection: in databases (e.g., Postgres, Spanner), each transaction is a node, “waits-for” is the edge. Cycle = deadlock. Detection algorithms run periodically over the wait-for graph.
• Build systems: detecting circular dependencies in Bazel, Cargo, npm — same family of algorithm, lifted to DAGs.
• Pollard’s rho factorization: Floyd’s cycle detection on the iteration x → (x² + c) mod n factors large integers. Same algorithm, profoundly different application.

Real systems this is the kernel of:

• Linux kernel kref debugging: detecting object reference cycles.
• TensorFlow / PyTorch dataflow graphs: cycle detection before compilation.
• Service mesh dependency analysis: Istio uses cycle detection over service-call graphs to flag bad architecture.

Principal-engineer code review comment: “Floyd’s is correct but in our production we use Brent’s algorithm — it has the same O(N) bound but fewer pointer dereferences on long acyclic inputs. We saw a 30% speedup in our packet-trace analyzer. Worth knowing both. Also: please add metric emission so if cycle is detected in our workflow scheduler, we page on it — silent cycle handling has caused two outages.”

p08 Linked List Cycle — Progressive Hints

Rule: Read ONE hint. Set a 5-minute timer. Try again. Only read the next hint if the timer expires.

Hint 1 — Pattern family

You can solve this with extra memory (remember every node you’ve seen — if you revisit one, cycle). Can you do it WITHOUT extra memory? Think about two things moving through the list at different speeds.

Hint 2 — Data structure / state

Two pointers. Both start at head. One advances by 1 each iteration; the other by 2. If there’s a cycle, the faster one will eventually lap the slower one and they’ll be at the same node. If no cycle, the faster one walks off the end.

Hint 3 — The key insight

Inside any cycle of length C, the gap between fast and slow (fast minus slow, mod C) increases by exactly 1 each step. Since the gap is bounded in [0, C-1], it must take the value 0 within C steps — that’s when they meet. The algorithm is guaranteed to terminate, with proof.

For the no-cycle case: fast (moving 2 per step) reaches the end (None) in at most N/2 steps.

Hint 4 — Pseudocode skeleton

slow = head
fast = head
while fast is not None and fast.next is not None:
    slow = slow.next
    fast = fast.next.next
    if slow is fast:
        return True
return False

Two correctness checks: (a) you guard BOTH fast AND fast.next before doing fast.next.next, (b) you advance then compare (not compare before the first advance, which would falsely return True for any list of length ≥ 1).

Hint 5 — Full algorithm + why this works

Floyd’s tortoise-and-hare: start slow = fast = head. In each loop iteration: advance slow by 1, fast by 2. If fast or fast.next is None, no cycle exists. If slow and fast point to the same node, a cycle exists.

Why speeds (1, 2) specifically: the gap between them increases by 2 - 1 = 1 per step (mod cycle length C). Since gcd(1, C) = 1 for any C, the gap eventually equals 0 — they meet. If you used (1, 3), the gap would increase by 2 per step; for even C, the gap might be permanently odd and never hit 0. The choice isn’t arbitrary; it guarantees correctness for all cycle lengths.

Why fast and fast.next BEFORE advancing fast by 2: because fast.next.next would crash on NoneType otherwise. The guard goes BEFORE the advancement.

HashSet variant (correctness oracle): walk the list, store id(node) in a set; if you encounter a duplicate id, return True. Use id() (identity), not node.val, because two distinct nodes can hold the same value — [1, 1, 1, 1] with no cycle would falsely trigger on val.

Time O(N) both; space: HashSet O(N), Floyd’s O(1). Floyd’s wins in interviews and production.

p09 — Maximum Subarray (Kadane’s Algorithm)

Source: LeetCode 53 · Medium · Topics: Array, Divide & Conquer, Dynamic Programming Companies (2024–2025 frequency): Amazon (very high), Microsoft (high), Bloomberg (very high), Apple (high), Meta (medium), Google (medium) Loop position: mid-loop coding round; sometimes given as “Easy” but the optimal is genuinely subtle

1. Quick Context

This is your first encounter with a 1-D dynamic programming algorithm that collapses to two scalars. The DP table is conceptually dp[i] = max subarray sum ending exactly at i, but the answer only needs dp[i-1], so you never allocate the array. Senior candidates derive this collapse on the spot. Mid candidates write the O(N) DP array and forget to optimize. Junior candidates write the O(N²) brute force and get stuck.

The interviewer is testing whether you can: (a) identify that “contiguous subarray” rules out two-pointer (which needs monotone structure) and dynamic-programming-with-prefix-sums (which gets the global sum, not the contiguous-piece argmax), (b) derive the recurrence on the spot, (c) collapse it to O(1) space.

What it looks like it tests: find the max-sum contiguous subarray. What it actually tests: can you discover Kadane’s recurrence on your own? Can you handle the all-negative-array trap?

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/maximum-subarray/

STOP. Set a 15-minute timer (this one is genuinely harder than the surrounding Easy problems). Code it cold. Do not read past this section until solved or expired.

If you find Kadane’s immediately because you’ve seen it: target 5 min, AND derive the recurrence aloud as you write. Memorization without derivation is a Mid signal — practice the derivation.

3. Prerequisite Concepts

• 1D Dynamic Programming intuition: “state at index i depends only on state at index i-1” (phase-05 §1)
• Why prefix sums DON’T directly solve this (they solve “sum of any subarray” but the argmax over all O(N²) subarrays still needs O(N²) without a cleverer transform — see Section 6)
• The “all-negative” trap: max(0, ...) is wrong when every element is negative; the answer is the maximum single element
• Loop invariants in DP: what state does each scalar represent at the top of each iteration?

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

Step 1 — Restate: “Given an integer array, return the maximum sum of any contiguous non-empty subarray.”

Step 2 — Clarify:

• “Can the array contain negatives?” (Yes — this is the entire point. Pure positives is trivial.)
• “Can it be all negatives?” (Yes — the answer is the maximum single element, NOT 0.)
• “Must subarray be non-empty?” (Yes per LC. If empty allowed, answer would be max(0, kadane(nums)).)
• “Need indices or just the sum?” (Per LC, just sum. Indices are a natural follow-up — track start/end.)
• “Subarray (contiguous) or subsequence (non-contiguous)?” (Subarray. If subsequence, answer = sum of positives, trivial.)

Step 3 — Constraints: N up to 10^5 per LC. O(N²) brute (10^10) won’t fit. O(N) is required.

Step 4 — Examples:

• [-2,1,-3,4,-1,2,1,-5,4] → 6 (subarray [4,-1,2,1])
• [1] → 1
• [-1] → -1 (single negative — critical trap)
• [-3, -2, -1, -5] → -1 (all negatives — must NOT return 0)
• [5, 4, -1, 7, 8] → 23 (mostly positive — sum almost everything)
• [1, -100, 2, -100, 3] → 3 (a single big negative resets the running sum)

Step 5 — Brute Force: Two nested loops; for each (i, j) compute sum. O(N²) with the partial-sum optimization (compute running sum as j advances), O(N³) naively. State this aloud.

Step 6 — Brute Force Complexity: O(N²) time with the running-sum trick, O(1) space. Acceptable correctness oracle for small N.

Step 7 — Pattern Recognition: “Max over all contiguous subarrays” + “decision at index i depends only on whether to extend the previous best or start fresh” → Kadane’s algorithm (1D DP, collapses to O(1) space). This is the canonical “DP that doesn’t look like DP” problem.

Step 8 — Optimize: The recurrence: best_ending_here[i] = max(nums[i], best_ending_here[i-1] + nums[i]). Interpretation: at each position, either extend the previous best (if doing so makes the sum positive) or start fresh at nums[i]. The global answer is max(best_ending_here) across all i. Collapse to two scalars: curr = nums[0], best = nums[0]. For i in 1..N-1: curr = max(nums[i], curr + nums[i]); best = max(best, curr). Return best.

Step 9 — Prove correctness: Loop invariant: at the top of iteration i, curr = max sum of any subarray ending exactly at index i-1, and best = max sum of any subarray ending at indices 0..i-1. The recurrence preserves this: a subarray ending at i either includes the optimal one ending at i-1 (then sum = curr + nums[i]) or starts fresh at i (sum = nums[i]). Taking max preserves the optimal-ending-at-i invariant. Taking running max preserves best over all positions.

5. Progressive Hints

If stuck for 5 minutes, open hints.md. One hint, 5-min timer, retry.

6. Deeper Insight — Why It Works

The DP formulation, made explicit: define dp[i] = max sum of contiguous subarray ending at i (inclusive). The recurrence dp[i] = max(nums[i], dp[i-1] + nums[i]) says: the best subarray ending at i either starts at i (skip the past) or extends the best one ending at i-1. The global answer is max(dp[0..N-1]). This is a one-dimensional DP. The trick is recognizing that “ending at i” is the right state — most candidates initially think of dp[i] = “max in nums[0..i]” which leads to a recurrence that requires both “include i” and “don’t include i” cases and doesn’t collapse cleanly.

Why O(1) space: the recurrence only depends on dp[i-1], so a single scalar curr suffices. The global max is also a scalar best. No array allocation needed.

Why “all negatives” is the trap: the recurrence curr = max(nums[i], curr + nums[i]) correctly handles it: when all values are negative, nums[i] is always larger than curr + nums[i] (since curr is negative), so curr = nums[i] each step, and best tracks the maximum single element. But a popular incorrect formulation, curr = max(0, curr + nums[i]), treats “empty subarray” as legal and returns 0 — wrong because the problem requires non-empty.

Why prefix sums alone don’t solve this in O(N): with prefix sums P, the sum of subarray (i, j) is P[j] − P[i-1]. Maximizing P[j] − P[i-1] over i ≤ j IS solvable in O(N): walk left to right, track min P seen so far, take max of P[j] − min_so_far. But this IS Kadane in disguise — it’s the same algorithm rephrased. Both are O(N), one pass, O(1) extra space.

Connection to LC 121 (Buy/Sell Stock): identical algorithm. “Max profit = max over j of (price[j] − min_so_far_price)” is “max subarray sum = max over j of (P[j] − min_so_far_P)” where P is the prefix sum of price differences. The two problems are literally the same algorithm on different inputs.

Divide & conquer alternative: split in half, recursively compute (a) max subarray entirely in left half, (b) max subarray entirely in right half, (c) max subarray crossing the midpoint (linear scan). Take max of the three. O(N log N) — worse than Kadane. Worth knowing because it’s a clean example of D&C and because LC sometimes asks for both.

7. Anti-Pattern Analysis

Wrong-but-tempting #1 — Reset to 0 when sum goes negative:

curr = 0; best = float('-inf')
for x in nums:
    curr += x
    if curr < 0: curr = 0
    best = max(best, curr)
return best

Wrong for all-negative arrays: returns 0 (never updates best with a positive value). The fix is curr = max(x, curr + x) not curr = max(0, curr + x).

Wrong-but-tempting #2 — Brute force with three loops: O(N³). Even the O(N²) running-sum version is wasteful. Acceptable to state aloud as the baseline, then optimize.

Wrong-but-tempting #3 — Sort the array first: Destroys the “contiguous” constraint entirely. After sorting, “contiguous” no longer means anything meaningful about the original array.

Wrong-but-tempting #4 — DP with explicit array:

dp = [0] * len(nums)
dp[0] = nums[0]
for i in range(1, len(nums)):
    dp[i] = max(nums[i], dp[i-1] + nums[i])
return max(dp)

Correct, O(N) time, but O(N) space when O(1) suffices. For interview, this is a “didn’t notice the collapse” mark. For production with billion-element arrays, it’s an unnecessary 8GB of allocation.

Wrong-but-tempting #5 — Maintain “best including” and “best excluding” separately: Some candidates try include[i] = best ending at i and exclude[i] = best not ending at i. Works but more complex than necessary — Kadane’s only needs one DP series, not two.

8. Skills & Takeaways

Generalizable patterns:

• 1-D DP with state collapse: any DP where dp[i] depends only on dp[i-1] collapses to O(1) space. Reappears in: climbing stairs (p05), house robber (LC 198), best time to buy/sell stock (p03), maximum product subarray (LC 152).
• “Extend or restart” decision: many subarray/substring problems ask “extend the current run or start fresh at this index?” — Kadane is the prototypical example.
• All-negative / all-zero / empty traps: any “max sum” problem with negatives requires checking whether empty subarray is allowed and handling all-negative correctly.

Analogous problems:

• LC 121 — Best Time to Buy/Sell Stock (Kadane on differences — your p03, same algorithm)
• LC 152 — Maximum Product Subarray (Kadane with two states: max-and-min ending here, because a negative times negative becomes max — Hard variant)
• LC 198 — House Robber (Kadane-style 1D DP with “skip current” choice)
• LC 918 — Maximum Sum Circular Subarray (Kadane twice — once for max, once for min, then global - min)
• LC 1186 — Maximum Subarray Sum with One Deletion (Kadane with two-state DP: “best ending here without deletion” and “with deletion”)
• LC 363 — Max Sum Rectangle ≤ K in Matrix (Kadane lifted to 2D)
• LC 53 itself is sometimes asked as “return the actual subarray, not just the sum” — extension: track start/end indices alongside curr/best.

When NOT to use this: non-contiguous subsequences (different problem, trivial: sum of positives or LIS-family). Streaming with multiple deletions (need a more complex deque-based variant).

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

• I derived the recurrence dp[i] = max(nums[i], dp[i-1] + nums[i]) on paper before coding
• My code uses TWO scalars (not an array) and handles all-negative correctly
• I can explain why max(nums[i], ...) is right and max(0, ...) is wrong
• I can articulate the loop invariant of both curr and best
• I can sketch the divide-and-conquer O(N log N) alternative and explain why Kadane is better
• My stress_test() passes 1000 iterations against the O(N²) brute force
• I solved LC 152 (Max Product Subarray) and saw the two-state extension of Kadane
• I noticed that p03 (Buy/Sell Stock) is the same algorithm on differences

If any unchecked: redo before moving to p10.

10. Company Context

Amazon (extremely common — every coding round may see this or a variant)

• The framing: Often in story form: “Given daily P&L, find the most profitable contiguous trading window.”
• Misleading example: They give you [1, 2, 3, 4] (all positive — trivial). Then [-1, -2, -3] (all negative — exposes whether you fell for the max(0, ...) trap).
• Adversarial extension: “Now return the actual subarray (start and end indices), not just the sum.” (Track start candidate when you reset; finalize when best updates.) Then: “Now allow ONE element to be deleted.” (LC 1186.)
• What they want to hear: Explicit derivation aloud. Verbatim phrase that earns points: “At each index I have two choices — extend or restart — and I pick whichever gives a larger sum ending here.”

Microsoft (loves the DP derivation question)

• The framing: Standard problem.
• Misleading example: [5, -10, 4, -1, 5] — first element is the temporary best (5), then a big negative pulls curr down, then you have to recognize that starting fresh at 4 was better.
• Adversarial extension: “Now return the indices.” Then “Now find the max-sum subarray in a 2D matrix.” (LC 363’s cousin — fix two rows, collapse columns, apply Kadane.)
• What they want to hear: Articulation of the DP state and recurrence. Microsoft phone screens explicitly score “derived the recurrence” as a separate rubric line.

Bloomberg (financial — they LOVE this problem)

• The framing: “Given a price series, find the optimal long-only trading window with no shorting allowed.”
• Misleading example: Includes negative price changes throughout — tests the all-negative handling.
• Adversarial extension: “Now with transaction costs of X — subtract X from each profit.” Then “Now what if shorting is allowed?” (Absolute value Kadane.)
• What they want to hear: Recognition that this IS Buy/Sell Stock in disguise, with explicit framing: “If I difference the price series, Kadane on the diffs gives the max single trade.” Bloomberg likes seeing the algorithmic family tree.

Apple (clarity + clean code)

• The framing: Standard.
• What they want to hear: Idiomatic code, clear variable names (curr, best, not c, b), explicit handling of empty / single-element inputs.

Meta (less common; usually appears as the harder LC 152 variant)

• The framing: Often LC 152 (Max Product) directly, with this as warmup if you fumble.
• What they want to hear: Awareness that product has two states (positive and negative) because negative × negative = max.

Google (medium frequency; high bar)

• The framing: Sometimes the divide-and-conquer version is asked explicitly, to test that you can write D&C cleanly.
• What they want to hear: Both Kadane (O(N)) and D&C (O(N log N)), with explicit “Kadane wins on this problem but D&C generalizes to 2D and to certain parallel implementations.”

11. Interviewer’s Lens

The scorecard line that gets you the offer: “Derived Kadane’s recurrence on the spot; optimized to O(1) space; recognized this as Buy/Sell Stock in disguise.”

The scorecard line that loses you: “Used max(0, ...) formulation; returned 0 on all-negative input; required interviewer to debug.”

12. Level Delta

13. Follow-up Questions & Full Answers

Follow-up 1: “Return the actual subarray, not just the sum.”

Signal sought: Bookkeeping discipline.

Full answer: “Track candidate start. When we ‘restart’ (i.e., nums[i] > curr + nums[i]), set tmp_start = i. When best updates, snapshot start = tmp_start, end = i. Return nums[start:end+1]. Single pass, O(1) extra state. Edge case: all-negative — tmp_start = end = argmax(nums), single-element subarray.”

Follow-up 2: “Now allow one element deletion.” (LC 1186)

Signal sought: Extending the state.

Full answer: “Two-state DP. with_delete[i] = best subarray ending at i using one deletion; without_delete[i] = best ending at i with no deletion. Recurrences: without[i] = max(nums[i], without[i-1] + nums[i]) (standard Kadane). with[i] = max(without[i-1], with[i-1] + nums[i]) — either delete nums[i] (carrying without[i-1] forward) or keep nums[i] and have already deleted earlier. Answer = max over all i of max(with[i], without[i]). Collapses to two scalars each. O(N) time, O(1) space.”

Follow-up 3: “Maximum sum circular subarray.” (LC 918)

Signal sought: Algorithmic re-application.

Full answer: “The optimal subarray is either (a) a normal subarray (Kadane gives this), or (b) wraps around — equivalently, (total sum) − (some subarray we exclude), so we want to MINIMIZE a subarray (Kadane on negated array). Return max(kadane(nums), total − min_subarray(nums)). Special case: if all elements are negative, the wraparound formula would ‘exclude everything’ = 0, but the problem requires non-empty, so handle separately: if max kadane result is negative, return that. Two Kadane passes. O(N) time, O(1) space.”

Follow-up 4: “Divide and conquer formulation.”

Signal sought: Algorithm versatility.

Full answer: “Recursively: max-subarray(arr) = max of {max-subarray(left half), max-subarray(right half), max-crossing-subarray(mid)}. The crossing case requires a linear scan from mid outward in both directions to find the best left-extending and right-extending pieces. Recurrence: T(N) = 2T(N/2) + O(N) → O(N log N). Worse than Kadane on a single machine but the D&C structure parallelizes cleanly and generalizes to 2D (LC 363’s cousin). Worth knowing both.”

Follow-up 5 (Hard, Principal signal): “Parallel Kadane across K machines.”

Signal sought: Distributed thinking, monoid recognition.

Full answer: “Each machine holds a contiguous shard. Each computes four scalars: (total_sum, max_prefix, max_suffix, max_subarray) over its shard. These compose associatively under a ‘merge’ operation: when merging shard A then shard B, the merged max_subarray is max(A.max_subarray, B.max_subarray, A.max_suffix + B.max_prefix). This is a monoid — the four-tuple under merge is associative with identity (0, 0, 0, -∞). That means we can map-reduce the entire computation: each shard contributes its 4-tuple, reduce them pairwise in any tree order. O(N/K) per machine, O(log K) reduction depth. SIMD implementations use the same trick at the cache-line level. This is a beautiful example of ‘rewrite the algorithm as a monoid to make it parallel.’”

14. Full Solution Walkthrough

See solution.py.

The file has six sections:

1. max_subarray_brute(nums) — O(N²) with running-sum trick; correctness oracle.
2. max_subarray(nums) — Kadane in two scalars; INVARIANT comments.
3. max_subarray_dp_array(nums) — Kadane with the explicit dp[] array; included for didactic comparison.
4. max_subarray_divide_conquer(nums) — O(N log N) version; useful to know.
5. stress_test() — generates 1000 random arrays including all-negative, asserts all four implementations agree.
6. edge_cases() — single positive, single negative, all-negative, all-positive, all-zero, the canonical example, sparse positives among negatives.

Decisions justified:

• Why init curr = best = nums[0] (not 0): empty subarray not allowed.
• Why max(nums[i], curr + nums[i]): handles all-negative correctly.
• Why we include the dp_array version: shows the unoptimized DP for didactic clarity, then we point out the collapse.

15. Beyond the Problem — Production Reality

Real applications of Kadane:

• Financial windowing: maximum profit / drawdown / volume window in time series. Trading desks compute “best trading interval” over historical bars; Kadane is the kernel.
• Anomaly detection: maximum contiguous deviation from baseline in monitoring data (Datadog, Prometheus).
• Genomic analysis: maximum-scoring local alignment (BLAST, Smith-Waterman) — the inner score recurrence is Kadane-like.
• Image processing: max-sum rectangle in a 2D image (LC 363) uses Kadane on collapsed column sums; appears in object-detection preprocessing.
• Signal processing: detecting bursts in a noisy signal — Kadane on (signal − threshold) finds the strongest burst window.

Production caveat — floating-point Kadane: if nums are floats with both positives and negatives, naive Kadane can accumulate floating-point error in curr. Use Kahan summation if precision matters. Production financial code does this.

Parallelization: the monoid formulation in Section 13.5 is real — Apache Spark MLlib’s vector-window algorithms use this structure to parallelize across executors. The four-scalar representation is the secret.

Principal-engineer code review comment: “Kadane is correct but our 2D variant (LC 363, applied to image kernels) is O(M²·N). We’ve seen people ‘cleverly’ parallelize by chunking rows, then have the chunks lose the cross-chunk optimal. Use the four-scalar monoid form for any parallel/chunked version — it’s the only correct way. Also: please add a unit test for the all-equal-negative array. We’ve shipped two bugs from max(0, ...) formulations.”

p09 Maximum Subarray — Progressive Hints

Rule: Read ONE hint. Set a 5-minute timer. Try again. Only read the next hint if the timer expires.

Hint 1 — Pattern family

Think about walking the array left to right. At each index, you face a yes/no decision: should the optimal subarray ending at this index extend what came before, or start fresh at this element?

Hint 2 — DP state

Let dp[i] = the maximum sum of any contiguous subarray that ends exactly at index i. The global answer is max(dp[i]) over all i. Can you write dp[i] in terms of dp[i-1] and nums[i]?

Hint 3 — The recurrence

dp[i] = max(nums[i], dp[i-1] + nums[i])

Either extend the best subarray ending at i-1 (if doing so beats starting fresh) OR restart at i. Take whichever is larger.

Critical trap: the recurrence is max(nums[i], ...), NOT max(0, ...). The latter is wrong for all-negative arrays — it would return 0, but the problem requires a non-empty subarray.

Hint 4 — Pseudocode skeleton + space collapse

curr = nums[0]                  # dp[i-1]
best = nums[0]                  # global max
for i in 1..N-1:
    curr = max(nums[i], curr + nums[i])
    best = max(best, curr)
return best

Two scalars, not an array. dp[i] only depends on dp[i-1], so a single variable suffices.

Hint 5 — Full algorithm + correctness

Kadane’s algorithm. Walk the array. Maintain two scalars:

• curr = max sum of any subarray ending exactly at the current index
• best = max sum of any subarray seen so far

For each new element x:

1. curr = max(x, curr + x) — extend the previous best or restart at x.
2. best = max(best, curr) — update running global maximum.

Loop invariant: at the top of iteration i, curr holds the best sum ending at i-1; best holds the global max over all positions 0..i-1. The recurrence preserves both, so after the loop best is the global maximum.

Why all-negative works: for [-3, -2, -1], at i=1: curr = max(-2, -3 + -2) = max(-2, -5) = -2; best = max(-3, -2) = -2. At i=2: curr = max(-1, -2 + -1) = -1; best = -1. Returns -1, the correct answer. The recurrence naturally restarts whenever nums[i] > curr + nums[i], which happens exactly when curr < 0.

Time O(N), space O(1). One pass.

Bonus — divide and conquer (O(N log N)): split in half, recursively find best in left and right halves AND the best subarray crossing the midpoint (linear scan outward from mid). Take max of three. Worse complexity than Kadane on a single machine but generalizes to 2D and parallelizes well.

p10 — Contains Duplicate

Source: LeetCode 217 · Easy · Topics: Array, Hash Table, Sorting Companies (2024–2025 frequency): Amazon (high), Microsoft (high), Apple (medium), Bloomberg (medium), Meta (medium), Google (medium) Loop position: phone screen warmup; the lead-in to LC 219 (Contains Duplicate II — sliding window) and LC 220 (Contains Nearby Almost Duplicate — bucket sort)

1. Quick Context

The interviewer’s bar is not “can you solve it” — even a freshman can. The bar is: how many distinct approaches can you enumerate and rank by tradeoff? Strong candidates list 3–4 (sort, hash set, brute force, statistical/Bloom for huge N), state the time/space cost of each, then pick. Mid candidates pick HashSet first without naming alternatives. This is the cheapest problem in the curriculum at which to demonstrate the “I think about tradeoffs, not just solutions” senior signal.

It’s also the gateway to a family of problems: LC 219 (within-K distance — sliding window), LC 220 (within-K distance AND within-T value — bucket / treemap), LC 287 (find THE duplicate in O(1) space with constraints — Floyd’s), LC 442 (find ALL duplicates with in-place marking).

What it looks like it tests: detect a duplicate. What it actually tests: can you enumerate approaches and pick the right one based on memory / time / sortability constraints? Do you know when each wins?

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/contains-duplicate/

STOP. Set a 10-minute timer. Code it cold. Do not read past this section until solved or expired.

If repeat: write THREE distinct solutions in the same scratch file. Brute, sort, HashSet. Time yourself for ALL THREE in 8 min. The point isn’t to pick one — it’s to demonstrate fluency across approaches.

3. Prerequisite Concepts

• HashSet / HashMap O(1) average insertion and lookup (phase-01 §3)
• Sorting cost trade: O(N log N) time, O(1) extra space (if in-place sort allowed) vs HashSet’s O(N) time AND space
• Adjacent-equal detection after sort: a O(N) linear scan post-sort
• For massive N (billions, doesn’t fit memory): probabilistic structures (Bloom filter for “definitely-not-seen”, HyperLogLog for cardinality estimation)

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

Step 1 — Restate: “Given an integer array, return True if any value appears at least twice; else False.”

Step 2 — Clarify:

• “What’s N’s upper bound?” (LC says 10^5; ask anyway, the production answer changes for 10^9.)
• “Is the input mutable? Can I sort in place?” (Mutation may be off-limits in production; HashSet is the non-mutating choice.)
• “Memory budget?” (If tight, sort + scan is O(1) extra; HashSet is O(N).)
• “What are valid values? Negatives? Floats?” (Per LC, integers; in production ask.)
• “Repeats considered duplicates if they are at the same index?” (No — same index is the same value, not a duplicate. Trivial, but ask.)

Step 3 — Constraints: N up to 10^5 per LC. Both O(N log N) and O(N) fit comfortably. Brute O(N²) = 10^10 will TLE. Solution memory: O(N) for HashSet, O(1) for sort-based (if in-place).

Step 4 — Examples:

• [1, 2, 3, 1] → True
• [1, 2, 3, 4] → False
• [1, 1, 1, 1] → True (early exit on iteration 2)
• [] → False (no values, no duplicate — confirm with interviewer)
• [7] → False (single element)
• [-1, -1, 0] → True (negatives)

Step 5 — Brute Force: Nested loop, compare every pair. O(N²) time, O(1) space. Acceptable as a stated baseline; never the final answer.

Step 6 — Brute Force Complexity: O(N²), O(1). TLE for LC’s constraint of 10^5.

Step 7 — Pattern Recognition: “Detect repetition in a sequence” → HashSet membership check (canonical) OR sort + adjacent compare (when memory matters). Family: LC 219 (with distance constraint → sliding window of size K), LC 220 (with distance AND value constraint → bucket-sort by value range), LC 287 (one specific duplicate in O(1) extra space → Floyd’s).

Step 8 — Optimize: Single-pass HashSet. Walk the array; for each x, if x in seen return True; else add x to seen. Return False at end. O(N) avg time, O(N) space. Early exit on first duplicate.

Step 9 — Prove correctness: Loop invariant: at top of iteration i, seen = {nums[0..i-1]} as a set. If nums[i] ∈ seen, then nums[i] equals some nums[j] with j < i — a true duplicate. If not, add and continue. After the loop, no duplicate was found, so all N values are distinct.

5. Progressive Hints

If stuck for 5 minutes, open hints.md. One hint, 5-min timer, retry.

6. Deeper Insight — Why It Works

Why HashSet is the textbook answer: “find a repeat” is structurally “have I seen this before?” — a membership question. The data structure built for that question in O(1) is the hash set. Memorize this connection: membership question → hash set.

Why sort-then-adjacent-compare is sometimes better: if N is huge but you can mutate, sort gives O(N log N) time and O(1) extra space (in-place sort). HashSet gives O(N) time but O(N) extra space. Memory often dominates the real cost — in Python, the overhead per dict entry is ~64 bytes, so a HashSet of 10^7 integers is ~640MB, which can push containers into OOM. Sort-based is the call for memory-constrained environments.

Why early exit matters: the HashSet check returns True the moment a duplicate is found. For arrays with frequent duplicates, expected runtime is O(distinct values) not O(N). The brute force can also early-exit, but its constant factor is worse and worst case is still O(N²).

Bloom filters for streaming / massive N: if N is 10^11 and you can’t fit a HashSet, a Bloom filter gives “definitely-not-seen” (no false negatives) with false-positive rate tunable by space. A pass with Bloom + a confirmation pass for flagged values gives expected O(N) at sub-N space. This is how anti-spam, anti-fraud, and CDN cache-membership work in production.

Why “Counter” overkill: Counter(nums).most_common(1)[0][1] > 1 works but allocates a full counter when you only need to know “any repeat?” — wastes O(distinct) memory growing to O(N) instead of early-exiting at first repeat. Idiomatic but suboptimal.

Why len(nums) != len(set(nums)) is cute but slow: materializes the full set even if a duplicate exists at index 1. Loses the early-exit advantage. For an array with a duplicate near the start, it’s O(N) where it could be O(2). The one-line elegance is a tradeoff against worst-case performance.

7. Anti-Pattern Analysis

Wrong-but-tempting #1 — Brute force:

for i in range(n):
    for j in range(i + 1, n):
        if nums[i] == nums[j]: return True
return False

O(N²). For N=10^5, this is 10^10 operations. TLE on LC, OOM-irrelevant but compute-fatal. State as baseline, then optimize. Never the final answer.

Wrong-but-tempting #2 — len(set(nums)) != len(nums):

return len(set(nums)) != len(nums)

Pythonic one-liner, O(N) time, O(N) space, but no early exit. Materializes the entire set even when the second element is a duplicate. For interview, mention as a fallback but explicitly note: “I’d write the explicit loop for early exit; this one-liner pays O(N) even on best-case inputs.”

Wrong-but-tempting #3 — Sort then check adjacent, mutating input without asking:

nums.sort()
return any(nums[i] == nums[i+1] for i in range(len(nums) - 1))

Works, O(N log N) time, O(1) extra space if sort is in-place. But mutates input. In production this can break callers. Always ask “may I mutate?” — if yes, this is the memory-efficient answer.

Wrong-but-tempting #4 — Counter / dict to count:

from collections import Counter
return any(c > 1 for c in Counter(nums).values())

O(N) time, O(distinct) space, no early exit (Counter is built fully before iterating values). HashSet with explicit loop is strictly better.

Wrong-but-tempting #5 — Treating it like LC 219 / 220 without being asked: Some candidates over-engineer and start using a sliding window or a sorted set. The vanilla problem doesn’t care about position or value distance. Solve what’s asked. Save the sliding-window for the follow-up.

8. Skills & Takeaways

Generalizable patterns:

• Membership question → HashSet: any “have I seen this before?” question solves in O(1) avg per check.
• Memory vs time tradeoff articulation: sort + scan (O(N log N), O(1)) vs HashSet (O(N), O(N)). Knowing both is Senior; knowing when to pick which is Staff.
• Early-exit discipline: prefer explicit loops that can return on first success over one-liners that always materialize the full structure.

Analogous problems:

• LC 219 — Contains Duplicate II (within K indices → sliding window of HashSet of size K)
• LC 220 — Contains Nearby Almost Duplicate (within K indices AND |val_i − val_j| ≤ T → bucket sort by val ranges, OR a sorted multiset with binary search)
• LC 287 — Find the Duplicate Number (Hard; O(1) space → Floyd’s on nums[nums[i]])
• LC 442 — Find All Duplicates in an Array (in-place marking by negating nums[abs(x) - 1])
• LC 268 — Missing Number (the inverse: XOR or sum trick)
• LC 136 — Single Number (XOR every element: pairs cancel, the loner remains)
• LC 645 — Set Mismatch (one missing + one duplicate; combine XOR and counting)