Mindset & Problem Solving

01 · why it exists

Why this exists, and the weight it carries

since1945

A problem-solving routine (Pólya → UMPIRE)

George Pólya; UMPIRE as taught by CodePath

In How to Solve It (1945), the mathematician George Pólya turned problem solving into a checklist. Its four headings: understanding the problem, devising a plan, carrying out the plan, looking back. CodePath's UMPIRE interview strategy — Understand, Match, Plan, Implement, Review, Evaluate — follows the same arc for coding rounds, adding "match it to a known pattern" and "evaluate the cost".

the problem it solvedFreezing in front of an unfamiliar problem: a routine always gives you a next step that needs no flash of genius.

its jobs today

Coding interviews: it structures a 45-minute round, so you're never sitting in silence.
Everyday engineering: clarify the requirement, build the simple version, then measure and improve — the same loop behind design docs.
Code review: Review and Evaluate are what reviewers do — trace an example, try edge cases, ask about cost.

the weight it carries

Illustrative: a 45-minute round. Understand costs about 5 minutes — 5 / 45 ≈ 11% of the round. Skip it, find out at minute 30 that you solved a different problem, and 30 / 45 ≈ 67% of the round is gone.

without it

You jump into code, solve the wrong problem, or hit a wall at minute 20 with nothing on the board — and panic makes it worse.

when · why · how

when: Every problem, every time — most of all when it looks unfamiliar.
why: About 5 minutes of planning protects the other 40: no typing on a misunderstood problem, and a correct brute force is always on the table.
how: Out loud: restate + examples (U), name a pattern (M), brute force with its Big-O then a better plan (P), code it in clear Java (I), dry-run + edge cases (R), state time and space (E).

since1983

Brute force first, then remove the bottleneck

Stephen C. Johnson & Brian W. Kernighan (in print); often attributed to Kent Beck

Trying every candidate is as old as counting — nobody invented it. What engineers did write down is the order of work: "first make it work, then make it right, and, finally, make it fast" (Johnson & Kernighan, BYTE, August 1983). The same line is often attributed to Kent Beck. In an interview it becomes: say the brute force, find its bottleneck, then upgrade.

the problem it solvedOptimising — or freezing — before anything works. A slow, correct answer gives a baseline, a fallback and a target to beat.

its jobs today

Reference implementation: the slow, obviously-correct version that tests compare the fast one against.
Interview fallback: a working O(n²) answer scores far better than an unfinished O(n) one.
Finding the bottleneck: once it works, you can see which step repeats work — a nested search, a recomputed sum.

the weight it carries

Illustrative: Two Sum on n = 10⁴ numbers. Brute force checks n(n − 1)/2 = 49,995,000 pairs. A one-pass HashMap does at most 10⁴ lookups + 10⁴ inserts = 20,000 operations — about 2,500× fewer.

without it

You stare at a blank editor waiting for the clever idea, or code a clever idea you can't prove — with nothing to fall back on.

when · why · how

when: Right after you understand the problem: say it in one or two sentences with its Big-O.
why: It's correct and quick to state, and its cost tells you exactly what the optimal must beat — e.g. O(n²) → O(n) by spending O(n) memory.
how: Two nested for loops with j = i + 1 (each pair once) — then ask which inner search a HashMap, a sort or a prefix sum can replace.

since1949

Dry run (trace table)

Alan Turing

In June 1949, at the Cambridge conference that opened the EDSAC computer, Turing gave a short talk, "Checking a Large Routine". His advice: the programmer should write down definite assertions about the variables, each of which can be checked on its own. He showed it on a factorial routine, with the assertions laid out as a table. A trace table is the everyday version: what each variable holds after each step.

the problem it solvedChecking a long program by staring at it as a whole. Small, checkable facts about each step make bugs visible one row at a time.

its jobs today

Interviews: dry-running your code on the example before saying "done" catches off-by-one and wrong-update bugs.
Debugging: a debugger's watch panel, or a few System.out.println lines, is a trace table the computer fills for you.
Code review: reviewers trace a tricky loop on a tiny input to convince themselves it ends and is right.

the weight it carries

Illustrative: reverseDigits(1230) runs 4 iterations with 3 changing variables (n, digit, rev) — a 4 × 3 table of 12 values, about a minute of writing — and it shows the trailing zero vanishing (the answer is 321).

without it

You say "I think it works", the interviewer runs the example, and the off-by-one they find costs far more than the minute a dry run would have.

when · why · how

when: After coding and before saying "done" — and on any loop whose boundaries you're not sure about.
why: It costs one row per iteration on a tiny input, and finds the same bugs a test run would — without a computer.
how: One column per variable, one row per iteration; change only what the Java line changes. With a computer, print the same row: System.out.println(n + " " + digit + " " + rev);

since1998–2000

Stress testing against a brute force

William M. McKeeman (differential testing); Koen Claessen & John Hughes (QuickCheck)

At DIGITAL, McKeeman tested C compilers by running the same machine-generated test programs through several compilers and comparing the results. He called it differential testing (Digital Technical Journal, 1998). In 2000, Claessen and Hughes presented QuickCheck: state a property, and the tool generates random inputs to break it. Comparing your fast solution with your brute force on random inputs is the same idea at practice scale.

the problem it solvedBugs that hide in inputs you would never think to write by hand.

its jobs today

Compiler testing: feed the same random programs to two compilers and flag any difference in behaviour.
Property-based testing: QuickCheck-style tools generate random inputs that try to break a property you state.
Practice: compare an optimised solution with a brute force on thousands of tiny random cases before trusting it.

the weight it carries

Illustrative: the stress test in this chapter runs 2,000 random arrays of length 2–9. Even at length 9 the brute force checks only 9·8/2 = 36 pairs, so the whole run is under 2,000 × 36 = 72,000 checks — instant — versus the 5 cases you'd write by hand.

without it

You trust five hand-written examples, and the bug that appears only with duplicates or negatives shows up in the hidden tests.

when · why · how

when: At home, after your optimal solution passes the examples — especially for tricky index logic, greedy choices or math shortcuts.
why: Tiny random inputs keep the O(n²) brute force cheap, so thousands of comparisons run in well under a second.
how: Random rnd = new Random(42); build small arrays in a loop, call both versions, and print the first input where they disagree.

02 · plain english

The idea in 30 seconds

Interview problems aren't solved by flashes of genius. They're solved by a routine you run every time: understand → brute force → improve → code → test.

A correct slow answer is worth far more than a fast answer you can't finish. Start slow, then make it fast.

Practice is about patterns, not memorised code: after roughly 150 well-reviewed problems (a common rule of thumb, not a study), most new questions look like old friends.

picture this

When a production server goes down at 2 a.m., a good on-call engineer doesn't improvise — they open the runbook: read the alert, reproduce, find the cause, fix, verify. UMPIRE is your interview runbook: under pressure you just do the next step.

03 · remember

What you must know

UMPIRE: Understand (restate, ask, examples) → Match (which pattern?) → Plan (brute force, then better) → Implement → Review (dry run) → Evaluate (complexity, trade-offs).
Constraints are hints. n ≤ 20 allows 2ⁿ; n ≤ ~5,000 allows n² comfortably (10⁴ is borderline); n ≤ 10⁵–10⁶ needs O(n log n) or O(n). Read them before choosing an idea.
Brute force first, out loud. It proves you understand the problem, gives you a fallback, and is often the starting point the optimal answer improves.
Find the bottleneck: ask "which step repeats work?" then pick a data structure that makes that step fast (HashMap for lookups, sorting for order, a heap for the minimum…).
Dry run with a table: one row per iteration, one column per variable. It catches off-by-one and edge-case bugs before the interviewer does.
Edge-case checklist: empty, one element, two elements, all equal, negatives/zero, already sorted, duplicates, max values (overflow).
Talk while you think. Silence looks like being stuck; narration lets the interviewer help and gives you credit for reasoning.
Practice smart: time-box with the 20-minute rule, re-solve with spaced repetition (1 → 3 → 7 → 16 → 35 days, the same ladder as the recall cards), and keep a log of why you got stuck.

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

Dry run — the trace table

Fill one row per loop iteration. Try n = 1230 and notice what happens to the trailing zero.

loading simulation…

javajava.util.*

1class DryRun {2    /** Reverses the decimal digits of a non-negative int: 1230 -> 321. Trace it by hand first! */3    static int reverseDigits(int n) {4        int rev = 0;5        while (n > 0) {6            int digit = n % 10;      // last digit7            rev = rev * 10 + digit;  // append it to rev8            n /= 10;                 // drop it from n9        }10        return rev;11    }12}

sim

Brute force first: every pair

Each lit cell is one pair checked. The triangle grows like n²/2 — that's the bottleneck to remove.

loading simulation…

javajava.util.*

1class Solution {2    public int[] twoSum(int[] nums, int target) {3        for (int i = 0; i < nums.length; i++) {4            for (int j = i + 1; j < nums.length; j++) { // every pair once5                if ((long) nums[i] + nums[j] == target) return new int[] {i, j}; // long: no overflow6            }7        }8        return new int[] {}; // problem guarantees an answer9    }10}

sim

The upgrade: remember what you've seen

Same problem, one pass. A HashMap turns "search for the partner" into one O(1) lookup.

loading simulation…

javajava.util.*

1class Solution {2    public int[] twoSum(int[] nums, int target) {3        Map<Integer, Integer> seen = new HashMap<>(); // value -> index4        for (int i = 0; i < nums.length; i++) {5            int need = target - nums[i];6            Integer j = seen.get(need);7            if (j != null) return new int[] {j, i}; // partner was seen earlier8            seen.put(nums[i], i);9        }10        return new int[] {};11    }12}

05 · cost

Time & space, explained

Two Sum, three ways — the brute → better → optimal ladder
	Time	Extra space	why
Check every pair	O(n²)	O(1)	n(n−1)/2 pairs: for n = 10⁴ that's ~5·10⁷ checks — passes, but at 10⁵ it would be ~5·10⁹.
Sort indices + two pointers	O(n log n)	O(n)	Sorting dominates; the extra index array keeps the original positions.
One-pass HashMap	O(n) average	O(n)	One O(1) average lookup and insert per element; the map may hold all n values.

A 45-minute coding interview, budgeted
	Minutes	You produce	why
U — Understand	0–5	Restated problem, 2 examples, clarified inputs	Most wrong answers come from solving a slightly different problem.
M + P — Match & Plan	5–12	Brute force + its Big-O, then a better idea the interviewer agrees with	Agreeing on the plan before coding means no wasted typing.
I — Implement	12–30	Clean code with good names, narrated	With a plan, coding is translation — it should be the calm part.
R — Review	30–38	A dry run on an example + 2–3 edge cases	Finding your own bug scores better than the interviewer finding it.
E — Evaluate	38–45	Final time/space, trade-offs, follow-ups, your questions	Shows you understand why the solution works and what it costs.

06 · java

Raw vs Collections Framework

Brute force first, then the upgrade

javabrute force: two loopsjava.util.*

1class Solution {2    public int[] twoSum(int[] nums, int target) {3        for (int i = 0; i < nums.length; i++) {4            for (int j = i + 1; j < nums.length; j++) { // every pair once5                if ((long) nums[i] + nums[j] == target) return new int[] {i, j}; // long: no overflow6            }7        }8        return new int[] {}; // problem guarantees an answer9    }10}

javaHashMap: one passjava.util.*

1class Solution {2    public int[] twoSum(int[] nums, int target) {3        Map<Integer, Integer> seen = new HashMap<>(); // value -> index4        for (int i = 0; i < nums.length; i++) {5            int need = target - nums[i];6            Integer j = seen.get(need);7            if (j != null) return new int[] {j, i}; // partner was seen earlier8            seen.put(nums[i], i);9        }10        return new int[] {};11    }12}

The brute force asks "is there a partner?" by scanning. The HashMap answers the same question in O(1) average time.
Use Map<Integer, Integer> (boxed types) — collections can't hold int directly. get returns null when the key is missing, so store it in an Integer, not an int.
(long) a + b in the brute force is a safety habit: LeetCode's ±10⁹ limits just fit in int (2·10⁹ < 2³¹ − 1 ≈ 2.147·10⁹), but values closer to Integer.MAX_VALUE would wrap and could create a false match.

Dry runs: trace before you trust

javaa loop worth tracingjava.util.*

1class DryRun {2    /** Reverses the decimal digits of a non-negative int: 1230 -> 321. Trace it by hand first! */3    static int reverseDigits(int n) {4        int rev = 0;5        while (n > 0) {6            int digit = n % 10;      // last digit7            rev = rev * 10 + digit;  // append it to rev8            n /= 10;                 // drop it from n9        }10        return rev;11    }12}

Make a table with one column per variable and one row per iteration — exactly what the simulation above builds.
Dry-run on the interviewer's example and on an edge case (0, one digit, trailing zeros).
If you must debug on a computer, print the same table with System.out.println instead of guessing.

Edge cases, decided up front

javaguards, safe starts, long sumsjava.util.*

1class EdgeCases {2    /** {min, max} of the array. Decide up front what "empty" means — here: an exception. */3    static int[] minMax(int[] nums) {4        if (nums == null || nums.length == 0) throw new IllegalArgumentException("empty input");5        int min = nums[0], max = nums[0];      // start from a real element, never from 06        for (int x : nums) {7            min = Math.min(min, x);8            max = Math.max(max, x);9        }10        return new int[] {min, max};11    }12 13    /** Average rounded down; the sum is a long so 10^5 values near 2^31 can't overflow. */14    static int averageFloor(int[] nums) {15        if (nums.length == 0) return 0;         // documented choice for the empty case16        long sum = 0;17        for (int x : nums) sum += x;18        return (int) Math.floorDiv(sum, nums.length); // floorDiv rounds negatives down too19    }20}

Decide (and say) what empty input returns before coding — throw, return 0, or return an empty list.
Start min/max from a real element (nums[0]), never from 0 — all-negative arrays break that.
Math.floorDiv rounds toward −∞; / rounds toward 0. They differ for negatives.

Stress testing: let the brute force check your fast code

javarandom tests vs brute forcejava.util.*

1class StressTest {2    /** Compares a slow-but-obvious answer with a fast one on many random inputs. */3    static boolean agree(int rounds, long seed) {4        Random rnd = new Random(seed);5        for (int round = 0; round < rounds; round++) {6            int[] nums = new int[2 + rnd.nextInt(8)];       // small inputs: easy to debug7            for (int i = 0; i < nums.length; i++) nums[i] = rnd.nextInt(21) - 10;8            int target = nums[0] + nums[nums.length - 1]; // guarantee one answer exists9            int[] slow = new TwoSum.Brute().twoSum(nums, target);10            int[] fast = new TwoSum.OnePassHashMap().twoSum(nums, target);11            boolean fastValid = fast.length == 2 && fast[0] != fast[1]12                    && nums[fast[0]] + nums[fast[1]] == target;13            if (slow.length != 2 || !fastValid) {14                System.out.println("Mismatch on " + Arrays.toString(nums) + " target " + target);15                return false;                               // print the smallest failing case16            }17        }18        return true;19    }20}

In practice (not in the interview), compare your optimal answer with the brute force on thousands of small random inputs.
Use a fixed seed (new Random(42)) so a failure can be reproduced, and keep inputs tiny so the failing case is easy to read.

Java API you will actually use
call	does	cost
`map.get(key)`	Value for key, or null if absent	O(1) average
`map.put(key, value)`	Insert or overwrite	O(1) average
`map.containsKey(key)`	Is the key present?	O(1) average
`map.getOrDefault(key, 0)`	Value or a default — perfect for counting	O(1) average
`Arrays.toString(arr)`	Readable print of an array while debugging	O(n)
`String.valueOf(i)`	int → String (Fizz Buzz)	O(digits)
`new Random(seed)`	Repeatable random inputs for stress tests	O(1) per number
`Math.floorDiv(a, b) / Math.floorMod(a, b)`	Division and remainder that round toward −∞	O(1)

A guaranteed-correct first answer

→ Brute force (nested loops / try everything)

Easy to prove, gives a fallback and a baseline to improve.

"Have I seen X?" or "where did I see X?"

→ HashSet / HashMap

Turns a linear scan into an O(1) average lookup.

Running totals or range sums

→ Prefix sums

Reuse the previous answer instead of re-adding.

Confidence that your optimal code is right

→ Stress test against the brute force

Random small inputs find bugs you'd never think of.

07 · recognise

Spot the pattern

"Find two/k items that add up to / match something"

HashMap of what you've seen (or sort + two pointers)

Input is sorted

Binary search or two pointers

Contiguous subarray / substring with a condition

Sliding window or prefix sums

"Top k", "k-th largest", "closest k"

Heap (PriorityQueue)

"All combinations / permutations / subsets", n ≤ 20

Backtracking (exponential is allowed)

"Number of ways", "min/max cost", choices that repeat

Dynamic programming

Grid, network, dependencies, "connected"

Graph BFS/DFS, union-find, topological sort

n up to 10⁵ or 10⁶

You need O(n log n) or O(n) — nested loops will time out

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

Coding before you understand: the #1 reason for wrong answers. Restate the problem and run one example by hand first.
Skipping the brute force because it feels "too easy" — then freezing with nothing on the board.
Coding in silence. The interviewer can't give credit (or hints) for thoughts they can't hear.
Never testing your own code — saying "I think it works" instead of dry-running it.
Ignoring constraints: an O(n²) idea for n = 10⁵ is a wrong answer, not a slow one.
Memorising solutions instead of the reason they work — a small twist in the problem breaks memorised code.
Grinding one problem for hours. Past ~20 minutes with no progress, learning from a hint is faster than staring.
Integer overflow: int tops out near 2.1·10⁹, so products (10⁵ × 10⁵) and sums of many large values need long.

tricks

Clarifying questions to keep ready: input size? negatives? duplicates? sorted? empty input? return indices or values? one answer or all?
When stuck: solve a smaller case by hand, draw it, write the brute force, then ask "what repeated work can I remember?"
Say your complexity out loud with a reason: "O(n) because each element is pushed and popped once."
Name variables for meaning (need, seen, left, windowSum) — it makes narration and debugging easier.
Keep a mistake log: problem, what blocked you, the key insight in one line. Review the log weekly.
20-minute rule: no progress after 20 minutes → read one hint. Still stuck after ~10 more → read the solution, understand it, close it, and re-code it from scratch.
Spaced repetition: re-solve each problem from a blank page after 1, 3, 7, 16 and 35 days. If you can't, the timer resets.

09 · why & how

Questions you might be too shy to ask

I freeze when I see a new problem. What do I literally do first?

Read it twice, then restate it in your own words to the interviewer. Write one small example and solve it by hand. Freezing usually means "I don't know the clever answer yet" — the routine gives you a next step that never needs cleverness. Bas itna yaad rakho: there is always a next step.

What if I can't think of even a brute force?

Solve one tiny example by hand, slowly, and watch what your hand does. "I tried every pair" becomes two nested loops. "I tried every starting point" becomes one loop with an inner loop. Most brute forces are just "try every option and keep the best" — write that sentence first, then the loops.

Should I mention the brute force if I already know the optimal solution?

Yes, briefly — one or two sentences with its Big-O. It shows structured thinking and sets up why the optimal is better. Then say "we can do better" and move on. Don't code the brute force unless asked or unless you're stuck.

How can I "Match" a pattern if I don't know many patterns yet?

Right now you can't, and that's fine. Skip M, say the brute force, and ask "which step repeats work?" — that question alone finds most upgrades. Each chapter in this course adds patterns and their trigger words, so M gets easier every week.

Is "about 10⁸ steps per second" an exact rule?

No, it's a rough estimate for simple steps (an addition, a comparison, an array read). Use it to rule ideas out, not to predict exact timing. n = 10⁵ with O(n²) is 10¹⁰ steps — about 100× over budget, so it's out, no matter how fast the machine is.

In a dry-run table, do I write the values before or after each line runs?

After. The first row holds the starting values (before the loop). Then add one row per iteration, written after the loop body finishes. For reverseDigits(1230): start n = 1230, rev = 0; after the first iteration digit = 0, rev = 0, n = 123. Change a cell only when a Java line changes that variable.

Running Sum in place: why does the loop start at i = 1, not i = 0?

Each step reads the cell on its left: nums[i] += nums[i - 1]. At i = 0 that's nums[-1], which throws ArrayIndexOutOfBoundsException. And nums[0] is already its own running sum, so it needs no work.

Is looking at the solution cheating?

No — not when you're practising. Reading a solution after an honest 20–30 minute attempt is how you learn patterns. The rule: understand it, close it, re-code it from scratch, and re-solve it again days later.

I understood the solution, but I can't write it from a blank page. What now?

Very normal: reading code and writing code are different skills. Close the solution and write the steps as comments first (// for each number, // look up target - x). Then turn each comment into one or two Java lines. Can't do a step? Peek only at that step, close it again, and continue. Re-solve it after 1 and 3 days.

How many problems do I need to solve before interviews?

Quality beats count. There's no study behind any exact number; a common rule of thumb is roughly 150–250 problems spread across all patterns, each reviewed with spaced repetition. 500 problems solved once and forgotten prepare you less.

What do I say when I'm stuck in the interview?

Narrate: "I have an O(n²) idea; the slow part is searching for the partner. If I could look it up in O(1)…" Interviewers often nudge you when they can see where you are. Asking "can I think for a minute?" is perfectly fine too.

English is not my first language. Will that hurt me in the interview?

What counts is that your reasoning is clear, not fancy words or a perfect accent. Use short sentences: "I store each number in a map. Then I look up the partner." Practise saying your solution out loud at home, alone — it feels odd at first, then becomes easy.

What if I can't finish the code in time?

A clear plan plus partial, well-structured code still scores. Say what the remaining parts would do. That's another reason to agree on the plan before coding.

Why do interviewers care about edge cases so much?

Because real code breaks on them: empty lists, one item, duplicates, overflow. Testing them unprompted signals you'd write reliable production code.

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run. show patterns & complexity

#1480
Running Sum of 1d Array
EasyGoogleAmazonMicrosoftBloombergMeta
#412
Fizz Buzz
EasyNVIDIAAmazonBloombergMicrosoftGoogle+1

Also practise this here

Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.

#1
Two Sum
Easyin Hashing
The worked example for the whole routine: say the O(n²) brute force, spot the repeated search, then trade memory for time with a HashMap.

11 · revise

The whole chapter on one screen

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

what it is
A routine, not genius: Understand → Match → Plan → Implement → Review → Evaluate. Same steps every time, so you always know the next one.
use it when
Every coding round and every practice problem — and the moment you freeze. Next step is always: restate it, then solve one tiny example by hand.
template
Say it out loud: "Brute force is O(n²) because… The repeated work is… A HashMap makes that O(1), so O(n) time, O(n) space."
cost
Constraints pick the idea: n ≤ 20 → 2ⁿ · n ≤ ~5,000 → n² (10⁴ borderline) · n ≤ 10⁵–10⁶ → n log n or n. Budget ≈ 10⁸ simple steps per second.
trap
Coding before understanding. Most wrong answers solve a slightly different problem. Restate it and run one example by hand first.
trap
int stops at 2,147,483,647. Products like 10⁵ × 10⁵ or sums of many big values need long — cast before the operation.
pro tip
Dry run with a table (one row per iteration, one column per variable), then test: empty, one element, duplicates, negatives, max values.
pro tip
Practice: stuck 20 minutes → read one hint. Re-solve from a blank page after 1, 3, 7, 16 and 35 days.
pro tip
At home, stress test: compare your fast code with the brute force on thousands of tiny random inputs (fixed seed).

12 · recall

Flip, remember, repeat

card 1 / 13

recall

You read a new problem and your mind goes blank. What exactly do you do in the first two minutes?

tap or Space to flip ↻

Question 1: You read a new problem and your mind goes blank. What exactly do you do in the first two minutes?

13 · check yourself

Quick quiz

What does the "M" in UMPIRE stand for?
Constraints say n ≤ 10⁵. Which idea is too slow?
You've been stuck on a practice problem for 20 minutes with zero progress. Best move?
In one-pass Two Sum, why check the map *before* inserting nums[i]?
Which input is NOT on the standard edge-case checklist?
Why say the brute force out loud even if you know a better solution?

0/0 correct · 6 left

14 · learn more