✦ Reference Hub
How to Solve Any Coding Problem 🧠
The difference between candidates who ace interviews and those who don't isn't raw intelligence — it's having a repeatable framework. This page is that framework.
The Core Truth
Interviewers aren't testing if you've seen the exact problem before. They're testing how you think: Do you communicate? Do you clarify? Do you recognize patterns? Do you handle setbacks gracefully? This framework trains exactly those skills.
1. The 5-Step Framework
Apply this every single time. Not sometimes — every time. It takes 30 seconds and prevents the #1 interview mistake: jumping to code before understanding the problem.
| Step | What to Do | What to Say Out Loud | Time Budget |
|---|---|---|---|
| 1. Understand | Read the problem. Identify: inputs, outputs, constraints, edge cases. Ask clarifying questions. | "So we're given an array of integers and need to find… Let me confirm: can the array be empty? Can values be negative? Are there duplicates?" | 2–3 min |
| 2. Examples | Work through 2–3 examples by hand. Include edge cases: empty, single element, all same. | "Let me trace through this example: [1,2,3] → output 6. And edge case: empty array → 0. Makes sense." | 2–3 min |
| 3. Brute Force | State the simplest correct solution, even if it's O(N²) or worse. Explain its complexity. | "The naive approach: for every pair, check if they sum to target. That's O(N²) time, O(1) space. Too slow for N=10⁵, but let me start here." | 2 min |
| 4. Optimize | Identify the bottleneck. Apply the optimization ladder. Get interviewer buy-in before coding. | "The bottleneck is the nested loop. If I use a hash set, I can check membership in O(1), reducing it to O(N). Can I code that up?" | 5–10 min |
| 5. Code + Test | Code the optimized solution. Trace through your example. Check edge cases. | "Let me trace through [2,7,11,15] with target=9… result is [0,1]. Edge case empty array: return empty. Looks good." | 15–20 min |
2. Pattern Recognition Cheat Sheet
When you read a problem, scan it for these keywords. They almost always map to a specific pattern or algorithm class.
| Keywords / Signals | Pattern to Try First | Why |
|---|---|---|
| "subarray", "substring", "contiguous", "window of size k" | Sliding Window | Avoid recomputing — slide a window instead |
| "sorted array", "pair with sum", "remove duplicates", "two indices moving" | Two Pointers | Sort + two ends meet in the middle |
| "find in sorted", "rotated array", "first/last occurrence", "search in log time" | Binary Search | Monotonic predicate → bisect |
| "all combinations", "all subsets", "all paths", "generate all" | Backtracking | Explore decision tree, prune early |
| "shortest path", "minimum steps", "level order", "K steps away" | BFS | BFS guarantees shortest path in unweighted graphs |
| "connected components", "cycle detection", "island count", "flood fill" | DFS / Union-Find | Traverse and mark connected regions |
| "max/min subarray", "number of ways", "optimal cost", "can we achieve X" | Dynamic Programming | Overlapping subproblems + optimal substructure |
| "intervals", "meeting rooms", "overlapping ranges", "merge" | Intervals / Greedy | Sort by start/end, sweep line |
| "next greater element", "monotonic", "stock prices", "valid parentheses" | Monotonic Stack | Maintain invariant while scanning |
| "top K", "K closest", "median stream", "K most frequent" | Heap (Priority Queue) | Keep K elements efficiently |
| "prefix sum", "range sum query", "subarray sum equals K" | Prefix Sum / HashMap | Precompute for O(1) range queries |
| "tree path", "LCA", "diameter", "depth", "ancestor" | Tree DFS (post-order) | Build answer bottom-up from leaves |
| "word search", "autocomplete", "starts with", "prefix matching" | Trie | Shared prefix structure |
| "repeated character", "anagram", "frequency count" | HashMap / Array Frequency | Count occurrences, detect duplicates |
| "design", "O(1) operations", "LRU cache" | HashMap + Doubly Linked List | Hash for O(1) lookup, list for O(1) order |
3. Brute Force → Optimal: The Optimization Ladder
When your brute force is too slow, apply these techniques in order until one fits.
| Technique | When to Try | Example Transform |
|---|---|---|
| 1. Cache repeated work (Memoization) | Recursive solution recomputes same subproblems | Naive Fibonacci O(2ⁿ) → memoized O(N) |
| 2. Trade space for time (Hash Map) | Searching for something in O(N) — make it O(1) | Two Sum O(N²) → O(N) with hash set |
| 3. Sort first | Many problems become trivial on sorted input | Two Sum in sorted array → two pointers O(N) |
| 4. Shrink the search space (Binary Search) | Answer is monotonic ("if X works, X+1 also works") | Capacity ship packages → binary search on capacity |
| 5. Avoid recomputation (Prefix/Suffix) | Repeated range queries on static array | Subarray sum O(N) per query → O(1) with prefix sum |
| 6. Sliding Window | Brute force tries all windows — most work is redundant | Max sum subarray of size K: O(NK) → O(N) |
| 7. Greedy Choice | Local optimal = global optimal (provable) | Activity selection: sort by end time, always pick earliest |
| 8. Mathematical formula | Loop over 1..N computing sum/product | Sum of 1..N: O(N) loop → O(1) formula N(N+1)/2 |
4. Dynamic Programming Decision Framework
Use this checklist to decide if DP applies and how to structure it.
Is it DP? — Two Requirements
- Optimal Substructure: Optimal solution uses optimal solutions to subproblems.
- Overlapping Subproblems: Same subproblems are solved multiple times in recursion.
If both are true → DP. If optimal substructure but no overlapping → Greedy or Divide & Conquer.
| Question | How to Answer |
|---|---|
| What are the states? | What information uniquely defines a subproblem? Usually index(es) + remaining capacity/target |
| What is dp[i] / dp[i][j]? | Define precisely in English first: "dp[i] = maximum profit using first i items" |
| What is the transition? | How does dp[i] depend on dp[i-1] or earlier states? |
| What are the base cases? | dp[0] or dp[0][0] — the trivial case with no items/no capacity |
| Top-down or bottom-up? | Top-down = recursion + memo (easier to write). Bottom-up = iterative table (faster, no stack) |
| Can space be optimized? | If dp[i] only depends on dp[i-1], use rolling array to reduce from O(N²) to O(N) |
DP Pattern Recognition
| Problem Type | DP Pattern | State Definition |
|---|---|---|
| Longest increasing subsequence | 1D DP + binary search | dp[i] = LIS ending at index i |
| 0/1 Knapsack | 2D DP → 1D with rolling array | dp[i][w] = max value with first i items, capacity w |
| Edit distance / LCS | 2D DP | dp[i][j] = answer for prefix s1[0..i], s2[0..j] |
| Coin change (min coins) | 1D DP (unbounded knapsack) | dp[amount] = min coins to make amount |
| Matrix chain multiplication | Interval DP | dp[i][j] = min cost to multiply matrices i..j |
| Partition into subsets | Bitmask DP | dp[mask] = can we form this subset |
5. Greedy Decision Framework
When does Greedy work?
Greedy works when a locally optimal choice at each step leads to a globally optimal solution. This must be proven, not assumed. The standard proof is the exchange argument: assume an optimal solution differs from greedy → show you can swap greedy's choice in without making things worse → contradiction.
| Problem | Greedy Choice | Why it works |
|---|---|---|
| Activity Selection | Always pick the activity finishing earliest | Leaves maximum room for future activities |
| Huffman Coding | Always merge two lowest-frequency nodes | Minimizes total weighted path length |
| Fractional Knapsack | Pick highest value/weight ratio first | Fractional allows partial items — no commitment needed |
| Jump Game | Extend max reach greedily at each step | Max reach only increases — never need to look back |
| Minimum spanning tree | Always pick cheapest edge that doesn't create cycle (Kruskal) | Cut property of MSTs |
6. The Complete Interview Script
Phase 1: Understanding the Problem
Say This
- "Let me make sure I understand the problem. We're given [restate in your own words]."
- "Can the input be empty? What should I return in that case?"
- "Are the values guaranteed to be positive/unique/sorted?"
- "What's the range of N? That'll help me figure out the required complexity."
Phase 2: Before You Code
Say This
- "Let me think through the brute force first — just to make sure I understand the problem fully."
- "The brute force is O(N²) — for N = 10⁵ that'd be 10¹⁰ operations, too slow."
- "I'm thinking I can use [pattern] to bring it down to O(N log N). Here's the idea: [explain]. Does that approach make sense before I start coding?"
Phase 3: While Coding
Say This
- "I'm initializing the hash map here to store [what it stores]."
- "This loop runs N times, each iteration is O(1) — so O(N) total."
- "I'm using lo + (hi - lo) / 2 instead of (lo + hi) / 2 to avoid integer overflow."
Phase 4: If You're Stuck
Don't Freeze — Say This
- "Let me think about this differently — what if I look at it from the end?"
- "I'm not immediately seeing the optimal solution. Can I talk through what I've tried so far?"
- "I know the brute force works. Let me think about what information I'm recomputing unnecessarily..."
- Silence for more than 60 seconds = bad. Thinking out loud, even when stuck, shows process.
7. Common Mistakes & How to Avoid Them
| Mistake | Symptom | Prevention |
|---|---|---|
| Off-by-one in loops | Last element missed, or index out of bounds | Always check: should it be i < n or i <= n? Trace with n=1, n=2. |
| Integer overflow | Wrong answer on large inputs, no compile error | Use long proactively. Mental check: will a*b exceed 2×10⁹? |
| Null/None pointer | Runtime crash on edge cases | Always check: can the head/root be null? Handle empty input first. |
| Modifying input array | Corrupts test cases in multi-test environments | Ask: "Can I modify the input?" If unsure, copy it. |
| Wrong base case in DP | Correct transitions, wrong final answer | Trace the simplest case by hand. dp[0] must be set correctly. |
| Not returning anything | Function returns undefined/null | Write the return statement first, then fill in the logic. |
| Using == on strings (Java) | Reference comparison, not value comparison | Always use .equals() in Java for string comparison. |
| Infinite loop | Code hangs, TLE | Every loop must have a guaranteed termination condition. Check: does the loop variable always progress? |
8. Time Estimation — What Can You Code in 30 Minutes?
| Approach | Typical Code Length | Time to Code | Recommendation |
|---|---|---|---|
| Two pointers / Sliding window | ~15–25 lines | 5–8 min | Always try this first if applicable |
| HashMap solution | ~20–30 lines | 5–10 min | Fast to write, explain clearly |
| BFS/DFS | ~25–40 lines | 8–12 min | Template helps — memorize it |
| Binary search | ~20–30 lines | 6–10 min | Easy to get wrong — trace carefully |
| 1D DP | ~20–35 lines | 8–15 min | Write state definition in comment first |
| 2D DP | ~30–50 lines | 15–25 min | Risky in 45-min interview — simplify if possible |
| Union-Find | ~30–45 lines | 10–15 min | If you've memorized the template: fast |
🏆 The Golden Rule
A working O(N²) solution with clear explanation beats a half-finished O(N log N) solution with no explanation. Always have a working solution before optimizing. Interviewers can guide you to the optimal from a working brute force — they can't do anything with unfinished code.
Practice These Patterns