Data Structures & Algorithms — All-Inclusive Study Guide

📝 Quiz · 🃏 Flashcards

Target: Senior software engineer interview refresher (Java/backend focus, 5+ yrs experience) Language: Java 21+ examples throughout, idiomatic java.util usage Format: Concept explanation → runnable code → gotchas → interviewer-style Q&A per section
This is the deep-dive companion to ../INTERVIEW_PREP.md §16 (Algorithms & Data Structures). Where that section lists 10 warm-up prompts, this guide rebuilds intuition from first principles — complexity analysis, every core data structure and algorithm, the pattern-matching toolkit that makes LeetCode-style problems tractable, and the meta-skills for performing on the whiteboard.
How to use this guide:
Full refresher: Walk §1 → §50 in order. Each section stands alone but builds on prior ones (Part 1 complexity language recurs everywhere; Part 6 patterns reference Parts 2–5 structures).
Targeted review: Use the coverage matrix to jump to the section answering a specific INTERVIEW_PREP.md §16 question.
Interview-eve cram: §49 rapid-fire + §47 complexity cheat-sheet + §48 decision tables. One hour will get you 80% of the surface area.
Practice set: §51 Practice Problems by Pattern — ~50 classic problems grouped by the patterns taught in Part 6.

Interview-Question Coverage Matrix

Maps each INTERVIEW_PREP.md §16 question (1–10) to the section(s) in this guide that answer it.

Q#	Topic	Section
1	Reverse a linked list (iterative + recursive)	§8
2	Two-sum (hash map, O(n))	§11, §30
3	Valid parentheses (stack)	§9
4	Merge two sorted lists / arrays	§8, §36
5	Find duplicates in an array	§11, §34
6	LRU cache (`LinkedHashMap` or DLL + map)	§11, §40
7	Top K frequent elements (heap or bucket sort)	§15, §35
8	Top-N from event stream, last hour (sliding window + heap)	§31, §35
9	Binary search on rotated sorted array	§20
10	BFS vs DFS — when pick each	§21

Part 1 — Complexity Analysis

The whole point of DSA study is choosing structures and algorithms that scale. Complexity analysis is the language you use to reason about scaling — and to communicate with your interviewer. Every answer you give on the whiteboard should end with "…and the complexity is O(X) time, O(Y) space." If you don't state complexity, you're not done.

1. Big-O, Big-Θ, Big-Ω

The precise definitions

Given functions f(n) (your algorithm's cost) and g(n) (a reference function like n or n²):

Big-O (upper bound): f(n) = O(g(n)) iff there exist constants c > 0 and n₀ such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀. "Eventually, f grows no faster than g up to a constant."
Big-Ω (lower bound): f(n) = Ω(g(n)) iff there exist constants c > 0 and n₀ such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n₀. "f grows at least as fast as g."
Big-Θ (tight bound): f(n) = Θ(g(n)) iff f(n) = O(g(n)) and f(n) = Ω(g(n)). "f and g grow at the same rate."

Concretely: 3n² + 5n + 100 is O(n²), Ω(n²), and Θ(n²). It is also O(n³) (a looser upper bound — still technically correct). It is not Θ(n³).

How interviewers actually use "Big-O"

In interviews, "Big-O" is used loosely to mean "tight asymptotic bound" — what a pedant would call Big-Θ. If they ask "what's the Big-O of quicksort?", the expected answer is O(n log n) average / O(n²) worst case, not an arbitrary loose upper bound like O(2ⁿ).

Rule of thumb: state the tight bound for the worst case (or best/average if they ask specifically). Be explicit about which case you're stating.

Constants, lower-order terms, and bases

Big-O discards constants and lower-order terms:

O(3n) = O(n)
O(n² + n) = O(n²)
O(100) = O(1)

And bases of logarithms are absorbed into the constant:

O(log₂ n) = O(log₁₀ n) = O(log n)

This is why we write "O(log n)" without specifying the base — change of base is just a constant factor (log_a(n) = log_b(n) / log_b(a)).

But: constants matter in practice. O(n) with a constant of 1000 may be slower than O(n log n) with a constant of 1 for n up to 10⁶. Interviewers rarely quiz on this, but it explains why, e.g., Arrays.sort on small arrays actually falls back to insertion sort.

Q&A

Q: What's the difference between O(n) and Θ(n)? O(n) says the algorithm's cost grows at most linearly. Θ(n) says it grows exactly linearly. Arrays.binarySearch on a sorted array is O(log n) — and also Θ(log n), because it always does at least log n comparisons (excluding lucky early exits).
Q: Why do we drop constants in Big-O? Because constants are implementation-dependent (CPU, cache, branch prediction, language, JIT) and don't affect how the algorithm scales. f(n) = 2n and g(n) = 100n are both O(n) — and doubling n doubles the work for both.
Q: If I say my algorithm is "O(n²)," am I saying it's always slow? No — you're stating an upper bound on growth. For small n, an O(n²) algorithm can easily beat an O(n log n) one because of smaller constants or better cache behavior. Hence Java's Arrays.sort(int[]) uses insertion sort (O(n²)) for arrays shorter than ~47 elements.

2. Time complexity in practice

The class ladder

From fastest to slowest. Memorize this order — it anchors all your analysis.

Class	Name	Example
O(1)	Constant	Hash map lookup, array index
O(log n)	Logarithmic	Binary search, balanced BST op, heap op
O(n)	Linear	Single pass over array, DFS of a tree
O(n log n)	Linearithmic	Merge sort, heap sort, `Arrays.sort`
O(n²)	Quadratic	Nested loop over array, naive two-sum
O(n³)	Cubic	Triple nested loop, naive matrix multiply
O(2ⁿ)	Exponential	Naive recursive Fibonacci, subset enumeration
O(n!)	Factorial	Permutation enumeration, brute-force TSP

Recognizing each class from code

O(1) — Constant. No loops over input, or loops bounded by a fixed constant:

java

int first = arr[0];                // O(1)
for (int i = 0; i < 10; i++) ...   // O(1) — 10 is a constant

O(log n) — Logarithmic. Each iteration halves (or fractions) the remaining problem:

java

while (n > 0) { n /= 2; ... }      // O(log n)
// Binary search, heap sift, balanced BST walk

O(n) — Linear. Every element touched a constant number of times:

java

for (int x : arr) ...              // O(n)

O(n log n) — Linearithmic. Typical of divide-and-conquer sort / merge patterns. Recurrence T(n) = 2T(n/2) + O(n) solves to O(n log n) (Master Theorem, §5).

O(n²) — Quadratic. Nested loops both bounded by n:

java

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) ...     // O(n²)

Also: for (int j = i+1; j < n; j++) — the inner loop shrinks, but total iterations are n(n-1)/2, still O(n²).

O(2ⁿ) — Exponential. Recursion that branches binary without memoization:

java

int fib(int n) {
    if (n < 2) return n;
    return fib(n-1) + fib(n-2);    // T(n) = T(n-1) + T(n-2) ≈ O(2ⁿ)
}

O(n!) — Factorial. Generating all permutations, TSP brute force.

Reading nested / sequential work

Sequential steps: O(a) + O(b) = O(max(a, b)). Two independent linear passes is still O(n).
Nested steps: O(a) × O(b) = O(a·b). Outer loop n times, inner loop m times = O(n·m).
Different variables: Be precise when inputs have different sizes — e.g., searching an n-length string in an m-length document is O(n·m), not O(n²).

Complexity of common Java operations

Operation	Structure	Complexity
`list.get(i)`	`ArrayList`	O(1)
`list.get(i)`	`LinkedList`	O(n)
`list.add(x)`	`ArrayList`	O(1) amortized
`list.add(0, x)` (prepend)	`ArrayList`	O(n)
`list.add(0, x)`	`LinkedList`	O(1)
`map.get(k)`	`HashMap`	O(1) average, O(log n) worst (tree-ified bucket)
`map.get(k)`	`TreeMap`	O(log n)
`set.contains(x)`	`HashSet`	O(1) average
`queue.poll()`	`PriorityQueue`	O(log n)
`queue.offer(x)`	`PriorityQueue`	O(log n)
`queue.peek()`	`PriorityQueue`	O(1)
`deque.offer/poll`	`ArrayDeque`	O(1) amortized

Q&A

Q: Why is LinkedList.get(i) O(n)? Because there's no index arithmetic — you traverse i next-pointers from the head (or n-i from tail, since Java's LinkedList is doubly linked). ArrayList.get(i) is O(1) because it's a direct array offset.
Q: I wrote for (int i = 0; i < n; i++) for (int j = i+1; j < n; j++). What's the complexity? Still O(n²). Total iterations are n(n-1)/2, which is Θ(n²) — dropping the constant 1/2 and the lower-order term.
Q: What's the complexity of Arrays.sort(int[]) vs Arrays.sort(Integer[])? Both are O(n log n) asymptotically. But the primitive variant uses Dual-Pivot Quicksort (fast, in-place, not stable); the reference variant uses Timsort (stable, slightly more overhead). That's why you pick int[] when you don't need stability.
Q: Is O(log n) always faster than O(n)? Asymptotically yes, for sufficiently large n. For small n, constants matter — O(n) with a tight constant can beat O(log n) with overhead. But in interviews, "asymptotically faster" is what they want to hear.

3. Space complexity

Every algorithm has two complexities: time (operations) and space (memory). Space is how much extra memory your algorithm uses beyond the input.

Auxiliary vs total space

Auxiliary space: Extra memory your algorithm allocates. This is what interviewers usually mean by "space complexity."
Total space: Auxiliary + input. Almost always the input is O(n), so total space is O(n) + auxiliary.

When you say "O(1) space," you mean O(1) auxiliary — the input doesn't count.

Recursion stack counts

A recursive function uses stack memory proportional to its maximum recursion depth.

java

int sum(int[] arr, int i) {
    if (i == arr.length) return 0;
    return arr[i] + sum(arr, i + 1);  // depth n → O(n) stack space
}

Even though you wrote no explicit data structure, the call stack is O(n). To write this in O(1) space, use iteration.

Tail recursion note: Java does not optimize tail calls. A tail-recursive function in Java still uses O(depth) stack. Languages like Scala or Scheme can eliminate it — Java cannot.

In-place algorithms

An in-place algorithm modifies the input and uses O(1) extra space. Classic examples:

Reversing an array with two swapping pointers — O(1) space.
In-place quicksort — O(log n) space (recursion stack).
In-place merge sort is hard; standard merge sort is O(n) space.

Common space-complexity traps

Hidden allocations in loops:
java
```
for (int i = 0; i < n; i++) {
    List<Integer> tmp = new ArrayList<>();  // allocates each iteration
    ...
}
```
1
2
3
4
If tmp grows to n, total allocated memory is O(n²) even if peak live memory is O(n). For space complexity (live memory at any point), this is O(n); but GC pressure matters in practice.
Slicing strings: "abcdef".substring(1, 4) in Java allocates a new String. Inside a loop over an n-length string, that's O(n²) total allocation — even though each call looks O(1).
Stream chains: list.stream().map(...).collect(toList()) allocates intermediate objects. Usually O(n) space — same as the output.

Q&A

Q: What's the space complexity of binary search? Iterative: O(1). Recursive: O(log n) because of the call stack.
Q: Merge sort is O(n log n) time. What about space? O(n) auxiliary — you need a temporary array for the merge step. The log n recursion depth contributes O(log n), dominated by the O(n) merge buffer.
Q: Your solution builds a hash map of the input. Is that O(n) space? Yes. Even though you're "just putting pointers into a map," the map itself holds n entries. HashMap<Integer, Integer> with n entries is O(n) auxiliary space.

4. Amortized analysis

Amortized analysis answers: what's the average cost per operation over a sequence of operations, in the worst case?

It's distinct from average-case analysis (which averages over random inputs). Amortized is a worst-case guarantee averaged over operations.

The `ArrayList.add` example

ArrayList stores elements in a backing array. When you call add(x) and the array is full, it:

Allocates a new array (typically 1.5× or 2× the current size).
Copies all existing elements — O(n).
Inserts the new element — O(1).

So add(x) is sometimes O(n). But amortized across n calls starting from empty, the total cost is O(n), so the average cost per call is O(1).

Why amortized O(1) and not O(log n) or similar? The key is doubling. After each resize, you've at least doubled capacity. So over n insertions, the total work for resizes is 1 + 2 + 4 + ... + n ≤ 2n, which is O(n). Dividing by n insertions gives O(1) amortized.

If you resized to capacity + constant instead of doubling, each insertion would trigger a resize, total work would be O(n²), and amortized cost per op would be O(n). Doubling is what makes dynamic arrays efficient.

`HashMap.put` amortized cost

Same argument applies to hash table rehashing: when load factor exceeds threshold (default 0.75 in Java), the map doubles its bucket array and rehashes every entry. Per-insert cost is O(1) amortized.

The three techniques (brief)

You don't need to memorize these for interviews, but knowing they exist helps:

Aggregate method: Compute total cost of n ops, divide by n. (ArrayList example above.)
Accounting method: Charge each op a fixed "amortized cost" and use the surplus to pay for expensive ops.
Potential method: Formal energy-function bookkeeping. Math-heavy; rarely seen in interviews.

What "amortized O(1)" doesn't guarantee

Worst-case single op can still be O(n). If your app cannot tolerate an occasional O(n) pause (hard-real-time trading system, low-latency game loop), amortized O(1) is not good enough — use a structure with worst-case O(1) guarantees (e.g., a pre-sized array).

Q&A

Q: Why is ArrayList.add amortized O(1) and not O(n)? Because each resize doubles capacity, so total copying work over n inserts is O(n). Divide by n ops → O(1) per op on average.
Q: Is ArrayList.add(0, x) amortized O(1)? No — it shifts all elements right by one. That's O(n) every time, so it's O(n) worst case and O(n) amortized. Insert at the end (add(x)) is the amortized-constant one.
Q: Why does HashMap have load factor 0.75 by default? Tradeoff between space and time. Lower load factor → fewer collisions → faster lookups but more memory. Higher load factor → more collisions → slower lookups but less memory. 0.75 is the empirical sweet spot.

5. Analyzing recursion

The recurrence relation

A recursive function's complexity is captured by a recurrence relation: an equation expressing T(n) in terms of T applied to smaller inputs.

Example: binary search.

java

int search(int[] arr, int target, int lo, int hi) {
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target) return search(arr, target, mid + 1, hi);
    return search(arr, target, lo, mid - 1);
}

One recursive call on half the input, plus O(1) work:

T(n) = T(n/2) + O(1)
T(n) = O(log n)

Merge sort:

T(n) = 2·T(n/2) + O(n)       ; two halves + O(n) merge
T(n) = O(n log n)

Naive Fibonacci:

T(n) = T(n-1) + T(n-2) + O(1)
T(n) = O(φⁿ) ≈ O(1.618ⁿ) ≈ O(2ⁿ)

Master Theorem (informal)

For recurrences of the form T(n) = a·T(n/b) + f(n) where a ≥ 1, b > 1:

Compare f(n) to n^(log_b a):

Case	Condition	Solution
1	`f(n) = O(n^(log_b a - ε))` for some ε > 0	`T(n) = Θ(n^(log_b a))`
2	`f(n) = Θ(n^(log_b a))`	`T(n) = Θ(n^(log_b a) · log n)`
3	`f(n) = Ω(n^(log_b a + ε))` and regularity	`T(n) = Θ(f(n))`

Practical use (the only cases you'll see in an interview):

Merge sort: a=2, b=2, f(n)=n. n^(log₂ 2) = n^1 = n. Case 2 → T(n) = Θ(n log n). ✓
Binary search: a=1, b=2, f(n)=1. n^(log₂ 1) = n^0 = 1. Case 2 → T(n) = Θ(log n). ✓
Karatsuba multiplication: a=3, b=2, f(n)=n. n^(log₂ 3) ≈ n^1.585. Case 1 → T(n) = Θ(n^1.585).

Tree-recursion intuition (the shortcut)

You rarely need to invoke the Master Theorem explicitly. For most interview problems, use recursion tree intuition:

How many recursive calls at each level?
How much work per call at each level?
How many levels?

Multiply: (calls per level) × (work per call) × (levels).

Merge sort: at each level, total work is O(n) (all the merges combined). There are O(log n) levels. Total: O(n log n).

Binary tree traversal: each node is visited once, O(1) work per node. Total: O(n).

Naive Fibonacci: the recursion tree nearly doubles at each level; depth is n; roughly 2ⁿ nodes total. O(2ⁿ).

Memoization changes the game

java

int fib(int n, int[] memo) {
    if (n < 2) return n;
    if (memo[n] != 0) return memo[n];
    return memo[n] = fib(n-1, memo) + fib(n-2, memo);
}

Each fib(k) is computed exactly once and cached. O(n) time, O(n) space. This is the bridge from recursion to dynamic programming (§27).

Q&A

Q: What's the complexity of this function?

java

void f(int n) {
    if (n <= 0) return;
    f(n / 2);
    f(n / 2);
    for (int i = 0; i < n; i++) { ... }
}

Recurrence: T(n) = 2·T(n/2) + O(n). By Master Theorem case 2, T(n) = O(n log n).

Q: Naive Fibonacci is O(2ⁿ). With memoization it's O(n). Why such a huge gap? Without memo, the recursion tree has exponentially many nodes — the same subproblem fib(k) is computed over and over. With memo, each fib(k) is computed exactly once, and subsequent calls are O(1) cache hits. n subproblems × O(1) each = O(n).
Q: Recursion uses stack. When does the depth matter? For n = 10⁴ or more in Java, you risk StackOverflowError (default stack ~512KB → ~10⁴ frames depending on frame size). For interview-scale n (≤ 10⁵), use iteration or explicit stack when depth is guaranteed large (e.g., DFS of a skewed tree).

Part 2 — Linear Data Structures

The structures in this part are the daily-driver tools. You will use at least two of them in nearly every interview problem — often arrays and hash tables in tandem, or stacks/queues as traversal scaffolding for Part 3 structures.

6. Arrays

Fixed arrays vs dynamic arrays

Fixed array (int[], Object[]). A contiguous block of memory, size fixed at allocation. Element access by offset: arr[i] compiles to base + i·sizeof(elem), a single memory op — O(1).

Dynamic array (ArrayList<E>). A wrapper over a fixed backing array that resizes when full. API appears unbounded, but internally it's arrays + copies.

Memory layout of int[10]: 10 ints in consecutive bytes. Cache-friendly — the CPU prefetches adjacent elements, so iterating is extremely fast. This is why int[] often beats ArrayList<Integer> by 3–5× in tight loops (plus avoids boxing).

Operations and complexity

Operation	Fixed `int[]`	`ArrayList<E>`
Access `arr[i]` / `list.get(i)`	O(1)	O(1)
Write `arr[i] = x` / `list.set(i, x)`	O(1)	O(1)
Append `list.add(x)`	n/a (fixed)	O(1) amortized
Insert at index `list.add(i, x)`	n/a	O(n) — shifts elements
Remove at index	n/a	O(n)
Search (unsorted)	O(n)	O(n)
Search (sorted)	O(log n) via `Arrays.binarySearch`	O(log n) via `Collections.binarySearch`
Length	O(1) (`arr.length`)	O(1) (`list.size()`)

Java specifics

java

// Primitive arrays
int[] arr = new int[10];           // zero-initialized
int[] arr2 = {1, 2, 3};            // literal init
int len = arr.length;              // field, not method

// Dynamic array
List<Integer> list = new ArrayList<>();
list.add(42);                      // append
list.add(0, 99);                   // insert at front (O(n))
Integer x = list.get(0);           // access (autoboxed)
int size = list.size();            // method, not field

// Array → List (view, fixed-size)
List<Integer> view = Arrays.asList(1, 2, 3);
view.add(4);                       // UnsupportedOperationException!

// Array → modifiable List
List<Integer> mut = new ArrayList<>(Arrays.asList(1, 2, 3));

// List → array
Integer[] out = list.toArray(new Integer[0]);
int[]     raw = list.stream().mapToInt(Integer::intValue).toArray();

Two-pointer & sliding-window scaffolding

Most array-based interview problems reduce to one of:

Two pointers from opposite ends (see §30)
Sliding window (see §31)
Prefix sums (see §38)
Sort + scan (canonical for interval and pairing problems)

Common pitfalls

Off-by-one on loop bounds. for (int i = 0; i <= arr.length; i++) — one past the end, ArrayIndexOutOfBoundsException. Always < arr.length.
Modifying while iterating. list.remove(i) during for (int i = 0; i < list.size(); i++) shifts the tail and skips the next element. Use Iterator.remove() or iterate backward.
Integer overflow in midpoint. int mid = (lo + hi) / 2 overflows if lo + hi > Integer.MAX_VALUE. Prefer int mid = lo + (hi - lo) / 2.
Boxing cost. List<Integer> boxes every int. In hot loops, use int[].
Confusing .length (array) with .size() (List) with .length() (String). Java's API inconsistency trips everyone.

Connect to experience

In Kafka consumers, batched ConsumerRecords are backed by iterables over contiguous storage — accessing by index is O(1), but avoid List.copyOf(records) in hot paths because that's an O(n) allocation you don't need.

Q&A

Q: Why is ArrayList usually preferred over LinkedList in Java even for frequent insertions? Cache locality. Even though LinkedList.add(i, x) has better theoretical complexity, the actual wall-clock performance of ArrayList dominates until you're inserting in the middle of very large lists (and even then, a different structure like a gap buffer usually wins). "CPU cache" beats "Big-O" for most realistic sizes.

Q: How would you reverse an array in place? Two pointers swapping toward the middle. O(n) time, O(1) space.

java

void reverse(int[] a) {
    int i = 0, j = a.length - 1;
    while (i < j) { int t = a[i]; a[i++] = a[j]; a[j--] = t; }
}

Q: What does Arrays.asList(1, 2, 3) return, and what's the gotcha? A fixed-size List backed by the given array. add and remove throw UnsupportedOperationException. Also: Arrays.asList(new int[]{1, 2, 3}) returns List<int[]> of size 1, not List<Integer> of size 3 — autoboxing doesn't descend into primitive arrays.

7. Strings

Java String internals

String is immutable. Every "modification" returns a new String. Internally, a String holds a char[] (or byte[] in compact-string mode from Java 9+) plus a cached hashCode.

Immutability consequences:

Safe to share across threads without synchronization.
Can be interned (see below).

String concatenation in a loop is expensive:

java

String s = "";
for (int i = 0; i < n; i++) s += i;       // O(n²) — creates n new Strings

Use StringBuilder:

java

StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) sb.append(i); // O(n)
String s = sb.toString();

String pool & `intern()`

String literals ("hello") are interned at class-load time — a single canonical instance lives in the string pool. new String("hello") creates a new object whose contents equal the interned copy.

java

String a = "hi";
String b = "hi";
String c = new String("hi");

a == b;          // true  — same pooled instance
a == c;          // false — different objects
a.equals(c);     // true  — logical equality
c.intern() == a; // true  — intern returns the pooled copy

Always use .equals() to compare string contents. == works by accident for interned strings and fails for dynamically-built ones.

`StringBuilder` vs `StringBuffer`

StringBuilder: not thread-safe, fast. Use this by default.
StringBuffer: thread-safe (every method synchronized), slow. Legacy — rarely needed.

`char[]` for in-place algorithms

Converting to char[] lets you mutate in place:

java

char[] chars = s.toCharArray();
chars[0] = 'X';
String mutated = new String(chars);

Useful for O(1)-space palindrome check, reverse-string-in-place, etc.

Substrings — watch the cost

s.substring(i, j) in modern Java (9+) copies the char[] range — O(j - i) time and space. In Java 6 and earlier, it shared the backing array (cheap but leaky). Post-Java-7, substring always copies.

Implication: for (int i = 0; i < n; i++) s.substring(i, i+1) is O(n²) allocation.

Common string interview problems

Problem	Technique	Complexity
Reverse a string	Two pointers on `char[]`	O(n) time, O(1) space
Check palindrome	Two pointers from ends	O(n), O(1)
Anagram check	Sort both strings, or count chars	O(n log n) sort / O(n) counting
Longest substring without repeating chars	Sliding window + set	O(n), O(k)
Valid anagram via counts	`int[26]` for lowercase	O(n), O(1)
String-to-int (`atoi`)	Linear scan + overflow check	O(n)
Substring search	KMP, Rabin-Karp, or built-in `indexOf`	O(n + m) / O(n) expected

Character frequency counting

For lowercase-ASCII-only, use a size-26 int array — faster and tighter than a HashMap<Character, Integer>:

java

int[] freq = new int[26];
for (char c : s.toCharArray()) freq[c - 'a']++;

For full Unicode, use Map<Character, Integer> or Map<Integer, Integer> (code points).

Q&A

Q: Why are Java strings immutable? Hash code caching (so String works as a HashMap key without recomputation), security (paths/URLs can't be mutated after validation), thread-safety, and the string pool optimization. The cost is an allocation on every modification.
Q: What's the complexity of s1.equals(s2) in the worst case? O(min(|s1|, |s2|)) — character-by-character comparison. The "equal length check" is O(1); the actual compare is linear.
Q: How do you check if two strings are anagrams in O(n) time? Count character frequencies in a size-26 array (assuming lowercase ASCII). Increment for s1, decrement for s2. At the end, all counts must be zero. O(n) time, O(1) space.

8. Linked lists

Structure & variants

A linked list stores elements in nodes, each holding a value and pointer(s) to neighbor(s). No contiguous memory, no random access.

Singly linked: node → next. Cheap, forward-only traversal.
Doubly linked: prev ← node → next. Enables O(1) deletion given a node reference; doubles memory per node.
Circular: tail's next points to head. Useful for round-robin.

Java's java.util.LinkedList is doubly linked.

Why (and when) you'd ever use one

Linked lists are rarely the right answer in production Java. ArrayList wins on cache locality for almost all workloads. Linked lists win when:

You truly need O(1) insert/delete given a node reference (not given an index — finding by index is still O(n)).
You're implementing an LRU cache, doubly-linked list + hash map (see §11).
You're writing low-level systems code where cache effects are tuned differently.

In interviews, linked lists are a pointer-manipulation exercise. The problems test whether you can handle head/tail/null edge cases cleanly.

The basic node

java

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

Reverse a linked list

This is §16 Q1 — must know both forms.

Iterative — O(n) time, O(1) space:

java

ListNode reverse(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;   // save before we overwrite
        curr.next = prev;             // reverse the pointer
        prev = curr;                  // advance prev
        curr = next;                  // advance curr
    }
    return prev;                      // new head
}

Recursive — O(n) time, O(n) space (call stack):

java

ListNode reverse(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = reverse(head.next);
    head.next.next = head;            // make the next node point back to me
    head.next = null;                 // sever my forward pointer
    return newHead;
}

The recursive version is elegant but has a subtlety: on the way back up, head.next is still the original next node (which now has no forward pointer of its own), and we use that to set up the reverse link.

Cycle detection — Floyd's tortoise-and-hare

Two pointers, one moves 1 step, the other moves 2. If there's a cycle, they eventually meet. If the fast one reaches null, no cycle.

java

boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

O(n) time, O(1) space. The alternative (hash set of visited nodes) is O(n) space.

Finding the cycle start is a follow-up — after detection, reset one pointer to head and advance both one step at a time; they meet at the cycle start. (Interview trivia: derives from the math 2·(L+x) = L + x + n·C.)

Merge two sorted lists

§16 Q4. Classic two-pointer merge:

java

ListNode merge(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0), tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }
        else                { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = (a != null) ? a : b;   // attach remaining tail
    return dummy.next;
}

Dummy node trick: eliminates the special case for "am I setting the head, or appending?" — you always append. Crucial for clean linked-list code.

Common linked-list patterns

Problem	Technique
Reverse list	Iterative pointer manipulation
Detect cycle	Fast/slow (Floyd)
Middle of list	Fast/slow (slow is middle when fast reaches end)
Nth from end	Two pointers, one n ahead
Merge sorted	Dummy + two pointers
Remove duplicates (sorted)	Single pass
Reverse in groups of k	Iterative reverse + reconnect
Palindrome list	Find middle → reverse second half → compare

Q&A

Q: Reverse a linked list iteratively. Walk through state. Three pointers: prev=null, curr=head, next. Loop: save next = curr.next, flip curr.next = prev, advance prev = curr, curr = next. When curr == null, prev is the new head.
Q: How do you find the middle of a linked list in one pass? Fast/slow pointers. Slow moves 1, fast moves 2. When fast reaches end, slow is at middle. For even length, slow lands on the second-middle — adjust if the problem wants the first.
Q: When would you actually use LinkedList over ArrayList in real code? Almost never for random access or iteration. Only for queue-like usage at the head (LinkedList implements Deque) — though ArrayDeque is usually faster there too. Honestly: rarely.

9. Stacks

The LIFO abstraction

A stack supports push, pop, and peek, all O(1). Last in, first out. Think: function call stack, browser back button, undo history.

Java implementations

java

// Preferred — ArrayDeque used as a stack
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);                      // equivalent to addFirst
stack.push(2);
int top = stack.peek();             // 2, doesn't remove
int popped = stack.pop();           // 2, removes

// DO NOT use: java.util.Stack (legacy, synchronized, extends Vector — slow)

Why ArrayDeque over Stack:

Stack extends Vector — synchronized on every op (overhead) and exposes confusing Vector methods.
ArrayDeque is faster, has a cleaner API, and is what the JDK docs recommend.

The call-stack analogy

Every recursive function is implicitly using a stack — the JVM's call stack. Any recursive algorithm can be rewritten iteratively with an explicit stack. You'd do this to:

Avoid StackOverflowError on deep recursion.
Have more control over traversal state.

Example — iterative DFS:

java

void dfs(TreeNode root) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    if (root != null) stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        visit(node);
        if (node.right != null) stack.push(node.right);  // right first
        if (node.left != null)  stack.push(node.left);   // left last → popped first
    }
}

Classic stack interview problems

Valid parentheses (§16 Q3). Push opens, pop-and-match on close.

java

boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
    for (char c : s.toCharArray()) {
        if (pairs.containsValue(c)) stack.push(c);
        else if (pairs.containsKey(c)) {
            if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;
        }
    }
    return stack.isEmpty();
}

Next greater element. Monotonic stack — see §37.

Evaluate postfix (RPN). Push operands; on operator, pop two, apply, push result.

Min stack (O(1) min). Two stacks: one for values, one for running minimums.

Iterative tree traversal. DFS with an explicit stack; in-order traversal is the classic version.

Q&A

Q: Why prefer ArrayDeque over java.util.Stack in modern Java?Stack is synchronized (performance cost) and extends Vector (exposes get(index), breaking the LIFO abstraction). ArrayDeque is unsynchronized, faster, and a pure deque/stack API.
Q: When would you convert recursion to an explicit stack? When recursion depth risks StackOverflowError (very deep or skewed trees, long linked lists), when you need to pause/resume traversal, or when the JVM's stack frame is too expensive (rare).
Q: Valid parentheses — what's the complexity and why is a stack the right tool? O(n) time, O(n) space. A stack naturally models "most-recently-opened bracket must be closed next" — exactly LIFO.

10. Queues & deques

The FIFO abstraction

A queue supports offer (add to back), poll (remove from front), peek. FIFO — first in, first out. Think: printer queue, request queue, BFS frontier.

A deque (double-ended queue) supports add/remove at both ends — the superset of both stacks and queues.

Java implementations

Class	Role	Thread-safe	Notes
`ArrayDeque<E>`	Deque (preferred)	No	Array-backed, fast, default choice
`LinkedList<E>`	Deque + List	No	Doubly linked, worse cache behavior
`PriorityQueue<E>`	Priority queue (not FIFO!)	No	Heap, O(log n) offer/poll — see §15
`ArrayBlockingQueue<E>`	Bounded blocking queue	Yes	Producer-consumer scenarios
`LinkedBlockingQueue<E>`	Blocking queue	Yes	Optionally bounded
`ConcurrentLinkedQueue<E>`	Non-blocking queue	Yes	Lock-free via CAS

For interview problems, use ArrayDeque. For concurrency questions, reference BlockingQueue.

Basic usage

java

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);           // add to back
queue.offer(2);
int front = queue.peek(); // 1
int removed = queue.poll(); // 1

// Deque — both ends
queue.offerFirst(0);      // prepend
queue.offerLast(3);       // append
queue.pollFirst();        // remove front
queue.pollLast();         // remove back

Capacity gotcha: ArrayDeque is unbounded, but it rejects nulls (throws NullPointerException). Use this as a sentinel that you didn't accidentally poll from an empty queue — but don't try to store null in one.

The BFS frontier

The classic queue use case (see §21 for full coverage):

java

void bfs(TreeNode root) {
    Deque<TreeNode> q = new ArrayDeque<>();
    if (root != null) q.offer(root);
    while (!q.isEmpty()) {
        TreeNode node = q.poll();
        visit(node);
        if (node.left != null)  q.offer(node.left);
        if (node.right != null) q.offer(node.right);
    }
}

Circular buffers (ring buffers)

A fixed-size array + two indices (head, tail) that wrap around with modulo arithmetic. Operations are O(1). Used for:

Bounded event buffers (logging, telemetry).
Audio/video pipeline buffers.
Producer-consumer with known max backlog.

Java doesn't have a built-in circular buffer for simple types, but ArrayDeque is implemented as one internally.

Monotonic queues

A deque whose contents are kept in monotonic (always-increasing or always-decreasing) order by popping from the back before inserting. Used for sliding window maximum/minimum (§37). One of the more elegant interview patterns.

Connect to experience

Kafka consumers are essentially distributed queues with at-least-once semantics. IBM MQ queues are broker-managed FIFO (with priority and persistence). The in-memory abstractions here scale down the same mental model — offer at the tail, poll from the head.

Q&A

Q: What's the difference between ArrayDeque and LinkedList as a Queue? Both implement Deque. ArrayDeque is array-backed (cache-friendly, fast), LinkedList is node-based (extra memory, worse locality). Prefer ArrayDeque unless you need LinkedList's List API.
Q: Why does ArrayDeque.offer(null) throw NPE? Because null is reserved as the "queue is empty" sentinel returned by poll() / peek(). Allowing null elements would make it impossible to distinguish "empty" from "null at head."
Q: How does a circular buffer achieve O(1) enqueue/dequeue without shifting elements? By maintaining head and tail indices and wrapping them with modulo capacity. Elements never move; only the indices advance. Fixed size means no rescaling cost.

11. Hash tables

The single most important data structure for interview problems. Hash tables make "lookup by key in O(1)" possible, which is the hinge on which countless problems turn.

What a hash table is

An array of buckets indexed by hash(key) % capacity. Each bucket holds the entries whose keys hash to that index. Key operations:

put(k, v): compute hash(k), go to bucket, insert or update entry.
get(k): compute hash(k), go to bucket, find entry by equals.
remove(k): same, then unlink.

All are O(1) average, assuming:

The hash function distributes keys uniformly.
The load factor is kept below some threshold (default 0.75 in Java).

Collision resolution

Two keys hashing to the same bucket is a collision. Strategies:

Separate chaining (Java's choice). Each bucket is a linked list (in Java 8+, converted to a balanced tree when size exceeds 8 — "tree-ification"). O(1) average; O(log n) worst case (tree-ified) or O(n) worst case (before Java 8 or in legacy impls).

Open addressing. On collision, probe other buckets (linear, quadratic, or double hashing). Used by some languages and libraries; not Java's HashMap. Simpler memory layout but harder to delete.

Load factor

load factor = n / capacity. When it exceeds the threshold (0.75 in Java), the table doubles capacity and rehashes every entry. Amortized O(1) put (§4).

Lower load factor → more memory, fewer collisions, faster lookups. Higher → opposite.

The `hashCode` / `equals` contract (recap)

If you put an object in a HashMap as a key, and override equals:

You must override hashCode such that a.equals(b) ⇒ a.hashCode() == b.hashCode().
Break this and entries become unfindable — you can put and then get returns null.

Lombok's @EqualsAndHashCode or Java records (auto-generated) solve this cleanly. (Deep-dive: CORE_JAVA.md §1 and §7.)

Java's hash-table zoo

Class	Notes
`HashMap<K,V>`	General-purpose. Not thread-safe. Allows null key/value.
`LinkedHashMap<K,V>`	Preserves insertion (or access, with `accessOrder=true`) order. Slightly slower.
`TreeMap<K,V>`	Sorted by key (Red-Black tree). O(log n) ops. `firstKey`, `ceilingKey`, range queries.
`ConcurrentHashMap<K,V>`	Thread-safe. Per-bucket locking in Java 8+. No null keys or values.
`HashSet<E>`	Set backed by `HashMap<E, Object>`.
`TreeSet<E>`	Sorted set backed by `TreeMap`.
`LinkedHashSet<E>`	Ordered set backed by `LinkedHashMap`.

Interview-scale patterns

1. Two-sum (§16 Q2).

java

int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (seen.containsKey(complement)) return new int[]{seen.get(complement), i};
        seen.put(nums[i], i);
    }
    return new int[0];
}

O(n) time, O(n) space — the canonical "hash map trades space for time" example.

2. Deduplicate / find duplicates (§16 Q5).

java

Set<Integer> seen = new HashSet<>();
for (int x : arr) if (!seen.add(x)) return x;  // first duplicate

HashSet.add returns false if already present — a clean idiom.

3. Frequency count.

java

Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) freq.merge(c, 1, Integer::sum);

merge is cleaner than getOrDefault(...) + 1; it handles the null case internally.

4. Group by key.

java

Map<String, List<String>> groups = new HashMap<>();
for (String word : words) {
    String key = canonical(word);                       // e.g., sorted chars
    groups.computeIfAbsent(key, k -> new ArrayList<>()).add(word);
}

5. LRU cache (§16 Q6). Two approaches:

A. LinkedHashMap with accessOrder=true.

java

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    LRUCache(int capacity) {
        super(capacity, 0.75f, true);   // accessOrder = true
        this.capacity = capacity;
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

O(1) get/put; LinkedHashMap moves accessed entries to the tail. Clean, 10-line solution.

B. Doubly linked list + HashMap<K, Node>. Manual version; demonstrates you understand the mechanism. You keep a HashMap for O(1) lookup and a DLL for O(1) move-to-front / evict-tail. More code, but some interviewers expect it.

The `HashMap` internals (short version — full version in `CORE_JAVA.md` §7)

Buckets array, default size 16, doubled on resize.
Hash = (h = key.hashCode()) ^ (h >>> 16) — XOR high bits into low for better spread.
Bucket index = hash & (capacity - 1) (requires capacity to be power of 2).
Collision: linked-list node; converted to Red-Black tree if chain length ≥ 8 AND table size ≥ 64.
Untreeify if shrinks to ≤ 6.

Gotchas

Mutable keys. Mutating a key after put breaks the map — its hash is cached based on the old state, and get looks in the wrong bucket. Use immutable key types.
ConcurrentModificationException. Iterating a HashMap while another thread modifies it (or even the same thread modifies outside the iterator) throws CME. Use ConcurrentHashMap or iterator.remove().
Iteration order. HashMap gives no ordering guarantee. Use LinkedHashMap for insertion order or TreeMap for sorted order.
Null keys. HashMap allows one null key; ConcurrentHashMap and TreeMap do not.
Memory overhead. Each entry is ~48 bytes in HashMap (key ref, value ref, next ref, hash int + object header + padding). For very large maps, this matters.

Connect to experience

Kafka consumer idempotency often uses a hash-backed dedup: Map<String, Long> from message ID to expiry timestamp, evicted periodically. At scale, this becomes a Redis SET NX EX — but the algorithmic shape is the same hash-map lookup.

Q&A

Q: What happens when two keys hash to the same bucket in Java's HashMap? They're stored in a linked list within that bucket. On lookup, the list is scanned and each entry's key is equals-compared. If the chain grows past 8 entries (and table size ≥ 64), it's converted to a Red-Black tree, giving O(log n) worst-case lookup.
Q: Is HashMap ever O(log n) in Java 8+? Yes — when a bucket tree-ifies, that bucket's operations become O(log n). Average case is still O(1), but pathological hash collisions no longer degrade to O(n).
Q: Why is HashMap not thread-safe, and what's ConcurrentHashMap's approach?HashMap has no internal locking — concurrent modifications can cause lost updates, infinite loops (pre-Java 8), or CME. ConcurrentHashMap uses fine-grained per-bucket locking + CAS operations for atomic updates, enabling high concurrency without locking the whole table.
Q: Two-sum in O(n) — explain the trick. For each element x, check whether target - x has been seen. A hash map makes that check O(1). One pass, O(n) time, O(n) space. Beats the O(n²) brute force.

Part 3 — Hierarchical & Specialized Structures

Trees, heaps, tries, union-find, and graphs. These are the "thinking in two dimensions" structures — pointers no longer form a line but a network. The traversal algorithms in Part 4 build on everything here.

12. Binary trees

Structure & terminology

A binary tree is a hierarchy of nodes where each node has at most two children (left, right). Terminology you need:

Root: node with no parent.
Leaf: node with no children.
Depth of a node: number of edges from the root. Root is depth 0.
Height of a tree: max depth of any node. A single-node tree has height 0.
Balanced tree: for every node, left and right subtree heights differ by ≤ 1 (various formal defs; this is the common one).
Complete tree: all levels filled except possibly the last, which is filled left-to-right. Heaps live on complete trees.
Perfect tree: all levels full. Has 2^h - 1 nodes for height h-1.
Full tree: every node has 0 or 2 children.

The basic node

java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

Traversals — know all four cold

For each traversal, you'll see both recursive and iterative forms. Every tree interview assumes fluency with at least DFS (pre/in/post) and BFS (level-order).

1. Pre-order (root → left → right). "Visit before recursing."

java

void preorder(TreeNode node, List<Integer> out) {
    if (node == null) return;
    out.add(node.val);
    preorder(node.left, out);
    preorder(node.right, out);
}

Use for: serializing a tree (can rebuild structure from pre-order + null markers).

2. In-order (left → root → right). "Visit in sorted order for a BST."

java

void inorder(TreeNode node, List<Integer> out) {
    if (node == null) return;
    inorder(node.left, out);
    out.add(node.val);
    inorder(node.right, out);
}

Use for: BST in sorted order; validating a BST; finding kth smallest.

3. Post-order (left → right → root). "Visit after children."

java

void postorder(TreeNode node, List<Integer> out) {
    if (node == null) return;
    postorder(node.left, out);
    postorder(node.right, out);
    out.add(node.val);
}

Use for: computing heights / sums from leaves up; deleting a tree; dependency resolution.

4. Level-order / BFS. Queue-based.

java

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();                      // snapshot this level's size
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null)  queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

The size = queue.size() snapshot is the trick for grouping by level.

Iterative in-order (the tricky one)

java

List<Integer> inorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) { stack.push(curr); curr = curr.left; }
        curr = stack.pop();
        result.add(curr.val);
        curr = curr.right;
    }
    return result;
}

The idiom is "go left as far as possible, pop/visit, move right, repeat."

Recursive patterns on trees

Most tree problems follow one of these shapes:

1. "Compute something from children, combine at current node." Post-order recursion.

java

int height(TreeNode node) {
    if (node == null) return -1;                       // or 0, depending on convention
    return 1 + Math.max(height(node.left), height(node.right));
}

2. "Pass something down from root." Pre-order, thread state via parameters.

java

boolean hasPathSum(TreeNode node, int target) {
    if (node == null) return false;
    if (node.left == null && node.right == null) return target == node.val;
    return hasPathSum(node.left, target - node.val)
        || hasPathSum(node.right, target - node.val);
}

3. "Both directions." Return a tuple (often via a wrapper class) encoding info needed by both the caller and sibling computations.

Common tree interview problems

Problem	Approach
Height / max depth	Post-order: `1 + max(left, right)`
Is balanced?	Post-order returning (height, isBalanced)
Diameter (longest path)	Post-order: update global `max` with `leftHeight + rightHeight`
Invert tree	Recursive: swap children
Serialize / deserialize	Pre-order with nulls, or level-order
Lowest common ancestor (BT)	Recurse both sides; if both non-null → current node is LCA
Zigzag level-order	Level-order with alternating reverse
Path sum (target)	DFS, subtract val
Count paths summing to target	Prefix sums on paths (see §38)

Q&A

Q: What's the space complexity of recursive tree traversal? O(h) where h is tree height. Balanced tree: O(log n). Skewed: O(n). This is the recursion stack.
Q: You need to traverse a tree iteratively. What data structures do you need? A stack for DFS, a queue for BFS. Stack can be ArrayDeque used as stack; queue can be ArrayDeque used as queue.
Q: BFS vs DFS on a tree — which uses more memory in the worst case? Depends on shape. For a balanced tree, BFS holds a full level (~n/2 nodes) → O(n). DFS holds a path (~log n) → O(log n). For a skewed (list-like) tree, DFS is O(n), BFS is O(1). General rule: balanced → DFS is cheaper; wide → DFS is cheaper; skewed → BFS is cheaper.

13. Binary search trees

The invariant

For every node N: all keys in left subtree are < N.key; all keys in right subtree are > N.key. (Some variants allow duplicates in right subtree — be explicit.)

This invariant makes search, insert, and delete follow a single path from root down — O(h) where h is height.

Operations

Search — follow left/right by comparison:

java

TreeNode search(TreeNode node, int key) {
    while (node != null && node.val != key)
        node = (key < node.val) ? node.left : node.right;
    return node;
}

Insert — search for position, attach there:

java

TreeNode insert(TreeNode node, int key) {
    if (node == null) return new TreeNode(key);
    if (key < node.val)      node.left  = insert(node.left,  key);
    else if (key > node.val) node.right = insert(node.right, key);
    return node;
}

Delete — three cases:

Leaf (no children): just remove.
One child: replace with that child.
Two children: replace with in-order successor (smallest in right subtree), then delete successor from right subtree.

java

TreeNode delete(TreeNode node, int key) {
    if (node == null) return null;
    if (key < node.val)      node.left  = delete(node.left, key);
    else if (key > node.val) node.right = delete(node.right, key);
    else {
        if (node.left == null)  return node.right;
        if (node.right == null) return node.left;
        TreeNode succ = node.right;
        while (succ.left != null) succ = succ.left;
        node.val = succ.val;
        node.right = delete(node.right, succ.val);
    }
    return node;
}

Worst case — the unbalanced tree

Inserting already-sorted keys 1, 2, 3, 4, 5 into a plain BST gives a right-leaning chain. Height = n, so every operation is O(n). This is why balanced BSTs exist (§14).

Finding kth smallest

In-order traversal yields sorted output. Stop at the kth:

java

int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) { stack.push(curr); curr = curr.left; }
        curr = stack.pop();
        if (--k == 0) return curr.val;
        curr = curr.right;
    }
    return -1;
}

Validate BST

Common mistake: checking only left.val < node.val < right.val. That's local; a node deeper in the left subtree could still violate the invariant. Correct: pass min/max bounds down:

java

boolean isValid(TreeNode node, long lo, long hi) {
    if (node == null) return true;
    if (node.val <= lo || node.val >= hi) return false;
    return isValid(node.left, lo, node.val) && isValid(node.right, node.val, hi);
}
// initial call: isValid(root, Long.MIN_VALUE, Long.MAX_VALUE)

Use long to avoid edge case where node values equal Integer.MIN_VALUE / MAX_VALUE.

Q&A

Q: What's the time complexity of BST operations? O(h) where h is the tree's height. Balanced BST: O(log n). Degenerate (list-like): O(n). Java's TreeMap uses a Red-Black tree to guarantee O(log n).
Q: How do you delete a node with two children from a BST? Replace its value with its in-order successor (smallest value in right subtree), then delete the successor from the right subtree. Alternatively, use the in-order predecessor (largest in left subtree).
Q: Why does naively checking node.left.val < node.val < node.right.val fail to validate a BST? Because the BST invariant is global: every ancestor bound must be respected. A node in the right subtree of the root can be deep down and still must be greater than root. You need to pass bounds down as you recurse.

14. Balanced BSTs (AVL & Red-Black intuition)

You won't be asked to implement a Red-Black or AVL tree from scratch in 99% of interviews. You will be asked what they are, why they exist, and what Java's TreeMap uses.

Why balancing matters

A plain BST degrades to O(n) on sorted input. A balanced BST guarantees O(log n) for all ops by keeping height ≈ log n via rotations on insert/delete.

AVL trees

Invariant: for every node, balance factor (left height − right height) is in {−1, 0, 1}.
Rebalancing: single/double rotations after insert/delete.
Height: ≤ 1.44 · log₂(n) — tighter than Red-Black.
Tradeoff: more rotations, faster lookups, slower inserts/deletes.
Use case: read-heavy workloads where lookup latency matters most.

Red-Black trees

Invariants: (1) every node is red or black; (2) root is black; (3) red node's children are black; (4) every path from a node to its descendant nulls has the same number of black nodes; (5) leaves (null) are considered black.
Consequence: longest path is at most 2× the shortest; height ≤ 2·log₂(n+1).
Rebalancing: rotations + color flips.
Tradeoff: less strictly balanced than AVL, but fewer rotations on modification. More balanced for write-heavy workloads.
Use case: Java TreeMap, C++ std::map, Linux kernel scheduler's rb_tree.

`TreeMap` / `TreeSet`

Java's sorted collections are Red-Black trees. Operations:

firstKey / lastKey: O(log n).
ceilingKey(k) / floorKey(k): O(log n) — great for range queries.
subMap(lo, hi): O(log n) + linear in range size.
Ordered iteration: O(n) (in-order walk).

When to prefer TreeMap over HashMap:

Need sorted iteration.
Need nearest-neighbor queries (ceilingKey, floorKey).
Need range scans.

HashMap's bucket tree-ification (brief)

Java 8 HashMap converts a bucket to a Red-Black tree when the chain exceeds 8 entries (and table size ≥ 64). This prevents adversarial collision attacks from degrading to O(n). See CORE_JAVA.md §7 for full depth.

Q&A

Q: What does Java's TreeMap use internally? A Red-Black tree. Supports sorted iteration, ceilingKey/floorKey, range queries, all in O(log n).
Q: AVL vs Red-Black — which is "more balanced"? AVL. Its balance factor ≤ 1 everywhere; Red-Black allows longer paths (up to 2× the shortest). AVL has faster lookups; Red-Black has fewer rotations per modification. Java picked Red-Black for TreeMap because mixed workloads favor the lower rotation cost.
Q: When would you pick TreeMap over HashMap? When you need any of: sorted iteration, nearest-key queries, range scans, or a guaranteed O(log n) worst case (no hash-collision pathology). Cost: O(log n) instead of O(1) average.

15. Heaps & priority queues

What a heap is

A binary heap is a complete binary tree with a heap-order property:

Min-heap: every parent ≤ both children. Root is the minimum.
Max-heap: every parent ≥ both children. Root is the maximum.

Heaps are usually stored in an array (not linked), exploiting the complete-tree property: for index i, children are 2i+1 and 2i+2, parent is (i-1)/2. No pointers — pure array indexing.

Operations

peek / find-min: O(1) — just look at index 0.
offer / insert: append at end, sift up. O(log n).
poll / extract-min: swap root with last, remove last, sift down from root. O(log n).
Build heap from array: heapify in O(n) — not O(n log n). (Bottom-up sift-down from last non-leaf.)

Java's `PriorityQueue`

java

// Min-heap (default, natural ordering)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(3); minHeap.offer(1); minHeap.offer(2);
minHeap.peek();  // 1
minHeap.poll();  // 1

// Max-heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

// Custom comparator — sort by distance
PriorityQueue<Point> nearest = new PriorityQueue<>(
    Comparator.comparingDouble(p -> p.distTo(origin))
);

Gotchas:

PriorityQueue is not thread-safe. For concurrent access use PriorityBlockingQueue.
No efficient contains or remove(object) — both are O(n). If you need decreaseKey, either use an indexed priority queue (hand-rolled) or lazy deletion.
Iteration order is NOT sorted. for (int x : heap) walks the internal array in array order, not heap order. Use poll repeatedly if you need sorted traversal (O(n log n)).

Heap sort

Build a max-heap from the input array (O(n)), then repeatedly extract max and place at the end (O(n log n) total). In-place, O(1) extra space, not stable. Not commonly used in practice (quicksort beats it constant-factor-wise), but it's a worst-case O(n log n) option.

Top-K pattern

The single most common interview use of a heap.

Top-K largest from a stream. Maintain a min-heap of size K. For each incoming element: offer it; if size exceeds K, poll (remove smallest). At the end, the heap contains the K largest.

Complexity: O(n log k) time, O(k) space. Beats "sort everything" O(n log n) when k << n.

java

int[] topKLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int x : nums) {
        minHeap.offer(x);
        if (minHeap.size() > k) minHeap.poll();
    }
    return minHeap.stream().mapToInt(Integer::intValue).toArray();
}

Top-K frequent elements (§16 Q7). Frequency count in a hash map, then top-K over the map entries — same min-heap-of-size-K pattern. Bucket-sort is an alternative O(n) approach if value range is bounded.

K-way merge

Merging K sorted streams with a heap. Keep one "current" element from each stream in a heap; repeatedly poll the min, emit it, offer the next element from that stream. O(n log k) total. See §36.

Median from stream

Two heaps: a max-heap for the lower half, a min-heap for the upper half. Keep them balanced (|size difference| ≤ 1). Median = top of the larger, or average of the two tops if equal size. O(log n) insert, O(1) median query.

Connect to experience

Streaming top-K is how you'd build "top 10 slowest endpoints in the last hour" — maintain a size-K min-heap per window. Similar to Kafka consumer metrics pipelines aggregating at the broker or consumer level.

Q&A

Q: What's the complexity of building a heap from an array of n elements?O(n), not O(n log n). The naive analysis says "n inserts × O(log n)" but the tight analysis using the bottom-up heapify approach gives O(n). Sifting down from level h costs O(h), and there are n / 2^(h+1) nodes at that level — the sum converges to O(n).
Q: Why is PriorityQueue.contains O(n) and not O(log n)? Because the heap's array is not sorted — only the heap-order property holds. To check containment, you must scan linearly. For O(log n) containment, you need an auxiliary hash-indexed structure.
Q: Top-K frequent elements — hash + heap vs bucket sort? Hash + heap: O(n log k), general-purpose. Bucket sort: O(n) but only works when the value range is bounded (e.g., frequencies 1..n, so make n buckets). Bucket sort wins when k is close to n; heap wins when k is small.

16. Tries

The structure

A trie (prefix tree) stores a set of strings (or keys over some alphabet) such that common prefixes share a path from the root. Each node represents a prefix; a node is "end-of-word" if some stored string ends there.

java

class TrieNode {
    TrieNode[] children = new TrieNode[26];    // lowercase a–z
    boolean isEnd;
}

For larger alphabets, use Map<Character, TrieNode> children.

Operations

Insert — walk down, creating nodes as needed:

java

void insert(TrieNode root, String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
        int i = c - 'a';
        if (node.children[i] == null) node.children[i] = new TrieNode();
        node = node.children[i];
    }
    node.isEnd = true;
}

Search — walk down; fail if any step misses:

java

boolean search(TrieNode root, String word) {
    TrieNode node = walk(root, word);
    return node != null && node.isEnd;
}

boolean startsWith(TrieNode root, String prefix) {
    return walk(root, prefix) != null;
}

TrieNode walk(TrieNode node, String s) {
    for (char c : s.toCharArray()) {
        node = node.children[c - 'a'];
        if (node == null) return null;
    }
    return node;
}

Time for insert/search: O(L) where L is the string length — independent of how many strings are stored. That's the trie's superpower.

Space tradeoff

Tries are memory-heavy: every node is an array of 26 pointers (or a map). For N strings of average length L, worst-case space is O(N·L·|Σ|). Optimizations:

Compressed trie (radix tree): merge chains of single-child nodes.
HAT-trie / adaptive trie: hybrid with hash tables.
Map<Character, ...> children for sparse alphabets.

Where tries shine

Autocomplete / typeahead. Walk to prefix node, DFS collect all descendants that are end-of-word.
Spell-check. Walk + allow mismatches → Levenshtein-distance search.
IP routing tables. Longest-prefix-match using binary tries on IP bits.
Dictionary existence checks. Better than HashSet<String> when you also need prefix queries.

Trie as alternative to hash set

For pure existence, HashSet<String> is simpler and usually faster. Use a trie when you also need prefix queries — that's the feature hash sets can't provide.

Q&A

Q: What's the time complexity of inserting a string of length L into a trie with N already-stored strings? O(L) — independent of N. Each character is one hop down the tree or one node allocation. The same is true for lookup.
Q: When would you use a trie over a HashSet<String>? When you need prefix queries (autocomplete, "does any stored word start with X?"). A hash set answers membership but not prefix-based queries.
Q: What's a compressed trie, and why would you use one? A trie where chains of single-child nodes are merged into a single edge labeled with the concatenated characters. Saves space on sparse tries. Radix trees and suffix trees are examples.

17. Disjoint Set / Union-Find

The problem it solves

You have n elements partitioned into disjoint sets. You want to efficiently:

find(x): which set does x belong to?
union(x, y): merge the sets containing x and y.

Naive linked-list impl: one op can be O(n). With two optimizations (union-by-rank + path compression), both ops become nearly O(1) — specifically O(α(n)) where α is the inverse Ackermann function, effectively < 5 for any realistic n.

The implementation

Each element points to a "parent." The root of each tree is the set representative.

java

class UnionFind {
    int[] parent, rank;

    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;   // each is its own root
    }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);  // path compression
        return parent[x];
    }

    boolean union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (rank[rx] < rank[ry])      parent[rx] = ry;
        else if (rank[rx] > rank[ry]) parent[ry] = rx;
        else                          { parent[ry] = rx; rank[rx]++; }
        return true;
    }
}

Why it's fast

Union by rank (or size): always attach the shorter tree under the taller one. Keeps height logarithmic without path compression.
Path compression: on find, re-point every node on the path directly to the root. Flattens the tree over time.
Combined, amortized O(α(n)) per op — essentially O(1).

Where union-find shines

Kruskal's MST algorithm (§23). Sort edges by weight; add if endpoints are in different components.
Connected components in an undirected graph.
Dynamic connectivity — "are u and v in the same component?" queries interleaved with edge additions.
Percolation / Hoshen–Kopelman in physics / image processing.
Equivalence relations — any problem framed as "merge these, ask if these are related."

Q&A

Q: What's the time complexity of union-find with both optimizations? Amortized O(α(n)) per operation, where α is the inverse Ackermann function. For any n under 10^80, α(n) ≤ 4. Effectively O(1).
Q: Union-find vs BFS for connected components — when pick each? BFS/DFS — one pass through the graph gives all components, O(V + E). Union-find wins when edges arrive online (streamed) and you need to answer connectivity queries interleaved with adds. BFS/DFS wins for a single batch pass.
Q: Why "union by rank" instead of "union by size"? Both work and both yield O(log n) height without path compression. Rank is an upper bound on height; size is the node count. Size is easier to reason about; rank is slightly cheaper to maintain. Either is fine — be consistent.

18. Graphs

Definitions

Graph G = (V, E): vertices and edges.
Directed vs undirected: edges have a direction or not.
Weighted vs unweighted: edges carry a cost (for shortest-path / MST) or not.
Cyclic vs acyclic: contains a cycle or doesn't. A DAG (directed acyclic graph) is the shape of dependency graphs, build systems, topological sorts.
Dense vs sparse: dense if |E| ≈ |V|²; sparse if |E| << |V|².

Representations

Adjacency list. List<List<Integer>> — for each vertex, a list of neighbors. Weighted: List<List<int[]>> where each int[] is {neighbor, weight}.

java

int n = 5;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
adj.get(0).add(1);   // edge 0 → 1
adj.get(1).add(0);   // undirected: add both directions

Adjacency matrix. boolean[V][V] or int[V][V] for weights. matrix[u][v] == true means edge u → v.

	Adjacency List	Adjacency Matrix
Space	O(V + E)	O(V²)
Add edge	O(1)	O(1)
Remove edge	O(degree(u))	O(1)
Edge exists?	O(degree(u))	O(1)
Iterate neighbors	O(degree(u))	O(V)

Rule of thumb: adjacency list for sparse graphs (almost always); adjacency matrix when you need fast edge-existence queries on a dense graph, or |V| is small enough that O(V²) memory is fine.

Edge list

Just a List<int[]> of {u, v, weight}. Simplest representation; used by Kruskal's MST (sort edges by weight).

In-memory modeling for service graphs

When you model microservice dependencies (for outage analysis, trace visualization, etc.), the adjacency list representation scales to thousands of services. Each node: a Service object. Each edge: a Dependency with metadata (protocol, SLO, retry policy). This is just a graph — BFS finds impact radius, DFS finds cycle dependencies (which should not exist in a DAG), and topological sort orders deploys.

Detecting a cycle

Undirected graph. DFS. Mark nodes as visited; during DFS from u, for each neighbor v, if v is visited and v ≠ parent(u), there's a cycle. Also possible with union-find: if union(u, v) returns false (already in same set), there's a cycle.

Directed graph. DFS with three states: unvisited (white), in progress (gray), done (black). If DFS ever hits a gray node, there's a cycle. (Hitting black is fine — already processed, no cycle via here.)

Connected components

Undirected: plain DFS/BFS; each connected component is one BFS tree. Count components by counting BFS launches.
Directed: weakly connected = undirected underlying graph is connected. Strongly connected = every pair mutually reachable. Use Kosaraju's or Tarjan's algorithm — O(V + E).

Common graph problems

Problem	Technique
Connected components	BFS/DFS
Shortest path (unweighted)	BFS
Shortest path (non-negative weights)	Dijkstra
Shortest path (arbitrary weights)	Bellman-Ford
All-pairs shortest paths	Floyd-Warshall
MST	Kruskal or Prim
Topological order	DFS post-order reversed, or Kahn's BFS
Cycle detection	DFS (3-color for directed)
Bipartite check	BFS with 2-coloring
Strongly connected components	Kosaraju or Tarjan

Connect to experience

For ArgoCD / GitOps, the application hierarchy is a DAG (app-of-apps). Cycle checks and topological ordering fall out naturally. For microservices, trace propagation is BFS across the service graph — latency adds at each hop.

Q&A

Q: When would you pick an adjacency matrix over an adjacency list? When the graph is dense (E ≈ V²), when V is small, or when edge-existence queries are the dominant operation and must be O(1). In practice, adjacency lists are the default.
Q: How do you detect a cycle in a directed graph? DFS with three states: white (unvisited), gray (on current stack), black (done). If DFS reaches a gray node, there's a back edge — a cycle.
Q: Weakly connected vs strongly connected — what's the difference? Weakly connected: connected when edge directions are ignored. Strongly connected: every pair of vertices has a directed path both ways. In a strongly connected digraph, you can get anywhere from anywhere.

Part 4 — Core Algorithms

With the data structures of Parts 2–3 in hand, Part 4 covers the algorithms that operate on them. Sorting, searching, graph traversal, shortest paths, MST, and topological sort — the classical toolkit every interviewer expects you to know cold.

19. Sorting

Why sorting matters in interviews

Half of medium-difficulty problems become trivial after sorting. "Can you solve this in O(n log n)?" is often code for "sort first, then sweep." Knowing when to reach for sort — and understanding stability and in-place tradeoffs — is more important than being able to code merge sort from memory.

The contenders

Algorithm	Time avg	Time worst	Space	Stable	In-place	Notes
Bubble sort	O(n²)	O(n²)	O(1)	Yes	Yes	Pedagogical only
Selection sort	O(n²)	O(n²)	O(1)	No	Yes	Minimal writes
Insertion sort	O(n²)	O(n²)	O(1)	Yes	Yes	Great on small/nearly-sorted
Merge sort	O(n log n)	O(n log n)	O(n)	Yes	No	Predictable, external sort
Quicksort	O(n log n)	O(n²)	O(log n)	No	Yes	Fastest in practice (usually)
Heap sort	O(n log n)	O(n log n)	O(1)	No	Yes	Worst-case guarantees
Counting sort	O(n + k)	O(n + k)	O(n + k)	Yes	No	Integer keys in [0, k)
Radix sort	O(d·(n + k))	O(d·(n + k))	O(n + k)	Yes	No	Fixed-width keys
Bucket sort	O(n + k) avg	O(n²)	O(n + k)	Yes	No	Uniform distribution

The three you must be able to code

Merge sort. Divide in half, recurse, merge.

java

void mergeSort(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid);
    mergeSort(a, mid + 1, hi);
    merge(a, lo, mid, hi);
}

void merge(int[] a, int lo, int mid, int hi) {
    int[] buf = new int[hi - lo + 1];
    int i = lo, j = mid + 1, k = 0;
    while (i <= mid && j <= hi) buf[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    while (i <= mid) buf[k++] = a[i++];
    while (j <= hi)  buf[k++] = a[j++];
    System.arraycopy(buf, 0, a, lo, buf.length);
}

O(n log n) time, O(n) space, stable.

Quicksort. Pick pivot, partition, recurse.

java

void quicksort(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);
    quicksort(a, lo, p - 1);
    quicksort(a, p + 1, hi);
}

int partition(int[] a, int lo, int hi) {
    int pivot = a[hi];         // simple: last element
    int i = lo - 1;
    for (int j = lo; j < hi; j++) {
        if (a[j] <= pivot) { i++; swap(a, i, j); }
    }
    swap(a, i + 1, hi);
    return i + 1;
}

O(n log n) average, O(n²) worst case (sorted input with last-element pivot). O(log n) space (recursion). Not stable.

Pivot strategies:

Last element: worst case on sorted input.
Random element: expected O(n log n) — the go-to for interviews.
Median-of-three: median of first/middle/last; good defense against common bad inputs.

Insertion sort. Worth knowing because it's the fallback for small subarrays in hybrid sorts.

java

void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
        a[j + 1] = key;
    }
}

O(n²) worst, O(n) on nearly-sorted, O(1) space, stable. Fantastic constant factors → used inside Timsort/introsort for small runs.

What Java actually uses

Arrays.sort(int[]) / other primitives: Dual-Pivot Quicksort (Yaroslavskiy). In-place, not stable (but primitives have no identity so stability is irrelevant). O(n log n) average, O(n²) worst.
Arrays.sort(Object[]) / Collections.sort: Timsort — a hybrid merge sort + insertion sort tuned for partially-sorted data. Stable. O(n log n) worst. Exploits existing runs.
Arrays.parallelSort: Fork/Join parallel merge sort. Useful when arrays are very large.

Stability

A sort is stable if equal elements retain their relative order from the input. Critical when sorting on a secondary key then a primary key.

java

// Sort people by age, then by name (secondary key first, stable sort = final order correct)
people.sort(Comparator.comparing(Person::getName));   // stable
people.sort(Comparator.comparingInt(Person::getAge)); // stable

If these sorts were unstable, the second call would scramble the name-order of people with equal age.

Non-comparison sorts

Counting sort. For integer keys in [0, k), build a count array, then reconstruct. O(n + k) time and space. Beats O(n log n) when k is small. Stable if implemented carefully.

java

int[] countingSort(int[] a, int k) {
    int[] count = new int[k];
    for (int x : a) count[x]++;
    int[] out = new int[a.length];
    int idx = 0;
    for (int v = 0; v < k; v++)
        while (count[v]-- > 0) out[idx++] = v;
    return out;
}

Radix sort. Sort by digit (LSD or MSD) using counting sort as a subroutine. Fixed-width keys only. O(d·(n + k)) where d is digit count.

Bucket sort. Distribute into buckets by a known-uniform hash, sort each bucket, concatenate. O(n) expected on uniform distributions; degrades on skewed data.

When you'd pick which

General-purpose, primitives: Arrays.sort (Dual-Pivot Quicksort).
General-purpose, stable, objects: Collections.sort / List.sort (Timsort).
Worst-case guarantee (no quicksort pathology): heap sort, merge sort.
Integer keys in known range: counting or radix.
External sort (data doesn't fit in memory): merge sort variant.
Small arrays (n < 50): insertion sort.

Q&A

Q: What sort does Arrays.sort(int[]) use, and Collections.sort(List)?Arrays.sort(int[]) — Dual-Pivot Quicksort (not stable, in-place, O(n log n) average). Collections.sort / List.sort / Arrays.sort(Object[]) — Timsort (stable, O(n) extra space, O(n log n) worst).
Q: Why does Java use two different sort algorithms for primitives and objects? Primitives have no notion of identity, so stability is irrelevant — you can use the faster Dual-Pivot Quicksort. Objects can have equal keys but differ by identity/other fields, so stability matters → Timsort.
Q: What's the difference between quicksort and merge sort in terms of space? Merge sort needs O(n) auxiliary space for the merge buffer. Quicksort partitions in place and uses only O(log n) stack space. Quicksort wins on memory; merge sort wins on worst-case time guarantee.
Q: When is insertion sort the right tool? Small n (< ~50), nearly-sorted data, or as the base case inside a hybrid sort (Timsort, introsort). Its O(n) best case on sorted input is unmatched, and constant factors are tiny.

20. Searching

Linear search

O(n), O(1) space. Use when data is unsorted and you don't want to pay to sort, or when n is tiny.

Binary search — the workhorse

Works on any sorted sequence where you can index in O(1) (arrays, not linked lists). O(log n) time, O(1) space iteratively.

The template:

java

int binarySearch(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;      // avoid overflow
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else                 hi = mid - 1;
    }
    return -1;
}

The three binary-search pitfalls

Overflow in midpoint. (lo + hi) / 2 overflows for large indices. Use lo + (hi - lo) / 2 always.
Off-by-one in bounds. Two common templates:
- Inclusive [lo, hi]: while (lo <= hi), update lo = mid + 1 / hi = mid - 1.
- Half-open [lo, hi): while (lo < hi), update lo = mid + 1 / hi = mid. Pick one style and use it consistently. Mixing → off-by-one bugs.
Infinite loops. If you write hi = mid with while (lo <= hi) and the target is just below mid, you can loop forever. This is why template discipline matters.

Binary search on the answer space

When the input isn't obviously sorted but the answer is monotonic ("for any feasible answer X, all Y ≥ X are also feasible"), binary-search the answer.

Example: Koko eating bananas. Find smallest speed k such that she finishes in h hours. Check feasibility at k with a linear scan. Binary search k over [1, max(piles)]. O(n log(max)) time.

java

int minEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = Arrays.stream(piles).max().getAsInt();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canFinish(piles, mid, h)) hi = mid;        // mid is feasible, try smaller
        else                          lo = mid + 1;    // mid too slow
    }
    return lo;
}

This "binary search on the answer" pattern unlocks a surprising number of problems (shipping capacity, split array, allocate books, etc.).

Rotated sorted array (§16 Q9)

Given a sorted array rotated at some unknown pivot, search in O(log n).

java

int searchRotated(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        if (a[lo] <= a[mid]) {                    // left half sorted
            if (a[lo] <= target && target < a[mid]) hi = mid - 1;
            else                                    lo = mid + 1;
        } else {                                  // right half sorted
            if (a[mid] < target && target <= a[hi]) lo = mid + 1;
            else                                    hi = mid - 1;
        }
    }
    return -1;
}

The trick: at each step, at least one of the two halves is sorted. Check which half is sorted, determine whether the target falls within that sorted half, and recurse into the appropriate side.

Find first / last occurrence

For an array with duplicates, binary search is easily adapted. "Find leftmost position where a[i] ≥ target" (lower bound):

java

int lowerBound(int[] a, int target) {
    int lo = 0, hi = a.length;          // half-open
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) lo = mid + 1;
        else                 hi = mid;
    }
    return lo;                          // first index with a[i] >= target (or a.length)
}

upperBound is the same with a[mid] <= target for the move-right condition.

`Arrays.binarySearch` / `Collections.binarySearch`

Built-in. Returns the index of the element if found, or -(insertion_point) - 1 if not. The negative-encoding trick is clever but surprising — if you forget, you get bizarre results. For interview code, writing your own is often clearer.

Q&A

Q: Why lo + (hi - lo) / 2 instead of (lo + hi) / 2? To avoid integer overflow when lo + hi exceeds Integer.MAX_VALUE. In practice, rare for small arrays, but a best practice — zero cost to write it safely.
Q: Search in a rotated sorted array — what's the key insight? At every step, at least one of the two halves (split at mid) is fully sorted. Identify which half is sorted, test whether target falls within that half's range; if yes, recurse there; else, recurse into the other half.
Q: What is "binary search on the answer space"? When the answer is numeric and monotonically feasible (any value ≥ the minimum feasible answer is also feasible), binary-search over the answer range. Use a feasible(x) check at each midpoint. Very common for "minimum X such that Y" problems.

21. Tree & graph traversal (BFS/DFS)

The two algorithms

BFS (breadth-first search). Explore level-by-level from the source. Queue-based.

DFS (depth-first search). Explore as deeply as possible before backtracking. Stack-based (or recursive — which uses the call stack).

Both run in O(V + E) on a graph with V vertices and E edges (every vertex enqueued once, every edge traversed once).

BFS — the template

java

void bfs(List<List<Integer>> adj, int start) {
    boolean[] visited = new boolean[adj.size()];
    Deque<Integer> queue = new ArrayDeque<>();
    queue.offer(start);
    visited[start] = true;
    while (!queue.isEmpty()) {
        int u = queue.poll();
        visit(u);
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                visited[v] = true;
                queue.offer(v);
            }
        }
    }
}

Why mark visited on enqueue, not on dequeue? If you wait until dequeue, the same vertex can be queued multiple times — quadratic blowup in dense graphs.

DFS — recursive and iterative

Recursive:

java

void dfs(List<List<Integer>> adj, int u, boolean[] visited) {
    if (visited[u]) return;
    visited[u] = true;
    visit(u);
    for (int v : adj.get(u)) dfs(adj, v, visited);
}

Iterative with stack:

java

void dfsIter(List<List<Integer>> adj, int start) {
    boolean[] visited = new boolean[adj.size()];
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(start);
    while (!stack.isEmpty()) {
        int u = stack.pop();
        if (visited[u]) continue;
        visited[u] = true;
        visit(u);
        for (int v : adj.get(u)) if (!visited[v]) stack.push(v);
    }
}

BFS vs DFS — when to use each (§16 Q10)

Situation	Pick
Shortest path in unweighted graph	BFS — first time you dequeue a node, its distance is optimal.
Shortest path in weighted graph	Not BFS. Use Dijkstra / Bellman-Ford / Floyd-Warshall.
Find any path or existence	Either works. DFS is simpler (recursive one-liner).
Cycle detection	DFS (three-color for directed).
Topological sort	DFS (post-order reversed) or BFS (Kahn's).
Connected components count	Either. Each BFS/DFS launch = one component.
All paths / backtracking enumeration	DFS — naturally explores one path at a time.
Memory budget: balanced/bushy tree	DFS (O(height) stack) beats BFS (O(width) queue).
Memory budget: very deep / skewed tree	BFS (O(width)) beats DFS (O(depth) → stack overflow risk).

BFS for shortest path

Track distances:

java

int[] bfsDistances(List<List<Integer>> adj, int start) {
    int n = adj.size();
    int[] dist = new int[n];
    Arrays.fill(dist, -1);
    dist[start] = 0;
    Deque<Integer> queue = new ArrayDeque<>();
    queue.offer(start);
    while (!queue.isEmpty()) {
        int u = queue.poll();
        for (int v : adj.get(u)) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                queue.offer(v);
            }
        }
    }
    return dist;
}

Multi-source BFS

When you have multiple sources (e.g., "distance to nearest police station from every cell"), seed the queue with all sources at distance 0. Standard BFS from there gives each cell its shortest distance to any source.

java

Deque<int[]> queue = new ArrayDeque<>();
for (int[] src : sources) { queue.offer(src); dist[src[0]][src[1]] = 0; }
// then standard BFS expansion

0-1 BFS

For graphs where edges have weight 0 or 1, use a deque: push 0-weight edges to the front, 1-weight to the back. Still O(V + E). Beats Dijkstra's log factor for this restricted case.

DFS for topological sort

See §24 for full coverage. Post-order reversed gives a topological order.

Connected components with DFS

java

int countComponents(List<List<Integer>> adj) {
    boolean[] visited = new boolean[adj.size()];
    int count = 0;
    for (int u = 0; u < adj.size(); u++) {
        if (!visited[u]) {
            dfs(adj, u, visited);
            count++;
        }
    }
    return count;
}

Q&A

Q: Why is BFS the right tool for shortest path in an unweighted graph but not a weighted one? BFS expands nodes in order of their hop distance from the source. In unweighted graphs, fewest hops = shortest path. With weights, a longer-hop path can be cheaper — BFS has no way to weight its exploration, so it gives wrong answers. Dijkstra uses a min-heap to always expand the currently-cheapest frontier node.
Q: Recursive DFS on a graph with 10⁶ nodes — what's the risk?StackOverflowError if the graph is deep (long chains). Java's default stack is ~512KB. Use iterative DFS with explicit stack, or increase stack size via -Xss, or prefer BFS.
Q: You want all shortest paths (not just one) in an unweighted graph. How? Run BFS from the source. As you discover each node, also remember its distance and all predecessors that reach it in optimal hops. Then backtrack from target through the predecessor DAG to enumerate all shortest paths.

22. Shortest paths

The four main algorithms

Algorithm	Graph	Weights	Complexity	Notes
BFS	Any	Unweighted (or 0/1)	O(V + E)	Simplest for unweighted
Dijkstra	Any	Non-negative	O((V+E) log V) with binary heap	The workhorse
Bellman-Ford	Any	Any (incl. negative)	O(V·E)	Detects negative cycles
Floyd-Warshall	Any	Any (no neg cycles)	O(V³)	All-pairs shortest paths

Dijkstra's algorithm

The standard single-source shortest-path for non-negative weights.

java

int[] dijkstra(List<List<int[]>> adj, int src) {
    int n = adj.size();
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(x -> x[1]));
    pq.offer(new int[]{src, 0});
    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        int u = top[0], d = top[1];
        if (d > dist[u]) continue;              // stale entry (lazy deletion)
        for (int[] edge : adj.get(u)) {
            int v = edge[0], w = edge[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{v, dist[v]}); // lazy — old entries stay, skipped later
            }
        }
    }
    return dist;
}

Why Dijkstra fails with negative weights: The algorithm finalizes a node's distance when first dequeued. A future negative edge could improve that distance, but Dijkstra has already locked it. Use Bellman-Ford for negative weights.

Why lazy deletion? Java's PriorityQueue doesn't support O(log n) decrease-key. Instead, push a new entry with the better distance; skip stale entries on dequeue (via the d > dist[u] check). Marginally more memory, but avoids O(n) remove.

Bellman-Ford

Handles negative weights; detects negative cycles.

java

int[] bellmanFord(int n, int[][] edges, int src) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
        }
    }
    // nth iteration: if any relaxation succeeds, there's a negative cycle
    for (int[] e : edges) {
        int u = e[0], v = e[1], w = e[2];
        if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v])
            throw new IllegalStateException("negative cycle");
    }
    return dist;
}

V - 1 iterations because any shortest path has at most V - 1 edges. A successful relax in the Vth iteration means a path improves infinitely — negative cycle.

Floyd-Warshall

All-pairs shortest paths, O(V³). Dynamic programming.

java

void floydWarshall(int[][] dist) {
    int n = dist.length;
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist[i][k] != Integer.MAX_VALUE
                 && dist[k][j] != Integer.MAX_VALUE
                 && dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
}

The k loop considers each vertex as a possible intermediate. After iteration k, dist[i][j] is the shortest path using only vertices {0..k} as intermediates.

A*

Heuristic-guided Dijkstra. Uses an estimate h(v) of distance from v to goal to prioritize. Runs faster in practice when a good heuristic is available (shortest paths on a map use straight-line distance as h). Optimal when h is admissible (never overestimates).

When to use which

Unweighted: BFS.
Non-negative, single source: Dijkstra.
Possible negative weights, single source: Bellman-Ford.
All-pairs, small V: Floyd-Warshall.
Path on a map / grid with good heuristic: A*.

Q&A

Q: Why can't Dijkstra handle negative weights? Dijkstra finalizes a node's distance when first extracted from the priority queue. A later negative edge could lower that distance, but Dijkstra never reconsiders finalized nodes. Bellman-Ford relaxes all edges V-1 times, so it doesn't have this assumption.
Q: Dijkstra's complexity is O((V+E) log V). Where does the log come from? The priority queue. Each vertex is inserted/extracted (log V each), and each edge may cause a relax (a PQ insert, log V). Total: O((V+E) log V). With a Fibonacci heap, decrease-key is amortized O(1), giving O(E + V log V) — but the constants make Fibonacci heaps rare in practice.
Q: How do you detect a negative cycle with Bellman-Ford? Run V-1 iterations of edge relaxation. Then do a Vth iteration: if any edge can still relax a distance, there must be a negative cycle reachable from the source. (Because V-1 iterations are enough to converge if no negative cycle exists.)

23. Minimum spanning tree

What an MST is

Given an undirected, connected, weighted graph, an MST is a subset of edges that connects all vertices with minimum total weight and has no cycles. For a graph with V vertices, an MST has exactly V − 1 edges.

Applications: network design (minimize cabling cost), clustering, approximate TSP.

Kruskal's algorithm

Sort edges by weight ascending. For each edge in order, add it to the MST if its endpoints are in different components (use union-find).

java

int kruskal(int n, int[][] edges) {
    Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));
    UnionFind uf = new UnionFind(n);
    int total = 0, count = 0;
    for (int[] e : edges) {
        if (uf.union(e[0], e[1])) {
            total += e[2];
            if (++count == n - 1) break;
        }
    }
    return total;
}

O(E log E) = O(E log V) — dominated by the sort.

Prim's algorithm

Start from any vertex; grow the MST one vertex at a time, always adding the cheapest edge crossing the cut.

java

int prim(List<List<int[]>> adj) {
    int n = adj.size();
    boolean[] inMst = new boolean[n];
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(x -> x[1]));
    pq.offer(new int[]{0, 0});
    int total = 0;
    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        int u = top[0], w = top[1];
        if (inMst[u]) continue;
        inMst[u] = true;
        total += w;
        for (int[] edge : adj.get(u)) {
            if (!inMst[edge[0]]) pq.offer(edge);
        }
    }
    return total;
}

O((V+E) log V) with binary heap.

Kruskal vs Prim — when each fits

Kruskal: shines on sparse graphs and when edges come pre-sorted or can be streamed. Uses union-find. Easy to implement.
Prim: shines on dense graphs. Uses a PQ keyed on "cheapest edge to the frontier."

Q&A

Q: Can there be more than one MST? Yes, if edges have equal weights. Otherwise the MST is unique.
Q: Kruskal uses union-find — why? Union-find answers "would adding this edge create a cycle?" in effectively O(1) by checking whether the endpoints are already in the same component. Without it, cycle detection would be O(V) per edge → O(E·V).
Q: If an edge is in every MST, is there a way to know that without computing the MST? Yes — if removing that edge disconnects the graph, it must be in every spanning tree (including MSTs). Or if it's the unique minimum edge crossing some cut, it's in every MST (the "cut property").

24. Topological sort

The problem

Given a DAG (directed acyclic graph), produce an ordering of vertices such that for every edge u → v, u appears before v. Examples:

Build system: compile dependencies before dependents.
Course prerequisites: take CS101 before CS201.
Deployment order: deploy a service before its consumers.

Only defined for DAGs; cycle → no valid topological order.

Two algorithms

Kahn's algorithm (BFS-based)

Repeatedly remove vertices with in-degree 0:

java

List<Integer> topoSortKahn(int n, List<List<Integer>> adj) {
    int[] indeg = new int[n];
    for (List<Integer> list : adj) for (int v : list) indeg[v]++;
    Deque<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) queue.offer(i);
    List<Integer> order = new ArrayList<>();
    while (!queue.isEmpty()) {
        int u = queue.poll();
        order.add(u);
        for (int v : adj.get(u)) {
            if (--indeg[v] == 0) queue.offer(v);
        }
    }
    if (order.size() != n) throw new IllegalStateException("cycle detected");
    return order;
}

O(V + E). Clean iterative form; also detects cycles (if order.size() < n, there's a cycle).

DFS-based topological sort

Run DFS; add nodes to a stack in post-order; reverse.

java

List<Integer> topoSortDFS(int n, List<List<Integer>> adj) {
    boolean[] visited = new boolean[n];
    boolean[] onStack = new boolean[n];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        if (!visited[i]) dfs(i, adj, visited, onStack, stack);
    }
    List<Integer> order = new ArrayList<>();
    while (!stack.isEmpty()) order.add(stack.pop());
    return order;
}

void dfs(int u, List<List<Integer>> adj, boolean[] visited, boolean[] onStack, Deque<Integer> stack) {
    visited[u] = true;
    onStack[u] = true;
    for (int v : adj.get(u)) {
        if (onStack[v]) throw new IllegalStateException("cycle detected");
        if (!visited[v]) dfs(v, adj, visited, onStack, stack);
    }
    onStack[u] = false;
    stack.push(u);                       // post-order
}

Either algorithm is fine. Kahn's is often preferred for its iterative nature and natural cycle detection.

Uniqueness

Topological order is not unique unless the DAG has a Hamiltonian path. If multiple vertices have in-degree 0 at any step, any order among them is valid.

To produce lexicographically smallest topological order, replace Kahn's FIFO queue with a PriorityQueue (min-heap).

Cycle detection as byproduct

Kahn's: if the final order has fewer than V vertices, some vertices never reached in-degree 0 → they're in a cycle.
DFS: during DFS, if you revisit a node currently on the recursion stack (gray in 3-color), that's a back edge → cycle.

Applications

Use case	Why
Build systems (`make`, Bazel)	Compile each source before anything that includes it
Package managers	Install dependencies before dependents
Course prerequisites	Take prereqs first
Spreadsheet recalculation	Update cells in dependency order
Deployment orchestration	Deploy upstream services first
Deadlock detection	A cycle in "waits-for" graph = deadlock

Connect to experience

ArgoCD's app-of-apps is a DAG. Installing an ApplicationSet implies a topological walk of the resulting apps — parent apps synced before children. If there's a cycle in sync dependencies, the sync will stall indefinitely.

Q&A

Q: What happens if you run topological sort on a graph with a cycle? Kahn's: the output will have fewer than V vertices (the cycle's nodes never reach in-degree 0). DFS: a back edge is detected — an edge to a node currently on the recursion stack. Both can be adapted to throw or return "cycle detected."
Q: Is the topological order unique? Not generally. For any DAG, there can be multiple valid topological orderings if multiple vertices have no incoming edges at the same step. It's unique iff the DAG has a Hamiltonian path — a single chain through all vertices.
Q: How would you find the lexicographically smallest topological order? Replace Kahn's FIFO queue with a min-heap. When multiple vertices are ready (in-degree 0), always pick the smallest. O((V + E) log V).

Part 5 — Algorithmic Paradigms

Where Part 4 was a catalog of specific algorithms, Part 5 is about the design techniques used to invent them. Recursion, divide-and-conquer, dynamic programming, greedy, and bit manipulation are the lenses. Knowing which lens to reach for is half the interview.

25. Recursion & backtracking

The recursion mental model

Every recursive function has two parts:

Base case(s): conditions where the answer is known directly, no recursion.
Recursive case(s): break into smaller subproblems, combine.

If you can't articulate the base case in one sentence, your recursion is wrong. If the recursive case doesn't provably make the subproblem smaller, you'll infinite-loop.

java

int factorial(int n) {
    if (n <= 1) return 1;              // base: factorial of 0 or 1 is 1
    return n * factorial(n - 1);       // recursive: reduce by 1 each call
}

When to reach for recursion

The problem has a self-similar substructure — solve a smaller version, combine.
The input is itself recursive — trees, linked lists, nested arrays.
The state space is a tree of choices — enumerate all configurations.

Backtracking — recursion with state that rolls back

Backtracking explores a tree of choices. At each node, try each option; recurse; if the option leads nowhere, undo and try the next.

Template:

java

void backtrack(State state) {
    if (isGoal(state)) { record(state); return; }
    for (Choice c : choices(state)) {
        if (isValid(state, c)) {
            apply(state, c);           // make the choice
            backtrack(state);          // recurse
            undo(state, c);            // unchoose — critical!
        }
    }
}

The "undo" step is what makes it backtracking rather than plain enumeration. You mutate shared state (e.g., a list), recurse, then reverse the mutation before exploring the next branch. This avoids the O(n) cost of copying state at each recursion.

Classic backtracking problems

Permutations.

java

List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(new ArrayList<>(), nums, new boolean[nums.length], result);
    return result;
}

void backtrack(List<Integer> path, int[] nums, boolean[] used, List<List<Integer>> result) {
    if (path.size() == nums.length) { result.add(new ArrayList<>(path)); return; }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        path.add(nums[i]);
        backtrack(path, nums, used, result);
        path.remove(path.size() - 1);   // undo
        used[i] = false;                 // undo
    }
}

O(n!·n) time (n! permutations × O(n) to copy each into result), O(n) recursion depth.

Subsets.

java

void subsets(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
    result.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        subsets(nums, i + 1, path, result);
        path.remove(path.size() - 1);
    }
}

O(2ⁿ·n) time — each element is in or out, and we copy O(n)-sized paths.

Combinations of size k, N-queens, Sudoku, word search. All same template — define state, choices, isGoal, isValid, apply/undo.

Pruning

The difference between "backtracking that takes 1 second" and "backtracking that takes 10 minutes" is almost always pruning. Prune:

When a partial solution can't possibly satisfy the constraints.
When a partial solution can't beat the current best (branch-and-bound).
When symmetry implies a branch is redundant.

N-queens benefits from pruning "can any queen be placed safely in the next column?" — without it, brute force is 8⁸ = 16M; with pruning, ~2000 nodes.

Recursion pitfalls

Stack overflow. Java's stack ~512KB → ~10⁴ frames. Convert to iterative for deep recursions.
Recomputation. Without memoization, overlapping subproblems blow up. See DP (§27).
Forgetting to undo. Backtracking bugs where mutation leaks between branches.
Returning partial answers. For problems where the recursion returns a value, make sure every path returns.

Q&A

Q: What's the difference between recursion and backtracking? Recursion is a general technique: function calls itself with smaller input. Backtracking is a specific kind of recursion that explores a tree of choices, making a choice, recursing, and undoing the choice before trying the next.
Q: Why the new ArrayList<>(path) in result.add — can't you just add path?path is a single mutable list that you're continuing to modify. Adding it by reference means all your "results" are aliases of the same list, which ends up empty or wrong. Always copy the snapshot.
Q: How do you know when recursion becomes DP? When you identify overlapping subproblems — the same input is recursed on multiple times — memoization turns recursion into DP. If each subproblem is unique (no overlap, e.g., pure divide-and-conquer), memoization doesn't help.

26. Divide & conquer

The template

Divide: split the problem into independent subproblems, usually equal-sized.
Conquer: solve each subproblem recursively.
Combine: merge subproblem results into the full answer.

Divide-and-conquer is recursion where subproblems are independent (no overlap). Contrast with DP, where subproblems overlap and memoization is needed.

Exemplars

Merge sort: divide array in half, sort each, merge. T(n) = 2T(n/2) + O(n) → O(n log n).
Quicksort: partition around pivot, recurse on each side. Same recurrence on average.
Binary search: divide search space in half, recurse on the relevant half. T(n) = T(n/2) + O(1) → O(log n).
Karatsuba multiplication: 3 multiplications of n/2-digit numbers instead of 4. T(n) = 3T(n/2) + O(n) → O(n^log₂3) ≈ O(n^1.585).
Strassen matrix multiply: 7 multiplications of n/2-sized blocks instead of 8. O(n^log₂7) ≈ O(n^2.807).

When D&C is the right tool

Subproblems can be solved independently (no shared state).
There's a natural "split in half" or "partition" step.
Combining subproblem results is cheaper than solving from scratch.

When it's not

Subproblems overlap → DP (§27).
Problem has no obvious decomposition → think differently, or check if a transformation (e.g., sorting first) reveals one.

A subtle D&C problem: count inversions

Given an array, count pairs (i, j) with i < j and a[i] > a[j]. Naive O(n²). D&C solution: while merge-sorting, count inversions during the merge step — O(n log n).

java

int mergeAndCount(int[] a, int lo, int mid, int hi, int[] buf) {
    int i = lo, j = mid + 1, k = 0, inv = 0;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) buf[k++] = a[i++];
        else { buf[k++] = a[j++]; inv += mid - i + 1; }   // all remaining left are > a[j]
    }
    while (i <= mid) buf[k++] = a[i++];
    while (j <= hi)  buf[k++] = a[j++];
    System.arraycopy(buf, 0, a, lo, k);
    return inv;
}

Q&A

Q: What's the difference between divide-and-conquer and dynamic programming? D&C: subproblems are independent (no overlap), solve each once, combine. DP: subproblems overlap — the same subproblem is needed by multiple recursive calls, so we memoize.
Q: What's the Master Theorem doing for you as an interviewer? It gives closed-form solutions for recurrences of form T(n) = aT(n/b) + f(n). You compare f(n) against n^(log_b a): the larger one dominates. Knowing three common cases (merge sort → O(n log n); binary search → O(log n); simple halving → O(n)) covers most interview recurrences.
Q: Merge sort has a natural D&C structure. What about quicksort? Same structure: partition (divide), recurse on each side (conquer), no combine (the in-place partition leaves things sorted). The split is data-dependent (pivot-based), which is why worst case is O(n²) — if the pivot always picks min/max, subproblems are n-1 and 0, giving T(n) = T(n-1) + O(n).

27. Dynamic programming

The most feared topic in interviews. Unnecessarily so. DP is pattern-matching applied to overlapping subproblems. Learn the patterns, trust the process.

What makes a problem DP-solvable

Two properties, both required:

Optimal substructure: optimal solution contains optimal solutions to subproblems. (Most counting/optimization problems have this.)
Overlapping subproblems: the same subproblem arises multiple times in the naive recursion.

If #2 isn't present, plain D&C is fine — no memoization needed.

The two styles

Top-down (memoization): Start from the top problem, recurse; cache subproblem results.

java

int fib(int n, Integer[] memo) {
    if (n < 2) return n;
    if (memo[n] != null) return memo[n];
    return memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
}

Bottom-up (tabulation): Build a table of subproblem results from base cases up.

java

int fib(int n) {
    if (n < 2) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

Trade-offs:

Top-down is often more natural to write — just add memoization to a recursive function.
Bottom-up typically has lower constants (no recursion overhead) and is easier to space-optimize.
Top-down only computes the subproblems needed for the actual answer; bottom-up computes all of them.

Space optimization

Many DP problems only need the last row/few rows of the table:

java

// Fibonacci with O(1) space
int fib(int n) {
    int a = 0, b = 1;
    for (int i = 0; i < n; i++) { int t = a + b; a = b; b = t; }
    return a;
}

This is a common follow-up: "can you do it in O(1) space?" For 1D DP that only looks back a constant distance, yes. For 2D, often you can drop one dimension.

Recognizing a DP problem

Ask yourself:

Does the problem ask for a count, a minimum/maximum, or an existence (can I?)? → likely DP.
Can I describe an answer in terms of answers to smaller instances? → likely DP.
Does the recursive solution recompute the same subproblem? → definitely DP.

Signal words: "minimum cost to", "how many ways to", "longest/shortest", "can we reach", "optimal strategy".

The canonical DP problems

Memorize the recurrences. They recur with small variations in most DP interviews.

1. Fibonacci / climbing stairs.

State: dp[i] = number of ways to reach step i.
Recurrence: dp[i] = dp[i-1] + dp[i-2] (one step or two steps).
Base: dp[0] = 1, dp[1] = 1.
Complexity: O(n) time, O(1) space.

2. Coin change (fewest coins to make amount).

State: dp[a] = min coins to make amount a.
Recurrence: dp[a] = 1 + min(dp[a - c]) for each coin c ≤ a.
Base: dp[0] = 0; everything else ∞ initially.
Complexity: O(amount × |coins|) time, O(amount) space.

java

int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);                      // sentinel = infeasible
    dp[0] = 0;
    for (int a = 1; a <= amount; a++)
        for (int c : coins)
            if (c <= a) dp[a] = Math.min(dp[a], 1 + dp[a - c]);
    return dp[amount] > amount ? -1 : dp[amount];
}

3. 0/1 knapsack.

State: dp[i][w] = max value using first i items with capacity w.
Recurrence: dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]).
Complexity: O(n·W) time, O(n·W) space (space-optimizable to O(W)).

4. Longest Increasing Subsequence (LIS).

O(n²) DP: dp[i] = LIS ending at i; dp[i] = 1 + max(dp[j]) for j < i, a[j] < a[i].
O(n log n): maintain a "tails" array; binary search for position.

5. Longest Common Subsequence (LCS).

State: dp[i][j] = LCS of a[0..i) and b[0..j).
Recurrence:
- If a[i-1] == b[j-1]: dp[i][j] = 1 + dp[i-1][j-1].
- Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Complexity: O(n·m) time and space.

6. Edit distance (Levenshtein).

State: dp[i][j] = min ops to transform a[0..i) into b[0..j).
Recurrence:
- If a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1].
- Else: dp[i][j] = 1 + min(insert, delete, replace).
Complexity: O(n·m).

7. Matrix chain multiplication. Classic interval DP. dp[i][j] = min ops to multiply matrices i..j. Recurrence splits at each k between i and j. O(n³).

The DP recipe

Define the state: what parameter(s) uniquely identify a subproblem? This is the hardest step.
Write the recurrence: how does this state relate to smaller states?
Identify base cases.
Decide top-down vs bottom-up.
Space-optimize if needed.

If you can do step 1 correctly, steps 2–5 are mechanical.

Q&A

Q: What's the difference between memoization and tabulation? Memoization is top-down: start from the full problem, recurse, cache results. Tabulation is bottom-up: fill a table in order of subproblem size. Same complexity; memoization has recursion overhead but may skip unnecessary subproblems.
Q: Coin change — why greedy doesn't always work. Greedy "always take the largest coin ≤ remaining amount" works for US coinage ({1,5,10,25}) but fails for {1,3,4} making 6: greedy takes 4 + 1 + 1 = 3 coins, optimal is 3 + 3 = 2 coins. DP considers all choices; greedy only the locally-best.
Q: How do you recognize a DP problem? Optimization/count problem ("minimum X to achieve Y", "how many ways to Z"), plus a natural recursive decomposition where the same subproblem recurs. If the naive recursion recomputes, memoize it — that's DP.

28. Greedy algorithms

The greedy approach

At each step, pick the locally optimal choice, hoping it leads to a globally optimal solution. When it works, greedy is simpler and faster than DP. When it doesn't, it silently gives wrong answers.

When greedy works

Formally: when the problem has the greedy-choice property (there exists an optimal solution starting with the greedy choice) and optimal substructure (the remaining problem is solved optimally).

Informally: you need to prove greedy works, typically via an exchange argument — "take any optimal solution, swap its first choice for the greedy choice, show it's still optimal."

Classic greedy problems

Activity selection / interval scheduling. Given intervals, pick the max number of non-overlapping. Sort by end time, iterate, take each interval whose start is ≥ previous end.

java

int maxNonOverlapping(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(x -> x[1]));
    int count = 0, prevEnd = Integer.MIN_VALUE;
    for (int[] iv : intervals) {
        if (iv[0] >= prevEnd) { count++; prevEnd = iv[1]; }
    }
    return count;
}

O(n log n). Why does picking earliest-end work? Because it leaves the most room for subsequent activities — any alternate first choice ending later can be swapped for the greedy pick without reducing the count.

Interval merge / minimum rooms. Sort by start time + sweep with a min-heap keyed on end times.

Huffman coding. Build optimal prefix code by repeatedly merging the two lowest-frequency nodes. Min-heap. O(n log n).

Fractional knapsack. Sort items by value/weight ratio descending; take greedily. Works because you can take fractional amounts. 0/1 knapsack is not greedy — must be DP.

Minimum spanning tree. Both Kruskal and Prim are greedy (§23).

Dijkstra. Greedy — always expand the cheapest-known unfinalized node.

Minimum coins in a canonical system (like US coinage). Works because of the specific coin values. Fails in general (see §27 coin change).

The greedy trap

The seductive danger: greedy feels right, so you skip the proof. Common failure modes:

Jumping to greedy without considering DP.
Picking the wrong greedy criterion (e.g., sort by start instead of end in activity selection).
Assuming locally-best is globally-best without an exchange argument.

Rule of thumb: if you can't prove greedy works in under a minute, try DP.

Greedy vs DP — how to decide

Situation	Greedy works?
Fractional knapsack	Yes
0/1 knapsack	No — DP
Activity selection (earliest end)	Yes
Coin change — canonical coin systems	Yes
Coin change — arbitrary coins	No — DP
Huffman coding	Yes
LCS, LIS, edit distance	No — DP
Dijkstra (non-negative weights)	Yes
Dijkstra with negatives	No — Bellman-Ford

Q&A

Q: When does greedy work and DP fail — or vice versa? Greedy works when the greedy-choice property holds: there's an optimal solution starting with the greedy pick. DP works when subproblems overlap and the decision at each step depends on multiple future possibilities. When greedy works, it's faster (typically O(n log n) vs O(n²) for DP).
Q: Fractional knapsack is greedy, but 0/1 knapsack is DP. Why? In fractional, you can take 0.7 of an item — sorting by value/weight ratio and taking greedily works because the best "density" always dominates. In 0/1, you're forced into all-or-nothing per item; the best ratio may be a 9 kg item when you have 10 kg left, forcing you to skip a 3 kg item worth more combined. You need DP to explore both branches.
Q: How do you prove a greedy algorithm is correct?Exchange argument: take any optimal solution; show you can swap its first choice for the greedy choice without making it worse. Then induct — the remaining subproblem is solved optimally by the rest of the greedy sequence.

29. Bit manipulation

The tools

Java bitwise ops (on int / long):

& AND, | OR, ^ XOR, ~ NOT.
<< left shift, >> arithmetic right shift (sign-extending), >>> logical right shift (zero-fill).

Binary representation

int is 32 bits, two's complement. long is 64 bits. Negative numbers: MSB is 1, and -x = ~x + 1.

Core tricks

Set bit i: n | (1 << i). Clear bit i: n & ~(1 << i). Toggle bit i: n ^ (1 << i). Check bit i: (n >> i) & 1 or (n & (1 << i)) != 0.

Lowest set bit: n & -n. E.g., 0b0101100 & 0b1010100 = 0b0000100. Result: a mask with just the lowest set bit of n.

Clear lowest set bit: n & (n - 1). E.g., 0b1100 & 0b1011 = 0b1000. Used in:

Count set bits (Hamming weight, Brian Kernighan's algorithm):

java

int popcount(int n) {
    int c = 0;
    while (n != 0) { n &= (n - 1); c++; }        // clear lowest set bit, count
    return c;
}

Runs in O(popcount(n)) iterations — typically much less than 32. Or just use Integer.bitCount(n) in Java.

Is power of 2: n > 0 && (n & (n - 1)) == 0.

XOR swap (interview trivia, don't actually use):

java

a ^= b; b ^= a; a ^= b;

Single number (XOR across array): If every element appears twice except one, XOR all elements. Pairs cancel; result is the lone element.

java

int singleNumber(int[] nums) {
    int r = 0;
    for (int x : nums) r ^= x;
    return r;
}

Missing number (1..n): XOR all elements and all indices 1..n. Paired values cancel; the missing one remains.

Subset enumeration with bitmask

Each bit represents "element i is in the subset or not." Useful for small-n bitmask DP.

java

for (int mask = 0; mask < (1 << n); mask++) {
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) { /* element i is in this subset */ }
    }
}

O(n·2ⁿ). Usable up to n ≈ 20.

Java gotchas

>> is arithmetic. -4 >> 1 == -2. For logical right shift (zero-fill), use >>>.
Shift amounts are masked. int x = 1 << 32 doesn't zero out — it's 1 << (32 & 31) = 1 << 0 = 1. Use long for shift counts ≥ 32 on ints.
Bitwise ops on byte / short promote to int. byte b = (byte) (b1 & 0xFF) is the idiomatic unsigned-byte read.
Integer.MIN_VALUE. -Integer.MIN_VALUE overflows — stays at MIN_VALUE. Math.abs(Integer.MIN_VALUE) == MIN_VALUE.

Interview problems where bits matter

Single number / missing number (XOR tricks).
Count 1 bits, reverse bits.
Power of 2 / power of 4 checks.
Sum of two integers without + (use XOR + AND + shift).
Subset-sum DP with bitmask over subsets.
Traveling Salesman DP with bitmask state.

Q&A

Q: What does n & (n - 1) do, and why is it useful? Clears the lowest set bit of n. Used for: checking if n is a power of 2 (n & (n - 1) == 0), counting set bits in O(popcount) time, various bitmask iteration tricks.
Q: Why does XOR-ing all elements in an array give the "single number"? XOR is commutative, associative, and x ^ x = 0, x ^ 0 = x. Paired elements XOR to 0; the lone element remains.
Q: How do you enumerate all subsets of an n-element set using bitmasks? Loop mask from 0 to (1 << n) - 1. Bit i of mask indicates whether element i is in the subset. Total: 2ⁿ subsets, each built in O(n) → O(n·2ⁿ). Practical for n ≤ 20.

Part 6 — Interview Patterns (the toolkit)

This is the most useful section of the guide for interviews. Most medium-difficulty problems fit one of these ten patterns. Recognizing the pattern in the first 60 seconds after reading the problem is 80% of the work — the template then writes itself.

Treat each pattern as a spell: a recognizable shape, a canonical code skeleton, and a set of problems it solves.

30. Two pointers

The idea

Use two indices (or pointers) that move through the data with coordinated rules. Converts many O(n²) brute-force approaches to O(n).

Variant A — opposite ends, moving inward

java

int l = 0, r = arr.length - 1;
while (l < r) {
    // compare arr[l], arr[r]; decide which to move
    if (...) l++;
    else     r--;
}

Canonical problems:

Two-sum on sorted array. Compare sum to target; move l right if small, r left if big. O(n).
Palindrome check. Compare s[l] to s[r]; both in → continue; mismatch → not palindrome.
Container with most water. Keep taller pointer; move shorter inward.
Reverse a string / array in place. Swap l and r, converge.

Two-sum on sorted (O(n), O(1)):

java

int[] twoSum(int[] sorted, int target) {
    int l = 0, r = sorted.length - 1;
    while (l < r) {
        int sum = sorted[l] + sorted[r];
        if (sum == target) return new int[]{l, r};
        if (sum < target) l++;
        else              r--;
    }
    return new int[0];
}

Variant B — same direction (fast/slow)

java

int slow = 0;
for (int fast = 0; fast < n; fast++) {
    if (condition(arr[fast])) arr[slow++] = arr[fast];
}
// array is now partitioned, slow is length of "kept" prefix

Canonical problems:

Remove duplicates from sorted array (in place). slow tracks last unique; advance when fast finds new.
Move zeros to end. Keep non-zero prefix with slow; fill trailing zeros after.
Partition array around a pivot. Dutch national flag problem (three pointers — extension).

Remove duplicates from sorted array:

java

int removeDuplicates(int[] a) {
    if (a.length == 0) return 0;
    int slow = 0;
    for (int fast = 1; fast < a.length; fast++) {
        if (a[fast] != a[slow]) a[++slow] = a[fast];
    }
    return slow + 1;                     // new length
}

Variant C — 3-sum via sort + two pointers

Sort. Fix one element; two-pointer the rest. O(n²).

Recognize the pattern when…

Array is sorted (or can be sorted cheaply).
You're looking for pairs / triples summing to something.
You need to partition or compact an array in place.
You're checking a palindrome or other symmetry.

Q&A

Q: Why does two-pointer work on sorted arrays but not unsorted? Because sorting gives you monotonic movement — moving l right always increases the sum; moving r left always decreases. This lets you decide each step correctly. On unsorted data, you have no such guarantee.
Q: What's the space complexity of the two-pointer partition-in-place pattern? O(1). You're reusing the input array.
Q: How do you adapt two-pointer to find all pairs summing to target? After finding one pair, advance both pointers (to skip duplicates — sort first) and continue. Don't stop at first match.

31. Sliding window

The idea

Maintain a "window" (subrange) of the input. Extend the window by moving the right edge; shrink it by moving the left edge. Typically one pass — O(n).

Use when the answer is some property of a contiguous subarray / substring.

Fixed-size window

Window size is given. Precompute the first window, then slide one step at a time: add the new right element, remove the old left element.

java

int maxSumFixed(int[] a, int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) sum += a[i];
    int best = sum;
    for (int i = k; i < a.length; i++) {
        sum += a[i] - a[i - k];
        best = Math.max(best, sum);
    }
    return best;
}

Variable-size window

Window grows/shrinks based on a condition. Pattern:

java

int l = 0;
for (int r = 0; r < n; r++) {
    // expand window by including arr[r]
    while (!valid(window)) {
        // shrink window from left
        l++;
    }
    // at this point, [l..r] is valid; record / update answer
}

Canonical problems:

Longest substring without repeating characters. Window contents = set of chars; shrink when duplicate.
Longest substring with at most k distinct characters. Window's distinct-char count ≤ k.
Minimum window substring (contains all chars of T). Expand until valid, then shrink while valid.
Smallest subarray sum ≥ S. Expand until sum ≥ S, shrink while sum ≥ S, record length.

Longest substring without repeating chars:

java

int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> lastSeen = new HashMap<>();
    int l = 0, best = 0;
    for (int r = 0; r < s.length(); r++) {
        char c = s.charAt(r);
        if (lastSeen.containsKey(c)) l = Math.max(l, lastSeen.get(c) + 1);
        lastSeen.put(c, r);
        best = Math.max(best, r - l + 1);
    }
    return best;
}

O(n) time, O(min(n, alphabet)) space.

Why it's O(n)

Both l and r only move forward. Each makes at most n moves total. So the total work across the whole algorithm is O(n), not O(n²), even though there's a nested while loop.

Recognize the pattern when…

Problem asks about a contiguous subarray / substring.
You're looking for the longest / shortest / count of subranges satisfying some property.
Moving the right edge only improves or worsens the property monotonically.
Stream of events / requests with a time window (last N seconds).

§16 Q8 — Top N by count in last hour from a stream

Combine sliding window (time-based) with a heap (top-K). Keep a deque of (timestamp, event) pairs; evict events older than 1 hour from the front. Maintain a frequency map + a size-N min-heap over counts. On expiration, decrement counts; if a counted item drops below heap threshold, rebuild.

The time-window is the slide; the heap is the top-K (§35).

Q&A

Q: Why is sliding window O(n) even though there's a nested while inside the for loop? Because each pointer only advances forward. r moves at most n times; l moves at most n times. Total iterations across the outer-for and inner-while combined is ≤ 2n.
Q: What makes a problem a sliding-window problem? Contiguous range, monotonic property (extending the window changes the property predictably), and the question is about the longest/shortest/count of valid ranges.
Q: Fixed-size vs variable-size window — how do you choose? Fixed: problem specifies window length (e.g., "max sum of any k consecutive"). Variable: problem specifies a property the window must satisfy (e.g., "longest substring with ≤ 2 distinct chars"). Different templates.

32. Fast & slow pointers

The idea

Two pointers that move at different rates through a sequence. Used to find cycles or midpoints in single-pass, constant-space.

Classic uses

1. Cycle detection in a linked list (Floyd's tortoise-and-hare). Already covered in §8.

2. Middle of a linked list. Slow moves 1, fast moves 2. When fast reaches end, slow is at middle.

java

ListNode middle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

3. Nth from end. Advance fast by n; then move both until fast reaches end. Slow lands at nth-from-end.

java

ListNode nthFromEnd(ListNode head, int n) {
    ListNode slow = head, fast = head;
    for (int i = 0; i < n; i++) fast = fast.next;
    while (fast != null) { slow = slow.next; fast = fast.next; }
    return slow;
}

4. Happy number. Compute digit-square sum repeatedly; if you cycle, it's not happy. Use fast/slow instead of a hash set to detect cycles with O(1) space.

5. Find duplicate number (Floyd). Treat array as a linked list: index → value as next pointer. Cycle exists iff there's a duplicate. Find cycle start → that's the duplicate.

Recognize the pattern when…

Linked list, or implicit linked-list structure (array where a[i] is the "next index").
You need to detect a cycle or find a position by ratio (middle = half speed).
Constraint says O(1) space on a linked list.

Q&A

Q: Why does Floyd's cycle detection work? If there's no cycle, fast reaches the end and we stop. If there's a cycle, fast laps slow — they must meet inside the cycle because their relative speed is 1 and the cycle length is finite.
Q: Fast/slow to find the middle — for even length, which middle do you get? If fast = head, you get the second middle (for 1→2→3→4, you get 3). If fast = head.next, you get the first middle (returns 2). Pick based on the problem.
Q: Why is fast/slow sometimes preferred over a hash set for cycle detection? Space. Hash set is O(n) — fast/slow is O(1). Same time complexity, but space matters in tight constraints or for streaming problems.

33. Merge intervals

The idea

Intervals represent [start, end] pairs. Many problems reduce to: sort + sweep.

Canonical problems

Merge overlapping intervals.

java

int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(x -> x[0]));
    List<int[]> out = new ArrayList<>();
    for (int[] iv : intervals) {
        if (out.isEmpty() || out.get(out.size() - 1)[1] < iv[0]) {
            out.add(iv);
        } else {
            out.get(out.size() - 1)[1] = Math.max(out.get(out.size() - 1)[1], iv[1]);
        }
    }
    return out.toArray(new int[0][]);
}

O(n log n), dominated by sort.

Insert interval into a sorted non-overlapping list. Three phases: intervals fully before new one (emit as-is), intervals that overlap (merge), intervals fully after (emit as-is). O(n).

Meeting rooms — minimum rooms required.

Option 1: sort intervals by start; use a min-heap keyed on end times. For each new interval, poll heap if its end ≤ current start (room freed); offer current end. Heap size = rooms in use; max observed = answer. O(n log n).
Option 2: event sweep. Create +1 event at each start, −1 at each end. Sort all events. Sweep tracking running sum; max value = rooms needed.

Non-overlapping intervals (min to remove). Greedy: sort by end time, iterate, remove any overlapping with last kept.

Recognize the pattern when…

Input is a list of intervals/ranges.
Question is about overlaps, merges, gaps, max concurrency, max non-overlapping.

Q&A

Q: Why sort by start time for merge, but by end time for max non-overlapping? Merge: sort by start to walk left-to-right; merge when current start ≤ running end. Max non-overlapping: sort by end time so greedy picks finish as early as possible, leaving most room for subsequent intervals — canonical greedy exchange-argument problem.
Q: Meeting rooms — heap approach vs sweep approach? Heap: straightforward; maintains rooms in use. Sweep: elegant for "max concurrent," reduces to sorted-events scan. Both O(n log n). Sweep sometimes easier to code.

34. Cyclic sort / in-place rearrangement

The idea

When the input is a permutation of 1..n (or 0..n−1, or some known-range integers), you can sort in O(n) by repeatedly swapping each element to its correct index.

java

void cyclicSort(int[] a) {
    int i = 0;
    while (i < a.length) {
        int correctIdx = a[i] - 1;             // for values 1..n
        if (a[i] != a[correctIdx]) swap(a, i, correctIdx);
        else i++;
    }
}

Each swap places at least one element in its final position → O(n) swaps → O(n) total.

Canonical problems

Find missing number in 1..n. Cyclic sort; the index where a[i] != i+1 marks the missing.
Find all duplicates. Cyclic sort; after sorting, a[i] != i+1 → a[i] is a duplicate.
Find first missing positive. Cyclic sort using only positives 1..n; first index where a[i] != i+1 gives answer.
Find the corrupt pair (one number duplicated, one missing). Combined traversal.

Cyclic sort is the go-to for "find X in an array that looks like a permutation of 1..n" problems — often O(n) time and O(1) space beating the hash-set approach.

Q&A

Q: Why is cyclic sort O(n) when it looks like two nested loops? Each swap places one element in its final position. There can be at most n such placements, so the total work across the algorithm is O(n).
Q: When does cyclic sort work? Only when input values are a (near-)permutation of a small known range — classically 1..n or 0..n−1. For general integer inputs, you need a hash set (O(n) time, O(n) space).

35. Top-K elements

The idea

Find the k largest / smallest / most-frequent items. Three main approaches, pick by context.

Approach A — size-K min-heap

For top-k largest: maintain a min-heap of size k. For each element: offer it; if size > k, poll. At the end, heap = k largest.

java

int[] topKLargest(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int x : nums) {
        heap.offer(x);
        if (heap.size() > k) heap.poll();
    }
    int[] out = new int[k];
    for (int i = k - 1; i >= 0; i--) out[i] = heap.poll();
    return out;
}

O(n log k) time, O(k) space.

For top-k smallest: use a max-heap (comparator reversed), same pattern.

Approach B — quickselect

Partition-based selection (like quicksort but only recurse into the relevant side). O(n) average, O(n²) worst. O(1) extra space. In-place.

java

int quickselect(int[] a, int k) {
    int lo = 0, hi = a.length - 1;
    int targetIdx = a.length - k;           // kth largest = (n-k)th smallest
    while (lo <= hi) {
        int p = partition(a, lo, hi);
        if (p == targetIdx) return a[p];
        if (p < targetIdx) lo = p + 1;
        else               hi = p - 1;
    }
    return -1;
}

Approach C — bucket sort (top-k frequent)

When values have a bounded range (especially frequencies in 1..n), bucket by frequency. Scan from highest bucket to lowest, emitting elements until k collected. O(n).

java

int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int x : nums) freq.merge(x, 1, Integer::sum);
    List<Integer>[] buckets = new List[nums.length + 1];
    for (var e : freq.entrySet()) {
        int f = e.getValue();
        if (buckets[f] == null) buckets[f] = new ArrayList<>();
        buckets[f].add(e.getKey());
    }
    int[] out = new int[k];
    int idx = 0;
    for (int f = buckets.length - 1; f >= 0 && idx < k; f--) {
        if (buckets[f] == null) continue;
        for (int x : buckets[f]) {
            if (idx < k) out[idx++] = x;
        }
    }
    return out;
}

Which to pick

Scenario	Pick
Streaming data (can't revisit)	Heap — O(n log k)
Static data, k small	Heap — simple, good constant factors
Static data, k ≈ n/2	Sort — O(n log n) is fine
Need the kth value but not the full k	Quickselect — O(n) average
Frequency-based top-k with bounded counts	Bucket sort — O(n)

Q&A

Q: Why use a min-heap for top-K largest, not a max-heap? The min-heap of size K retains the K largest seen so far. Its root (minimum of the K) is the threshold for entry: any new element greater than root belongs in the top-K, pushing root out. With a max-heap, you'd need a different strategy (don't shrink to K).
Q: Quickselect vs heap — what's the tradeoff? Quickselect: O(n) average, O(n²) worst, in-place, not stable. Heap: O(n log k) guaranteed, O(k) space, works on streams. Use quickselect when you have all data up front and don't fear worst case. Heap when you want worst-case guarantee or streaming.
Q: Top-K frequent via bucket sort — why is it O(n)? Frequency counts lie in [1, n]. Build n+1 buckets. Each element is placed once (O(n)). Scan buckets descending — total work proportional to number of distinct elements + K → O(n). Avoids the log factor of heap-based approaches.

36. K-way merge

The idea

Merge k sorted sequences into one sorted output. Use a min-heap of size k holding the current head of each sequence.

java

ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
    for (ListNode head : lists) if (head != null) heap.offer(head);
    ListNode dummy = new ListNode(0), tail = dummy;
    while (!heap.isEmpty()) {
        ListNode min = heap.poll();
        tail.next = min;
        tail = tail.next;
        if (min.next != null) heap.offer(min.next);
    }
    return dummy.next;
}

Total elements: n. Heap ops: O(log k) each. Total: O(n log k).

Canonical problems

Merge k sorted lists. Above.
Smallest range covering elements from k lists. Heap of (value, listIdx); track max across heap; sliding window on range.
Kth smallest in a sorted matrix. Treat each row as a sorted list → k-way merge, stop at kth.

Why k-way merge is elegant

Merging two at a time is O(n · k) (pairwise merge). Heap-based k-way is O(n log k) — a big speedup when k is large. The heap acts as a dynamic "which stream has the smallest next element" oracle.

Connect to experience

If you've dealt with merging partitioned Kafka consumer output for time-ordered downstream processing — that's a k-way merge. Each partition is a sorted (by timestamp) stream; output is the time-sorted union.

Q&A

Q: Why O(n log k) for k-way merge, not O(n log n)? Heap size is bounded by k (one entry per stream). Each of n elements causes one heap poll + one heap push → O(log k) each. Total O(n log k).
Q: When is pairwise merging (repeatedly merge two) better than heap-based? Almost never — pairwise is O(n·k) in the worst case. It wins only when k is very small (k = 2, trivially).

37. Monotonic stack/queue

The idea

A stack (or deque) whose contents are always monotonic — strictly increasing or strictly decreasing. Before pushing a new element, pop anything that would violate monotonicity.

Used for: "for each element, find the next/previous greater/smaller element" in O(n).

Monotonic stack — next greater element

java

int[] nextGreater(int[] a) {
    int[] out = new int[a.length];
    Arrays.fill(out, -1);
    Deque<Integer> stack = new ArrayDeque<>();    // stack of indices
    for (int i = 0; i < a.length; i++) {
        while (!stack.isEmpty() && a[stack.peek()] < a[i]) {
            out[stack.pop()] = a[i];
        }
        stack.push(i);
    }
    return out;
}

For each element, any previously-unresolved smaller elements are popped and resolved. Each index is pushed and popped at most once → O(n).

Canonical problems

Next/previous greater/smaller element. Template above.
Daily temperatures. Days until warmer — same shape, store day diffs.
Largest rectangle in histogram. Monotonic stack of increasing heights; when popping, compute the rectangle ending at current index.
Trapping rain water (non-monotonic-stack approach). Two-pointer is usually cleaner here.

Monotonic deque — sliding window maximum

Maintain a deque of indices such that a[deque] is monotonically decreasing. Front of deque = index of max in current window.

java

int[] maxSlidingWindow(int[] a, int k) {
    int n = a.length;
    int[] out = new int[n - k + 1];
    Deque<Integer> dq = new ArrayDeque<>();          // indices, decreasing a-values
    for (int i = 0; i < n; i++) {
        while (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();     // evict out-of-window
        while (!dq.isEmpty() && a[dq.peekLast()] < a[i]) dq.pollLast();       // maintain monotonicity
        dq.offerLast(i);
        if (i >= k - 1) out[i - k + 1] = a[dq.peekFirst()];
    }
    return out;
}

O(n) — each element enters and leaves the deque once.

Recognize the pattern when…

Problem asks "for each i, find the nearest j where [some greater/smaller property]."
Problem asks about max/min in every sliding window.
Problem involves a rectangular histogram area.

Q&A

Q: Why is next-greater-element O(n) with a stack, not O(n²)? Each index is pushed once and popped at most once. Total work is 2n across the whole algorithm — amortized O(1) per element.
Q: Sliding window maximum — why a deque, not a heap? Heap doesn't support efficient removal of arbitrary elements (O(n)). Deque maintains monotonicity in O(1) amortized and lets you both evict out-of-window from the front and maintain monotonicity at the back.

38. Prefix sums & difference arrays

Prefix sum

prefix[i] = a[0] + a[1] + ... + a[i-1]. Precompute in O(n). Then range sum a[l..r] is prefix[r+1] - prefix[l] in O(1).

java

int[] buildPrefix(int[] a) {
    int[] p = new int[a.length + 1];
    for (int i = 0; i < a.length; i++) p[i + 1] = p[i] + a[i];
    return p;
}

int rangeSum(int[] p, int l, int r) {     // inclusive l, r
    return p[r + 1] - p[l];
}

Subarray sum equals K (classic hash-map + prefix)

Count subarrays whose sum equals K.

java

int subarraySum(int[] a, int k) {
    Map<Integer, Integer> counts = new HashMap<>();
    counts.put(0, 1);                     // empty prefix
    int sum = 0, count = 0;
    for (int x : a) {
        sum += x;
        count += counts.getOrDefault(sum - k, 0);
        counts.merge(sum, 1, Integer::sum);
    }
    return count;
}

O(n) time. Works with negative numbers (unlike sliding window).

Key insight: sum[l..r] == k iff prefix[r+1] - prefix[l] == k, iff prefix[l] == prefix[r+1] - k. For each prefix p, count how many earlier prefixes equaled p - k.

2D prefix sum

prefix[i][j] = sum of submatrix from (0,0) to (i-1,j-1). Builds in O(m·n). Any axis-aligned rectangle sum is O(1) via inclusion-exclusion:

sum(r1..r2, c1..c2) = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]

Difference array (for range updates)

Inverse of prefix sum. If you need to add v to every element in a[l..r] many times, then later query values:

diff[l] += v; diff[r+1] -= v (O(1) per update).
Final values: a[i] = prefix sum of diff up to i.

O(n) to build; O(1) per range update; O(n) to finalize. Great for "many range updates, one final pass."

Recognize the pattern when…

Problem asks about subarray sums (including negatives).
Many range sum queries.
Multiple range updates followed by queries.
2D version: submatrix sum queries.

Q&A

Q: Why does subarray-sum-equals-k work with a hash map of prefix sums?sum[l..r] = prefix[r+1] - prefix[l]. Setting this equal to k gives prefix[l] = prefix[r+1] - k. So as we walk r, we count how often prefix[r+1] - k has appeared as an earlier prefix. O(n), one pass.
Q: Why does sliding window fail on "subarray sum equals k" if array has negatives? Sliding window relies on monotonic growth: extending the window only increases the sum. With negatives, extending can decrease the sum → you can't decide whether to move l or r. Prefix sums + hash map handles negatives correctly.

39. Recursion → DP conversion playbook

The five-step process

Given a naive recursion with overlapping subproblems, convert it to DP:

Step 1: Identify the state. Which parameters of the recursive call uniquely determine the subproblem? Those are your state variables. E.g., for fib(n), state is n. For LCS, state is (i, j).

Step 2: Write the recurrence. Express the recursive relationship. E.g., dp[i][j] = dp[i-1][j-1] + ... (match case) or max(dp[i-1][j], dp[i][j-1]) (mismatch case).

Step 3: Identify base cases. The simplest inputs with known answers. fib(0) = 0, fib(1) = 1. LCS of empty string = 0.

Step 4: Decide top-down or bottom-up.

Top-down: add memoization to the naive recursion.
Bottom-up: fill a table in subproblem-size order.

Step 5: Space-optimize if possible. If the recurrence only looks back a constant distance, replace the table with a few scalars.

Example: naive Fibonacci → DP

Naive:

java

int fib(int n) { return n < 2 ? n : fib(n-1) + fib(n-2); }    // O(2ⁿ)

Top-down memoized:

java

int fib(int n, Integer[] memo) {
    if (n < 2) return n;
    if (memo[n] != null) return memo[n];
    return memo[n] = fib(n-1, memo) + fib(n-2, memo);
}    // O(n), O(n) space

Bottom-up tabulated:

java

int fib(int n) {
    if (n < 2) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
    return dp[n];
}    // O(n), O(n) space

Space-optimized:

java

int fib(int n) {
    if (n < 2) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) { int c = a + b; a = b; b = c; }
    return b;
}    // O(n), O(1) space

When you're stuck

Draw the recursion tree for a small input. Circle repeated subproblems. The circles are your memoization candidates. The parameters of a circle are your state variables.

Q&A

Q: Top-down or bottom-up — which do you write first in an interview? Write the recurrence as plain recursion first (proves you understand the structure). Add memoization (easy, confidence-boost). Then convert to bottom-up if the interviewer pushes for "can you do it iteratively?" — shows the full progression.
Q: How do you space-optimize a 2D DP? Identify which rows of the table are actually needed. If dp[i][j] depends only on dp[i-1][*] and dp[i][*], you only need two rows. If only on dp[i-1][j-1] and similar, one row + a saved scalar.
Q: Memoization but still O(2ⁿ) — what went wrong? Either your state key doesn't capture all relevant parameters (two different calls with the same key actually need different answers), or you forgot to check the cache before recursing. Double-check both.

Part 7 — Java-Specific Cheat Sheet

Everything you need to write correct, idiomatic Java under interview pressure — without fumbling in the API, stumbling on gotchas, or reinventing what the JDK already provides. Keep this section open in the last hour before an interview.

40. Java Collections for interviews

The decision tree

Ask, in order:

Do I need key-value mapping? → Map.
Do I need uniqueness only? → Set.
Do I need ordering? → List (insertion) / TreeMap/TreeSet (sorted) / LinkedHashMap/LinkedHashSet (insertion).
Do I need FIFO/LIFO? → Deque (ArrayDeque).
Do I need priority ordering? → PriorityQueue.

The big table

Structure	Ops	Time	Ordering	Null?	Thread-safe?
`ArrayList<E>`	`get/set i`	O(1)	Insertion	null ok	No
	`add`	O(1) amortized
	`add i`	O(n)
	`remove i`	O(n)
`LinkedList<E>`	`get i`	O(n)	Insertion	null ok	No
	`add` (end)	O(1)
	`addFirst` / `addLast`	O(1)
`ArrayDeque<E>`	`push/pop/offer/poll`	O(1) amortized	Insertion	No null	No
`HashMap<K,V>`	`get/put/remove`	O(1) avg, O(log n) worst	None	null key/val ok	No
`LinkedHashMap<K,V>`	`get/put/remove`	O(1) avg	Insertion or access	null ok	No
`TreeMap<K,V>`	`get/put/remove`	O(log n)	Sorted by key	No null key	No
`ConcurrentHashMap<K,V>`	`get/put/remove`	O(1) avg	None	No null	Yes
`HashSet<E>`	`add/contains/remove`	O(1) avg	None	null ok	No
`LinkedHashSet<E>`	`add/contains/remove`	O(1) avg	Insertion	null ok	No
`TreeSet<E>`	`add/contains/remove`	O(log n)	Sorted	No null	No
`PriorityQueue<E>`	`offer/poll`	O(log n)	Heap-order (min)	No null	No
	`peek`	O(1)
	`contains/remove`	O(n)

When to pick which

Goal	Use
Random-access index list	`ArrayList`
Frequent front-insert/remove	`ArrayDeque` (or `LinkedList`)
Stack (LIFO)	`ArrayDeque` (push/pop)
Queue (FIFO)	`ArrayDeque` (offer/poll)
Priority queue	`PriorityQueue`
Lookup by key	`HashMap`
Sorted-by-key lookup, range queries	`TreeMap`
Lookup preserving insertion order	`LinkedHashMap`
LRU cache	`LinkedHashMap(cap, 0.75f, true)` + `removeEldestEntry`
Concurrent key-value access	`ConcurrentHashMap`
Membership test	`HashSet`
Sorted membership / nearest-neighbor	`TreeSet`

LRU cache (§16 Q6) — the one-liner

java

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int cap;
    public LRUCache(int cap) { super(cap, 0.75f, true); this.cap = cap; }
    @Override protected boolean removeEldestEntry(Map.Entry<K, V> e) { return size() > cap; }
}

accessOrder=true makes the map move accessed entries to the tail — eldest is LRU.

Building each structure fast

java

// ArrayList
List<Integer> list = new ArrayList<>();
List<Integer> sized = new ArrayList<>(1000);                  // hint capacity
List<Integer> fromArray = new ArrayList<>(List.of(1, 2, 3));

// HashMap / HashSet
Map<String, Integer> map = new HashMap<>();
Set<String> set = new HashSet<>();
Map<String, Integer> literal = Map.of("a", 1, "b", 2);         // immutable

// Deque (as stack or queue)
Deque<Integer> stack = new ArrayDeque<>();
Deque<Integer> queue = new ArrayDeque<>();

// PriorityQueue
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
PriorityQueue<int[]> byFirst = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));

Q&A

Q: When would you pick LinkedHashMap over HashMap? When you need insertion or access order preserved — LRU caches, ordered output of accumulated state, predictable iteration order.
Q: Why does ConcurrentHashMap forbid null keys/values? Because map.get(k) == null must mean "key absent" — if null were a valid value, there'd be no way to distinguish. For HashMap (single-threaded), you can disambiguate with containsKey. For concurrent maps, such a two-step check isn't atomic, so they ban null outright.
Q: ArrayDeque vs LinkedList for queue usage?ArrayDeque wins. Circular-buffer-backed, cache-friendly, faster across the board. LinkedList has more overhead (node allocations, pointer chasing) and matches ArrayDeque only on one op: removeFirstOccurrence via the List iterator.

41. Useful built-ins under pressure

Sorting

java

Arrays.sort(intArr);                                   // primitives, Dual-Pivot Quicksort
Arrays.sort(objArr);                                   // objects, Timsort (natural order)
Arrays.sort(objArr, Comparator.reverseOrder());        // descending
Arrays.sort(points, (a, b) -> a[0] - b[0]);            // custom — WATCH OUT for overflow
Arrays.sort(points, Comparator.comparingInt(a -> a[0]));  // overflow-safe

Collections.sort(list);
list.sort(Comparator.comparing(Person::getName).thenComparingInt(Person::getAge));

The comparator overflow trap: (a, b) -> a[0] - b[0] overflows when a[0] is very negative and b[0] very positive. Prefer Comparator.comparingInt(...) or Integer.compare(a[0], b[0]) — both overflow-safe.

Binary search

java

int idx = Arrays.binarySearch(sortedArr, key);      // returns -(insertion+1) if absent
int idx = Collections.binarySearch(sortedList, key);

Decode the "negative encoding" if needed: if (idx < 0) idx = -idx - 1; // insertion point.

Math

java

Math.min(a, b); Math.max(a, b);
Math.abs(x);                          // careful: Math.abs(Integer.MIN_VALUE) is MIN_VALUE!
Math.floorDiv(a, b); Math.floorMod(a, b);   // correct for negatives
Math.addExact(a, b);                  // throws ArithmeticException on overflow
Integer.MAX_VALUE; Integer.MIN_VALUE; Long.MAX_VALUE;
Math.pow(2, 30);                      // returns double — cast carefully

Bit operations

java

Integer.bitCount(n);                  // popcount
Integer.numberOfLeadingZeros(n);
Integer.numberOfTrailingZeros(n);
Integer.highestOneBit(n);             // largest power of 2 ≤ n
Integer.toBinaryString(n);
Integer.reverse(n);
Long.bitCount(n);                     // long version

Strings

java

s.charAt(i);                          // char at index
s.length();                           // string length (method, not field)
s.substring(i, j);                    // [i, j)
s.toCharArray();                      // mutable char[]
String.valueOf(x);                    // any type to String
Integer.parseInt(s);
Integer.toString(n);
s.split(",");                         // argument is a REGEX — beware "."
s.split("\\.");                       // escape regex metacharacters
String.join(",", list);               // join an Iterable
s.equals(other);                      // NEVER use ==
s.equalsIgnoreCase(other);
Character.isDigit(c);
Character.isLetter(c);
Character.isLetterOrDigit(c);
Character.toLowerCase(c);
Character.toUpperCase(c);
Character.getNumericValue(c);         // '7' -> 7

StringBuilder

java

StringBuilder sb = new StringBuilder();
sb.append(x);                         // chainable; returns this
sb.append(arr);
sb.reverse();
sb.delete(start, end);
sb.deleteCharAt(i);
sb.setCharAt(i, c);
sb.charAt(i);
sb.length();
sb.toString();

Arrays & Lists conversion

java

// int[] → Integer[]
Integer[] boxed = Arrays.stream(intArr).boxed().toArray(Integer[]::new);
// int[] → List<Integer>
List<Integer> list = Arrays.stream(intArr).boxed().toList();
// List<Integer> → int[]
int[] raw = list.stream().mapToInt(Integer::intValue).toArray();
// Collection → array
String[] arr = stringList.toArray(new String[0]);

Arrays.asList(1, 2, 3);               // fixed-size list backed by varargs array
List.of(1, 2, 3);                     // IMMUTABLE list (Java 9+)
Set.of(1, 2, 3); Map.of("a", 1);      // immutable counterparts
Arrays.fill(arr, value);
Arrays.copyOf(arr, newLength);
Arrays.copyOfRange(arr, from, to);    // [from, to)
System.arraycopy(src, srcPos, dst, dstPos, length);
Arrays.equals(arr1, arr2);
Arrays.hashCode(arr);
Arrays.toString(arr);                 // pretty-print
Arrays.deepToString(arr2D);

Stream idioms (terse but allocate — know their cost)

java

// Sum
int sum = Arrays.stream(arr).sum();
// Max/min
int max = Arrays.stream(arr).max().getAsInt();
// Filter + count
long n = list.stream().filter(x -> x > 0).count();
// Group-by
Map<String, List<Person>> byCity = list.stream()
    .collect(Collectors.groupingBy(Person::city));
// Count-by
Map<String, Long> counts = list.stream()
    .collect(Collectors.groupingBy(x -> x, Collectors.counting()));
// Sorted toList
List<Integer> sorted = list.stream().sorted().toList();
// Range
IntStream.range(0, n).forEach(...);

Map merge / compute / getOrDefault

java

// Frequency count
map.merge(k, 1, Integer::sum);

// Append to list value
map.computeIfAbsent(k, x -> new ArrayList<>()).add(v);

// Default on absence
int count = map.getOrDefault(k, 0);

// Conditional put
map.putIfAbsent(k, v);

// Iterate entries
for (Map.Entry<K, V> e : map.entrySet()) { e.getKey(); e.getValue(); }

42. Common Java interview gotchas

Integer overflow

java

int mid = (lo + hi) / 2;                  // overflows for large lo+hi
int mid = lo + (hi - lo) / 2;             // safe

Math.abs(Integer.MIN_VALUE);              // returns Integer.MIN_VALUE! (still negative)

int a = 10_000_000 * 10_000_000;          // silently overflows; use long
long b = 10_000_000L * 10_000_000;        // promotes to long

Autoboxing gotchas

java

// Integer cache: -128 to 127
Integer x = 127, y = 127;
x == y;                                   // true (cached)
Integer a = 128, b = 128;
a == b;                                   // false — different objects!
a.equals(b);                              // true — always use equals

// Null unbox
Integer n = null;
int i = n;                                // NullPointerException

// In ternary
int i = flag ? 0 : someInteger;           // if someInteger is null → NPE

// Boxing in hot loops
List<Integer> list = ...;
long sum = 0;
for (Integer x : list) sum += x;          // autobox+unbox each iteration

In hot paths, use int[] instead of List<Integer>.

String pitfalls

java

"a" == "a";                               // true  (literal interning)
"a" == new String("a");                   // false (different object)
"a".equals(new String("a"));              // true (content compare)

// substring cost (Java 7+)
s.substring(1, 4);                        // allocates and copies — O(n), not O(1)

// split is regex
"a.b".split(".");                         // returns [] because "." matches any char!
"a.b".split("\\.");                       // ["a", "b"]

// concatenation in loops
String r = "";
for (int i = 0; i < n; i++) r += i;       // O(n²) — each += creates new String

Character arithmetic

java

char c = '5';
int n = c - '0';                          // 5 — idiomatic digit extraction

char lower = 'C' + 32;                    // 'c' — chars auto-widen to int in arithmetic

// But assigning back to char needs cast
char c2 = (char) (c + 1);                 // '6'

Array / List confusion

java

int[] arr = {1, 2, 3};
arr.length;                               // field

List<Integer> list = ...;
list.size();                              // method

String s = "abc";
s.length();                               // method

// Arrays.asList with primitives
List<int[]> a = Arrays.asList(new int[]{1, 2, 3});   // single-element list of int[]!
List<Integer> b = Arrays.asList(1, 2, 3);            // this is what you want

ConcurrentModificationException

java

for (Integer x : list) {
    if (x == 0) list.remove(x);           // CME on next iteration
}

// Fix: use Iterator's remove
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
    if (it.next() == 0) it.remove();
}
// Or iterate backward over index-based loop if using List
for (int i = list.size() - 1; i >= 0; i--) {
    if (list.get(i) == 0) list.remove(i);
}
// Or use removeIf
list.removeIf(x -> x == 0);

HashMap iteration order

java

Map<String, Integer> m = new HashMap<>();
m.put("a", 1); m.put("b", 2); m.put("c", 3);
// Iteration order is NOT "a", "b", "c" — it's bucket order, unpredictable

Use LinkedHashMap or TreeMap if order matters.

PriorityQueue ordering traps

java

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(3); pq.offer(1); pq.offer(2);
for (int x : pq) System.out.print(x);     // 1 3 2 — heap order, not sorted!
// To get sorted, you must poll one at a time.

// No "decrease key" — updates require re-add + lazy-delete pattern

Comparator subtraction overflow

java

Comparator<int[]> c = (a, b) -> a[0] - b[0];      // overflows with MIN_VALUE/MAX_VALUE
Comparator<int[]> safe = Comparator.comparingInt(a -> a[0]);
Comparator<int[]> safe2 = (a, b) -> Integer.compare(a[0], b[0]);

Recursion depth

Java's default stack ~512KB → ~10,000 frames depending on frame size. For long linked-list traversals or deep trees, prefer iteration or increase stack via -Xss.

`Integer.parseInt` and negative signs

java

Integer.parseInt("42");           // 42
Integer.parseInt("-42");          // -42
Integer.parseInt("+42");          // 42 (Java 7+)
Integer.parseInt("42L");          // NumberFormatException — no suffix
Integer.parseInt("");             // NumberFormatException
Integer.parseInt(null);           // NullPointerException

Modulo with negatives

java

-7 % 3;                          // -1 in Java — NOT 2
Math.floorMod(-7, 3);            // 2 — mathematical modulo

Use Math.floorMod when you need Python-style positive modulo.

Part 8 — Meta-skills: How to interview on DSA

Knowing the algorithms is necessary but not sufficient. Interviewers are also evaluating how you think under pressure: how you clarify, communicate, and recover. The sections below are the soft-skills playbook — the scaffolding that makes the hard-skills of Parts 1–7 visible.

43. The 5-minute problem-attack template

Within the first 5 minutes after reading the problem, you should have:

Clarified the problem.
Walked through 1–2 examples.
Stated a brute-force approach with complexity.
Begun optimizing, or declared you're going to code the brute force.

Here's the phase-by-phase template.

Phase 1 — Clarify (60 seconds)

Ask about:

Input range. Can it be empty? Single element? Very large? Negative numbers?
Output form. Return the value, or modify in place? Indices or elements?
Uniqueness / duplicates. Can inputs repeat? Are the targets unique?
Sorted / unsorted. If not stated, assume unsorted and ask.
Character set / alphabet. ASCII, Unicode, lowercase only?
Tie-breaking. If multiple valid answers, which to return?
Language-level constraints. Any overflow concerns? Can you assume fits in int?

Don't ask trivia just to look thoughtful — ask what genuinely affects the approach.

Phase 2 — Examples (30–60 seconds)

Walk the interviewer through a small example by hand. Convinces them (and you) that you've understood. Also catches edge cases early.

"OK, for input [1, 2, 3, 4] and target 5, I'd expect output [0, 4] because 1+4=5…"

Phase 3 — Brute force + complexity (60 seconds)

State the obvious n² or exponential approach — even if you already see the O(n) solution. Interviewers want to see you cover the space, and brute force gives them a baseline to compare against.

"The brute force is O(n²): for each pair, check if they sum to target. That's obviously too slow for n = 10⁵, so let me think about how to improve it."

Phase 4 — Optimize (2 minutes)

Think out loud about pattern-matching to Part 6 techniques. Say things like:

"I see a sorted array — two-pointer might work here."
"I'm looking for contiguous subarrays — sliding window is worth considering."
"This recursion will recompute subproblems — let me check for DP."

If stuck: try to refine brute force (can I skip cases? Precompute? Sort first?).

Phase 5 — Code (5–15 minutes)

Narrate as you code. State each invariant. Don't type silently.

Phase 6 — Test (2 minutes)

Walk through your code with a small example. Then check edge cases:

Empty input.
Single element.
All same value.
Max/min integer.
Duplicates.
Already-sorted / reverse-sorted.

Phase 7 — Complexity (30 seconds)

"This is O(n) time, O(n) space. The time is dominated by the single pass; the space comes from the hash map, which could hold all elements in the worst case."

Never skip Phase 7. Interviewers expect you to state complexity unprompted.

44. Communicating while solving

Narrate your thought process

Silence is the enemy. Interviewers can't give you hints if they can't tell where you're stuck. Narrate:

"I'm trying to see if there's structure I can exploit…"
"The fact that it's sorted makes me think of two-pointer or binary search…"
"Let me think — if I pick X first, then Y has to be… hm, that doesn't work for the case where…"

State invariants

As you code, say what's true at each step:

"After this loop, slow points to the first duplicate…"
"I'm maintaining the invariant that the heap contains the K largest seen so far."

This makes bugs easier to spot (yours and theirs) and demonstrates rigor.

Acknowledge alternatives

"This works in O(n log n). I think there's probably an O(n) solution using bucket sort, but this is simpler — let me start here and optimize if time permits."

Shows awareness of the full design space without over-engineering.

Recover cleanly from mistakes

When you realize you're going in the wrong direction:

Don't hide. "Wait, I just realized this approach fails when [X]. Let me back up."
Don't defend. Acknowledge quickly, then think forward.
Don't restart unless truly necessary. Often a small tweak fixes it.

Ask before assuming

If the problem is ambiguous and you're about to commit to an assumption, state it:

"I'll assume input is never empty — is that OK?"
"If there are multiple valid answers, I'll return the first one I find — sound good?"

When you're truly stuck

Say so. "I'm stuck. Let me walk through the structure of what I know…" is better than 3 minutes of silence. Often the interviewer will offer a nudge, but only if they know you're stuck.

45. Common mistakes that sink candidates

Ranked by how often they sink candidates who knew the algorithm:

1. Jumping to code before understanding the problem

Symptom: you start typing before you've run a single example by hand. Result: wrong solution, or correct solution to the wrong problem. Cost: 10 minutes of wasted coding and awkward recovery.

Fix: force yourself to walk one example out loud before touching the keyboard.

2. Skipping complexity analysis

Symptom: you write a solution, test it, say "I think it works" — and never state complexity. Interviewer has to prompt you. Result: they doubt you understand asymptotic analysis.

Fix: end every code walkthrough with "this is O(X) time, O(Y) space."

3. Ignoring edge cases

Symptom: code works on the happy path. Interviewer asks "what about empty input?" — you say "oh, right" and bolt on a check. Result: you look reactive.

Fix: run the edge-case checklist (§46) before the interviewer asks.

4. Silent debugging

Symptom: code doesn't work, you fall silent, stare, reread, change things randomly. Result: interviewer has no idea what you're thinking.

Fix: narrate. "OK, I expected slow to be 3 here but it's 2 — so my loop must be advancing prematurely. Let me re-examine the update condition…"

5. Not using built-ins you actually know

Symptom: you reimplement Integer.bitCount or Arrays.sort instead of using them, and burn 5 minutes. Result: less time for the actual problem.

Fix: know the Part 7 cheat sheet. Use Map.merge, PriorityQueue, TreeMap.ceilingKey, etc. — they're expected, not impressive.

6. Premature optimization

Symptom: you try to write the optimal solution from the start, get stuck on edge cases in the optimal version, and run out of time. Result: no working solution.

Fix: brute force → working → optimized. Always have something that runs.

7. Ignoring hints

Symptom: interviewer says "what if you sorted the array first?" — you say "no, I want to try it unsorted" and continue failing. Result: interviewer concludes you're uncoachable.

Fix: treat hints as free help. Say "oh, if I sort first then…" and run with it.

8. Overflow bugs

Symptom: (lo + hi) / 2 for large indices; a - b comparator with Integer.MIN_VALUE. Result: wrong answer on an edge test.

Fix: default to lo + (hi - lo) / 2 and Integer.compare / Comparator.comparingInt.

9. Off-by-one errors

Symptom: binary search returns the wrong bound; loop terminates one iteration early/late. Result: subtle bug you can't find under pressure.

Fix: pick one binary-search template and stick to it. When testing, walk an explicit example with indices.

10. Treating DP as a magic bullet

Symptom: you hear "optimization problem," reach for DP, and try to fit it even when greedy works. Result: 20 minutes building a DP table for a 5-line greedy solution.

Fix: check for greedy first — it's usually faster to implement and test.

46. Edge-case checklist

Run through this list before declaring a solution done. Customize per problem, but these defaults catch most bugs:

Inputs

Empty input (null array, empty string, empty list)?
Single-element input?
All elements identical?
Already sorted / reverse-sorted?
Duplicates present? (Many problems subtly assume uniqueness.)
Negative numbers? Zero? (Especially for sum / sliding window.)
Max / min integer? (Overflow traps.)
Very large n (does it fit in memory?)

Tree / graph specific

Single node?
Linked-list-shaped tree (skewed)?
Disconnected graph?
Cycles present (when you assumed DAG)?
Self-loops, parallel edges?

String specific

Empty string?
Single character?
Whitespace / non-alpha characters?
Case sensitivity assumption correct?
Unicode vs ASCII?

Numeric specific

Division by zero?
Overflow in intermediate calculations?
Integer.MIN_VALUE / Integer.MAX_VALUE boundaries?
Very small / very large floats (precision)?

Concurrency / streaming (if applicable)

Out-of-order events?
Late-arriving data?
Ties / equal keys?
Backpressure (bounded memory)?

Back Matter

47. Complexity cheat-sheet table

Keep this open 10 minutes before the interview — verbal muscle memory.

Data structures

Structure	Access	Search	Insert	Delete	Space
Array	O(1)	O(n)	O(n)	O(n)	O(n)
Dynamic array (ArrayList)	O(1)	O(n)	O(1) amortized	O(n)	O(n)
Singly linked list	O(n)	O(n)	O(1) at head	O(1) at head	O(n)
Doubly linked list	O(n)	O(n)	O(1) at either end	O(1) given node	O(n)
Stack	n/a	O(n)	O(1)	O(1)	O(n)
Queue	n/a	O(n)	O(1)	O(1)	O(n)
Hash table (average)	n/a	O(1)	O(1)	O(1)	O(n)
Hash table (worst, tree-ified)	n/a	O(log n)	O(log n)	O(log n)	O(n)
Binary heap	n/a	O(n)	O(log n)	O(log n)	O(n)
Binary search tree (balanced)	O(log n)	O(log n)	O(log n)	O(log n)	O(n)
Binary search tree (unbalanced)	O(n)	O(n)	O(n)	O(n)	O(n)
Red-Black / AVL tree	O(log n)	O(log n)	O(log n)	O(log n)	O(n)
Trie	n/a	O(L)	O(L)	O(L)	O(N·L·Σ)
Union-find (w/ both opts)	n/a	n/a	O(α(n))	n/a	O(n)

Sorting

Algorithm	Best	Average	Worst	Space	Stable
Bubble	O(n)	O(n²)	O(n²)	O(1)	Yes
Insertion	O(n)	O(n²)	O(n²)	O(1)	Yes
Selection	O(n²)	O(n²)	O(n²)	O(1)	No
Merge	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Quicksort	O(n log n)	O(n log n)	O(n²)	O(log n)	No
Heapsort	O(n log n)	O(n log n)	O(n log n)	O(1)	No
Timsort (Java)	O(n)	O(n log n)	O(n log n)	O(n)	Yes
Counting	O(n+k)	O(n+k)	O(n+k)	O(n+k)	Yes
Radix	O(d(n+k))	O(d(n+k))	O(d(n+k))	O(n+k)	Yes

Graph algorithms

Algorithm	Complexity	Notes
BFS / DFS	O(V + E)	Unweighted traversal
Dijkstra (binary heap)	O((V+E) log V)	Non-negative weights
Bellman-Ford	O(V·E)	Handles negatives, detects neg cycles
Floyd-Warshall	O(V³)	All-pairs shortest paths
Kruskal's MST	O(E log E)	With union-find
Prim's MST (heap)	O((V+E) log V)	Good for dense graphs
Topological sort	O(V + E)	DFS or Kahn's

48. Decision tables

"I need fast..."

I need…	Pick
Lookup by key, order doesn't matter	`HashMap`
Lookup by key, sorted iteration	`TreeMap`
Lookup by key, insertion order preserved	`LinkedHashMap`
Thread-safe key lookup	`ConcurrentHashMap`
Get min / max repeatedly	`PriorityQueue`
Insert/remove at both ends	`ArrayDeque`
Random access by index	`ArrayList` or primitive array
Unique-element test	`HashSet`
Sorted set with range queries	`TreeSet`

"Given a problem about..."

If the problem involves…	Consider…
Contiguous subarray / substring	Sliding window, prefix sums
Pairs / triples summing to target	Hash map (unsorted) or two pointers (sorted)
Next greater / smaller	Monotonic stack
Max / min in sliding window	Monotonic deque
Top-K / kth element	Heap or quickselect
Shortest path, unweighted	BFS
Shortest path, non-negative weights	Dijkstra
Shortest path, possible negatives	Bellman-Ford
Dependency order / scheduling	Topological sort
Cycle detection	DFS (3-color for directed), or union-find
Connected components	BFS/DFS, or union-find
Palindrome / reverse	Two pointers
Counting ways / minimum cost / longest-X	DP
Choice-based optimization w/ greedy-choice property	Greedy
"Find X in array of 1..n"	Cyclic sort
All permutations / combinations / subsets	Backtracking
Prefix matching / autocomplete	Trie
Min spanning tree	Kruskal (sparse) or Prim (dense)
Merge k sorted streams	Heap-based k-way merge
Range sum queries	Prefix sums (immutable); segment tree or BIT (mutable)

"This looks exponential..."

If naive is exponential but you need polynomial…	Try
Recursion recomputes subproblems	Memoize → DP
Greedy-choice property holds	Greedy
Can partition problem independently	Divide and conquer
Small state space (n ≤ 20)	Bitmask DP
Monotonic constraint	Binary search on answer

49. Top 40 rapid-fire review questions

Thirty-second answers. Test yourself the morning of.

Complexity

What's O(log n) with base, say, 3? Same as O(log n) — base drops out as a constant.
Amortized O(1) vs worst-case O(1)? Amortized averages worst case across n ops; any single op can be O(n).
Space complexity of recursive binary search? O(log n) from the call stack.

Arrays / strings

Overflow-safe midpoint? lo + (hi - lo) / 2.
Why is String += x in a loop O(n²)? Each += allocates a new String.
Anagram check in O(n), O(1) space? int[26] frequency counter.
Reverse an array in place? Two pointers swapping toward middle.

Linked lists

Reverse iteratively in one sentence? Three pointers prev/curr/next; flip each next; advance.
Detect cycle in O(1) space? Floyd's fast/slow.
Find middle in one pass? Fast/slow; slow is middle when fast reaches end.

Stacks / queues

Valid parentheses approach? Push opens, pop-and-match on close.
Why ArrayDeque over Stack? Unsynchronized, faster, cleaner API.
Monotonic stack use case? Next greater / smaller element in O(n).

Hash tables

Two-sum in O(n)? Hash map of seen values; check complement.
Why does HashMap.put amortize to O(1) despite rehashing? Doubling capacity makes rehash cost geometric → O(1) per insert amortized.
Mutable keys — why forbidden? Hash changes after insert; get looks in wrong bucket.

Trees

In-order traversal of BST — what order? Sorted (ascending).
BFS vs DFS for shortest path on an unweighted tree/graph? BFS.
Kth smallest in BST? In-order traversal, stop at kth.
Validate BST — what's the trick? Pass min/max bounds down; not just local compare.

Heaps

Top-K largest, data structure? Size-K min-heap.
Top-K frequent, optimal? Hash + bucket sort → O(n).
Median from stream? Two heaps (max-heap lower, min-heap upper).

Graphs

Adjacency list vs matrix — when matrix? Dense graphs, small V, fast edge-exists queries.
Dijkstra why not for negatives? Finalizes on first dequeue; future negative edge can't improve.
Topological sort two approaches? Kahn's (BFS, in-degree 0 queue) or DFS post-order reversed.

Sorting / searching

What sort does Arrays.sort(int[]) use? Dual-Pivot Quicksort.
What sort does Collections.sort use? Timsort (stable).
Binary search on answer space — one use case? Min speed to finish by deadline.
Search rotated sorted array — trick? One half is always sorted; recurse there if target fits, else other half.

Paradigms

DP top-down vs bottom-up — which to write first? Top-down (memoized recursion) is often more natural; bottom-up for iteration.
Coin change — greedy or DP? DP for general; greedy only works for canonical systems.
Exchange argument — what does it prove? That greedy is correct; swap greedy's pick into any optimal, show still optimal.
Bitmask DP — when useful? Small state space (n ≤ 20); traveling salesman, subset DP.

Patterns

Sliding window O(n) despite nested loop — why? Pointers only advance forward.
Sliding window — when fails? When array has negatives and problem needs contiguous sums.
Prefix sum + hash map — canonical use? Count subarrays summing to k, handles negatives.
K-way merge — complexity? O(n log k) with heap of k stream heads.

Java-specific

Comparator overflow trap? (a, b) -> a - b can overflow; use Integer.compare or Comparator.comparingInt.
PriorityQueue iteration order? Heap order, not sorted. Must poll to get sorted sequence.

50. Further reading

Books

Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms (CLRS). The reference. Don't read cover-to-cover; use it as a lookup for specific algorithms you want to see proved rigorously.
Steven Skiena — The Algorithm Design Manual. More practical than CLRS. Part I is the best pedagogical intro to design techniques; Part II is a catalog of problems with solutions.
Robert Sedgewick, Kevin Wayne — Algorithms, 4th Edition. Java-flavored; exceptional on sorting and graphs. Free companion lectures on Coursera.
Jon Bentley — Programming Pearls. Short, dense essays on algorithmic thinking. Great plane-ride reading.

Interview-focused

Gayle McDowell — Cracking the Coding Interview (6th ed). The standard. Problem catalog + interview framing. Language-agnostic (pseudocode + Java).
Elements of Programming Interviews (EPI) — Java version. More challenging than CTCI; tighter solutions.

Online resources

Big-O Cheat Sheet — printable reference.
NeetCode 150 / NeetCode 250 — curated LeetCode list organized by pattern, with video walkthroughs.
LeetCode — the de facto interview problem archive. Filter by topic tag, difficulty, and company.
Visualgo — interactive visualizations for sorting, searching, graph algorithms. Great for building intuition.
Algorithms Specialization (Coursera, Sedgewick) — Stanford's Tim Roughgarden course; rigorous, mostly free to audit.
USACO Guide — competitive-programming focused but excellent for graph and DP patterns.

Problem-solving practice (free)

Codeforces — contests and archive; problem ratings help you calibrate difficulty.
AtCoder — cleaner problem statements than Codeforces; weekly Beginner Contests are well-curated.
Project Euler — math-heavy; good for bit manipulation and number theory.

51. Practice Problems by Pattern

Fifty classic problems grouped by the patterns from Part 6. Each entry includes a one-line setup, difficulty, and the key insight. Attack in this order as a refresher set; skip any you've recently solved cold.

Arrays & strings (8)

Two Sum. Return indices i, j with a[i] + a[j] == target. Easy. Hash map → O(n).
Best Time to Buy and Sell Stock. Max profit from one buy+sell. Easy. Track running min; profit = current − min so far.
Product of Array Except Self. out[i] = product of all except a[i], no division. Medium. Prefix and suffix products.
Rotate Image (2D matrix). Rotate 90° in place. Medium. Transpose + reverse each row.
Spiral Matrix. Output elements in spiral order. Medium. Four bounds shrinking inward.
Set Matrix Zeroes. If cell is 0, zero its row+col; in place. Medium. Use first row/col as markers, O(1) extra space.
Longest Common Prefix. Of an array of strings. Easy. Vertical scan or divide-and-conquer.
String to Integer (atoi). Parse string to int, handling signs, overflow, whitespace. Medium. Careful overflow checks.

Two pointers (4)

3Sum. All unique triples summing to 0. Medium. Sort + for loop + two pointers. Skip duplicates.
Container With Most Water. Two lines forming max-area rectangle. Medium. Two pointers; always move shorter.
Remove Duplicates from Sorted Array. In place; return new length. Easy. Slow/fast pointers.
Valid Palindrome II. Is it palindrome after deleting at most one char? Easy. Two pointers; on mismatch, try skipping left or right.

Sliding window (4)

Longest Substring Without Repeating Characters. Medium. Map char → last-seen index; move l past duplicates.
Minimum Window Substring. Smallest substring containing all chars of T. Hard. Expand to valid, shrink while valid.
Permutation in String. Does s2 contain permutation of s1? Medium. Fixed-size window + char count compare.
Longest Repeating Character Replacement. Longest substring with ≤ k replacements. Medium. Window of (length − maxCharCount) ≤ k.

Fast & slow pointers (3)

Linked List Cycle. Does the list have a cycle? Easy. Floyd's tortoise/hare.
Linked List Cycle II. Return cycle start node. Medium. Detect cycle; reset one pointer to head; advance both 1 step.
Happy Number. Repeated digit-square-sum reaches 1? Easy. Fast/slow detects cycle without hash set.

Linked lists (4)

Reverse Linked List. Iterative + recursive. Easy. prev/curr/next; flip.
Merge Two Sorted Lists. Merge into one sorted list. Easy. Dummy node + two pointers.
Add Two Numbers. Lists represent reversed digits; add. Medium. Carry-based addition digit by digit.
Reorder List. L0→Ln→L1→Ln-1→... Medium. Find middle → reverse second half → interleave.

Stacks & queues / monotonic (4)

Valid Parentheses. Matched brackets. Easy. Stack.
Min Stack. push/pop/top/getMin all O(1). Medium. Auxiliary stack of running mins.
Daily Temperatures. For each day, days until warmer. Medium. Monotonic stack of indices.
Sliding Window Maximum. Max over every window of size k. Hard. Monotonic deque of decreasing values.

Hash tables (4)

Group Anagrams. Group strings by anagram class. Medium. Key by sorted chars, or by frequency tuple.
Top K Frequent Elements. Medium. Heap (O(n log k)) or bucket sort (O(n)).
Contains Duplicate II. Duplicate within k indices? Easy. HashMap of value → last index.
Longest Consecutive Sequence. Longest run of consecutive integers. Medium. HashSet; for each value, extend only from "start of run."

Trees (traversal + BST) (6)

Maximum Depth of Binary Tree. Easy. Recursion: 1 + max(left, right).
Same Tree / Symmetric Tree. Easy. Mirror recursion.
Binary Tree Level Order Traversal. Medium. BFS with size snapshot.
Lowest Common Ancestor (Binary Tree). Medium. Recurse both sides; two non-nulls → current is LCA.
Validate Binary Search Tree. Medium. Pass min/max bounds.
Kth Smallest Element in a BST. Medium. In-order traversal, stop at k.

Heaps / top-K (3)

Kth Largest Element in an Array. Medium. Size-K min-heap or quickselect.
Find Median from Data Stream. Hard. Two heaps.
Meeting Rooms II. Minimum rooms. Medium. Sort by start; min-heap on end times.

Graphs (BFS/DFS/topo) (5)

Number of Islands. Count connected components of 1s. Medium. BFS/DFS flood fill.
Clone Graph. Deep-copy an undirected graph. Medium. BFS/DFS + map old→new.
Course Schedule. Can you take all courses (cycle detection)? Medium. Topological sort.
Word Ladder. Shortest transformation sequence. Hard. BFS where neighbors differ by one char.
Pacific Atlantic Water Flow. Cells reachable from both oceans. Medium. Reverse-BFS from each shore.

Backtracking (3)

Subsets. All subsets of a distinct-element array. Medium. Classic backtracking; include/exclude.
Permutations. All permutations. Medium. Used-array backtracking.
Word Search. Does board contain word? Medium. DFS with visited marker; mark/unmark.

Dynamic programming (6)

Climbing Stairs. Ways to reach step n. Easy. Fibonacci recurrence.
Coin Change. Fewest coins to make amount. Medium. dp[a] = 1 + min(dp[a-c]).
House Robber. Max sum with no adjacent. Medium. dp[i] = max(dp[i-1], dp[i-2] + a[i]).
Longest Increasing Subsequence. Medium. O(n²) DP or O(n log n) with tails array.
Edit Distance. Min ops to transform s1 → s2. Hard. 2D DP with insert/delete/replace.
Word Break. Can s be segmented into dictionary words? Medium. dp[i] = any dp[j] && s[j..i] in dict.

Greedy / intervals (3)

Merge Intervals. Merge overlapping. Medium. Sort by start; extend or push.
Non-overlapping Intervals. Min to remove. Medium. Sort by end; keep if start ≥ last kept end.
Jump Game. Can you reach the last index? Medium. Greedy: track max reachable; fail if i > reach.

You've got this. Work through the patterns in Part 6 until recognition is automatic. Run the rapid-fire list (§49) the morning of. And when you sit down to the whiteboard: clarify → example → brute force → optimize → code → test → complexity. Every time. Good luck.

Data Structures & Algorithms — All-Inclusive Study Guide ​

Table of Contents ​

Part 1 — Complexity Analysis (the measurement layer) ​

Part 2 — Linear Data Structures ​

Part 3 — Hierarchical & Specialized Structures ​

Part 4 — Core Algorithms ​

Part 5 — Algorithmic Paradigms ​

Part 6 — Interview Patterns (the toolkit) ​

Part 7 — Java-Specific Cheat Sheet ​

Part 8 — Meta-skills ​

Back matter ​

Interview-Question Coverage Matrix ​

Part 1 — Complexity Analysis ​

1. Big-O, Big-Θ, Big-Ω ​

The precise definitions ​

How interviewers actually use "Big-O" ​

Constants, lower-order terms, and bases ​

Q&A ​

2. Time complexity in practice ​

The class ladder ​

Recognizing each class from code ​

Reading nested / sequential work ​

Complexity of common Java operations ​

Q&A ​

3. Space complexity ​

Auxiliary vs total space ​

Recursion stack counts ​

In-place algorithms ​

Common space-complexity traps ​

Q&A ​

4. Amortized analysis ​

The ArrayList.add example ​

HashMap.put amortized cost ​

The three techniques (brief) ​

What "amortized O(1)" doesn't guarantee ​

Q&A ​

5. Analyzing recursion ​

The recurrence relation ​

Master Theorem (informal) ​

Tree-recursion intuition (the shortcut) ​

Memoization changes the game ​

Q&A ​

Part 2 — Linear Data Structures ​

6. Arrays ​

Fixed arrays vs dynamic arrays ​

Operations and complexity ​

Java specifics ​

Two-pointer & sliding-window scaffolding ​

Common pitfalls ​

Connect to experience ​

Q&A ​

7. Strings ​

Java String internals ​

String pool & intern() ​

StringBuilder vs StringBuffer ​

char[] for in-place algorithms ​

Substrings — watch the cost ​

Common string interview problems ​

Character frequency counting ​

Q&A ​

8. Linked lists ​

Structure & variants ​

Why (and when) you'd ever use one ​

The basic node ​

Reverse a linked list ​

Cycle detection — Floyd's tortoise-and-hare ​

Merge two sorted lists ​

Common linked-list patterns ​

Q&A ​

9. Stacks ​

The LIFO abstraction ​

Java implementations ​

The call-stack analogy ​

Classic stack interview problems ​

Q&A ​

10. Queues & deques ​

The FIFO abstraction ​

Java implementations ​

Basic usage ​

The BFS frontier ​

Data Structures & Algorithms — All-Inclusive Study Guide

Table of Contents

Part 1 — Complexity Analysis (the measurement layer)

Part 2 — Linear Data Structures

Part 3 — Hierarchical & Specialized Structures

Part 4 — Core Algorithms

Part 5 — Algorithmic Paradigms

Part 6 — Interview Patterns (the toolkit)

Part 7 — Java-Specific Cheat Sheet

Part 8 — Meta-skills

Back matter

Interview-Question Coverage Matrix

Part 1 — Complexity Analysis

1. Big-O, Big-Θ, Big-Ω

The precise definitions

How interviewers actually use "Big-O"

Constants, lower-order terms, and bases

Q&A

2. Time complexity in practice

The class ladder

Recognizing each class from code

Reading nested / sequential work

Complexity of common Java operations

Q&A

3. Space complexity

Auxiliary vs total space

Recursion stack counts

In-place algorithms

Common space-complexity traps

Q&A

4. Amortized analysis

The `ArrayList.add` example

`HashMap.put` amortized cost

The three techniques (brief)

What "amortized O(1)" doesn't guarantee

Q&A

5. Analyzing recursion

The recurrence relation

Master Theorem (informal)

Tree-recursion intuition (the shortcut)

Memoization changes the game

Q&A

Part 2 — Linear Data Structures

6. Arrays

Fixed arrays vs dynamic arrays

Operations and complexity

Java specifics

Two-pointer & sliding-window scaffolding

Common pitfalls

Connect to experience

Q&A

7. Strings

Java String internals

String pool & `intern()`

`StringBuilder` vs `StringBuffer`

`char[]` for in-place algorithms

Substrings — watch the cost

Common string interview problems

Character frequency counting

Q&A

8. Linked lists

Structure & variants

Why (and when) you'd ever use one

The basic node

Reverse a linked list

Cycle detection — Floyd's tortoise-and-hare

Merge two sorted lists

Common linked-list patterns

Q&A

9. Stacks

The LIFO abstraction

Java implementations

The call-stack analogy

Classic stack interview problems

Q&A

10. Queues & deques

The FIFO abstraction

Java implementations

Basic usage

The BFS frontier