Data Structures & Algorithms

These are my notes from grinding ~300 LeetCode problems and reading through 3,700+ problem statements. I've distilled what actually matters for FAANG interviews — the patterns that keep showing up, the data structures you need cold, and the problems worth your time.

The patterns that matter most

After enough problems, you realize there are really only about 12-15 patterns. Everything else is a variation. Here's what I've seen ranked by how often they show up:

The first 5 alone cover probably 60% of what you'll see in interviews.

Data Structures

Arrays

Contiguous memory, O(1) random access. Shows up everywhere.

Things to know cold:

• Subarray — Contiguous elements: [1,3,2] from [5,1,3,2,4]
• Subsequence — Maintains order but not contiguous: [1,3,4] from [5,1,3,2,4]
• Subset — Any combination, order doesn't matter
• Prefix Sum — Precompute cumulative sums for O(1) range queries: prefix[i] = prefix[i-1] + arr[i]
• Kadane's Algorithm — Maximum subarray sum in O(n). Comes up a lot.

Strings

Immutable in Java (String Pool). Use char[] or StringBuilder when you need to modify.

String-specific algorithms (rarely asked directly, but good to know the ideas):

• KMP — Pattern matching in O(n + m) using failure function
• Rabin-Karp — Rolling hash for O(n) average pattern matching
• Z-Algorithm — Z-array for pattern matching in O(n + m)
• Manacher's — All palindromic substrings in O(n)

Hash Map / Hash Set

O(1) average for everything. Half of all "easy" and "medium" problems become trivial once you think "what if I just stored this in a map?"

When to reach for a HashMap:

• Two Sum (store complements)
• Frequency counting
• Grouping (anagrams, patterns)
• Duplicate detection
• Caching (LRU with LinkedHashMap)

Linked Lists

The tricks that come up over and over:

• Two-pointer (slow/fast) — Detect cycle, find middle, find nth from end
• Dummy head node — Simplifies edge cases at the head
• Reversal — Iterative (3 pointers) or recursive. Practice both.

Stack

LIFO. Surprisingly useful — monotonic stacks alone solve a whole class of problems.

Where stacks show up:

• Valid parentheses matching
• Monotonic stack — next greater element, largest rectangle in histogram
• Expression evaluation (postfix, infix to postfix)
• DFS (explicit stack replaces recursion)
• Min stack (track minimum at each level)

Queue

FIFO. The main thing to remember: BFS = queue.

Trees

Binary Tree Properties

BST

Left < parent < right for all nodes.

Self-Balancing BSTs

Traversals

Heap (Priority Queue)

Complete binary tree. Parent >= children (max-heap) or <= children (min-heap).

When to use: anything with "top K", "kth largest", "merge K sorted", or "running median."

Trie (Prefix Tree)

Use for: autocomplete, spell checker, word search, IP routing (longest prefix match), word break.

Graph Representations

Use adjacency list for almost everything. Matrix only when the graph is dense or you need O(1) edge checks.

Disjoint Set (Union-Find)

Use for: Kruskal's MST, cycle detection (undirected), connected components, accounts merge.

Data Structures in Real Systems

Algorithm Patterns (with templates)

Two Pointers

Recognize it: Sorted array, finding pairs, removing in-place, palindromes.

Sliding Window

Recognize it: "Longest/shortest subarray/substring with constraint X."

Template I use:

int left = 0;
for (int right = 0; right < n; right++) {
    // expand: add arr[right] to window state
    while (window is invalid) {
        // shrink: remove arr[left] from window state
        left++;
    }
    // update answer
}

Binary Search

Recognize it: Sorted data, or "find minimum X such that..." (search on answer space).

Binary search on answer space is underrated. Problems like Koko Eating Bananas, Split Array Largest Sum, Ship Packages — they all follow the same template.

DFS

Recognize it: Explore all paths, detect cycles, topological sort, connected components.

BFS

Recognize it: Shortest path (unweighted), level-order, "minimum steps to reach X."

Backtracking

Recognize it: "Generate all...", "find all combinations/permutations", constraint satisfaction.

Template:

void backtrack(state, choices) {
    if (isGoal(state)) {
        result.add(copy(state));
        return;
    }
    for (choice : choices) {
        if (isValid(choice)) {
            make(choice);
            backtrack(state, remaining);
            undo(choice);
        }
    }
}

Pruning makes or breaks your runtime: sort candidates, skip duplicates, check constraints early.

Dynamic Programming

Recognize it: "Find min cost / max value / number of ways" + choices at each step that affect future decisions. If greedy fails (you can find a counterexample), it's probably DP.

Categories

My approach for every DP problem

1. Define state — What uniquely describes a subproblem?
2. Recurrence — How does current relate to smaller subproblems?
3. Base cases — What's trivially solvable?
4. Iteration order — Dependencies must be computed first
5. Space optimize — Can you go from 2D to 1D?

Greedy

Recognize it: Local optimal → global optimal. You need to prove it works (exchange argument or show no counterexample).

Graph Algorithms

Sorting

Java: Arrays.sort() = Dual-Pivot Quicksort for primitives, TimSort for objects.

Complexity Cheat Sheet

Operations by Data Structure

*O(1) with reference to node; O(n) to find it.

Space Complexity

Math & Bit Manipulation

Number Theory

Bit Manipulation

How to pick the right approach