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:
| N | Acceptable Complexity | Likely Approach |
|---|---|---|
| ≤ 10 | O(N!) or O(2^N · N) | Backtracking, bitmask brute force |
| ≤ 20 | O(2^N · N) | Bitmask DP, meet-in-the-middle |
| ≤ 100 | O(N^4) | Multi-loop brute, Floyd-Warshall |
| ≤ 500 | O(N^3) | Interval DP, matrix chain |
| ≤ 5,000 | O(N^2) | 2D DP, edit distance |
| ≤ 100,000 | O(N log N) or O(N √N) | Sort + scan, segment tree, sqrt decomp |
| ≤ 1,000,000 | O(N) or O(N log N) | Linear scan, hashmap, two pointers |
| ≤ 10^8 | O(N) or O(log N) | Math closed form, binary search on answer |
| ≤ 10^18 | O(log N) | Binary exponentiation, math |
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