Data Structures & Algorithms

1. Introduction & Why DSA Matters

Data Structures and Algorithms (DSA) means picking the right representation for data and a procedure that matches your constraints. I keep tripping over it—latency budgets, interview loops, and code nobody profiled. The wrong structure or an overly loose bound is how something “fine locally” turns painful under load.

2. Complexity Analysis — The Language of Performance

Before the structures themselves, it helps to agree on Big-O notation: an asymptotic upper bound on how work grows with input size n.

2.1 Big-O, Big-Ω, and Big-Θ

• O(f) — upper bound (worst-case ceiling).
• Ω(f) — lower bound (best-case floor).
• Θ(f) — tight bound (both upper and lower).

2.2 Amortized Complexity

The average cost per operation across a sequence. A dynamic array's push is O(1) amortized even though occasional resizes are O(n) — the cost is spread over many cheap operations.

3. The Mental Model of DSA

Every data structure represents a tradeoff. There is no "best" structure — only the best for a specific access pattern.

4. Arrays & Dynamic Arrays

An array is a contiguous block of memory holding fixed-size elements indexed by integer offsets. Because indexing is computed as base + i × sizeof(T), access is O(1). This locality also produces extreme cache efficiency — arrays are usually the fastest structure for sequential workloads despite their humble interface.

4.1 Dynamic Array Growth Strategy

Dynamic arrays (Python list, Java ArrayList, C++ std::vector) double their capacity when full, giving amortized O(1) append:

5. Strings

Strings are arrays of characters but with their own algorithmic universe. Most languages make strings immutable — operations that "modify" return new strings. Use a string builder (StringBuilder / list-then-join) when concatenating in loops to avoid O(n²) behavior.

5.1 Essential String Algorithms

6. Linked Lists

A linked list trades O(1) random access for O(1) insertion/deletion anywhere, given a reference. Each node holds data plus a pointer to the next node (and previous, for doubly linked).

6.1 Classic Linked List Tricks

• Fast/slow pointers (Floyd's tortoise & hare) — detect cycles, find midpoint.
• Reverse in place — iterate maintaining prev/curr/next pointers.
• Dummy head node — eliminates edge cases at the front of the list.
• Merge two sorted lists — basis of merge sort on lists.

# Reverse a singly linked list
def reverse(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

7. Stacks — LIFO

Last-In-First-Out. Imagine a stack of plates: you push onto and pop from the top. Used in: function call stacks, undo systems, expression parsing, DFS, backtracking.

7.1 Classic Stack Patterns

• Balanced parentheses — pair every opener with its closer.
• Monotonic stack — next-greater / next-smaller element in O(n).
• Expression evaluation — infix → postfix conversion (shunting yard).
• Min stack — O(1) min with auxiliary stack of running minima.

8. Queues & Deques — FIFO

First-In-First-Out. Used in: BFS, task scheduling, message buffers, OS kernels.

A deque (double-ended queue) allows push/pop from both ends in O(1). A priority queue orders by priority instead of arrival time (usually backed by a heap).

9. Hash Tables — The Workhorse

Hash tables map keys to values in O(1) average time by transforming keys into array indices through a hash function. They are arguably the most important data structure in everyday engineering — they underpin caches, sets, dictionaries, symbol tables, deduplication, and indexing.

9.1 Collision Resolution

9.2 Load Factor & Resizing

When load factor (n / capacity) exceeds a threshold (typically 0.75), the table doubles and re-hashes everything. This is O(n) but amortized O(1) per insert.

10. Trees

A tree is a connected, acyclic graph with a designated root. Each node has 0 or more children. Trees model hierarchies (file systems, DOM), enable fast search (BSTs), and back storage engines (B-Trees).

10.1 Tree Traversals

10.2 Balanced Trees

11. Heaps & Priority Queues

A binary heap is a complete binary tree satisfying the heap property: in a min-heap, every parent ≤ its children; in a max-heap, parent ≥ children. Stored as an array; for index i, children are 2i+1, 2i+2; parent is (i-1)/2.

11.1 When to Use a Heap

• Top-K frequent / largest / smallest in a stream
• Dijkstra's / Prim's algorithm (priority queue)
• Median of a stream (two heaps)
• Event scheduling (next event by time)
• Huffman coding

12. Tries (Prefix Trees)

A trie stores strings character-by-character in a tree, sharing common prefixes. Lookup, insert, and prefix queries run in O(L), independent of the number of stored strings.

Use Tries For: autocomplete, spell-check, IP routing (radix trie), DNA k-mers, Aho–Corasick multi-pattern matching.

13. Graphs

A graph G = (V, E) is a set of vertices V connected by edges E. Graphs are the most expressive structure in CS — almost any real-world entity-relationship problem reduces to one. Examples: social networks, road maps, dependency resolution, web crawl, neural networks, blockchain.

0: [1, 2]
1: [0, 3]
2: [0, 3]
3: [1, 2]

   0 1 2 3
0 [0 1 1 0]
1 [1 0 0 1]
2 [1 0 0 1]
3 [0 1 1 0]

14. Union–Find (Disjoint Set Union)

A Union–Find structure maintains a collection of disjoint sets supporting find(x) (which set?) and union(x,y) (merge sets). With path compression + union by rank, every operation runs in nearly O(1) — formally O(α(n)), the inverse Ackermann function.

Used For: Kruskal's MST, network connectivity, dynamic graph problems, "is this a cycle?" checks.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank   = [0]*n
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # path compression
            x = self.parent[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        return True

15. Segment Tree & Fenwick Tree (BIT)

Range query structures. A segment tree answers range-sum, range-min, range-gcd, etc. in O(log n) with O(log n) point or range updates. A Fenwick tree (BIT) handles prefix sums with simpler code but only invertible operations.

16. Sorting Algorithms

16.1 The Comparison Lower Bound

This is why counting/radix/bucket sort can beat n log n — they exploit the structure of the keys (integers in a bounded range), not arbitrary comparison.

16.2 Quicksort — The Industrial Workhorse

def quicksort(arr, lo, hi):
    if lo < hi:
        pivot = partition(arr, lo, hi)
        quicksort(arr, lo, pivot - 1)
        quicksort(arr, pivot + 1, hi)

def partition(arr, lo, hi):
    p = arr[hi]; i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= p:
            i += 1; arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[hi] = arr[hi], arr[i+1]
    return i + 1

17. Searching Algorithms

17.1 Linear vs Binary Search

Linear search: O(n). Binary search: O(log n) but requires sorted data.

# Canonical binary search — find target index, else -1
def bsearch(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2     # (lo + (hi - lo)//2) avoids overflow in fixed-width langs
        if arr[mid] == target: return mid
        elif arr[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return -1

17.2 The Binary-Search-on-Answer Pattern

When you can phrase a problem as "what's the minimum/maximum X such that condition(X) is true?" and the predicate is monotonic, you can binary search the answer space — even if it's not an array.

Examples: minimum capacity to ship in D days, smallest pages to allocate, Koko eating bananas, find peak element.

18. Recursion & Backtracking

Recursion is a function that calls itself on smaller instances. Every recursive solution needs:

1. Base case — the trivial input that returns directly.
2. Recursive case — break the problem into smaller subproblems.
3. Progress — guarantee the recursion reaches the base case.

18.1 The Recursion Tree

18.2 Backtracking Template

def backtrack(state):
    if is_goal(state):
        results.append(copy(state))
        return
    for choice in candidates(state):
        if is_valid(state, choice):
            apply(state, choice)        # make
            backtrack(state)
            undo(state, choice)         # unmake — the heart of backtracking

Classic backtracking problems: N-Queens, Sudoku, permutations, combinations, subset sum, word search, graph coloring.

19. Divide & Conquer

Three steps:

1. Divide — split into smaller, independent subproblems.
2. Conquer — solve each recursively.
3. Combine — merge subsolutions into the final answer.

19.1 The Master Theorem

For T(n) = a·T(n/b) + f(n):

Classic D&C algorithms: Merge sort, Quicksort, Karatsuba multiplication, Strassen matrix multiply, FFT, closest pair of points.

20. Dynamic Programming

DP = recursion + memoization. It solves problems with two properties:

1. Optimal substructure — the optimal solution contains optimal solutions to subproblems.
2. Overlapping subproblems — the same subproblem appears many times.

20.1 Top-Down vs Bottom-Up

def fib(n, memo={}):
    if n < 2: return n
    if n not in memo:
        memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

def fib(n):
    if n < 2: return n
    a, b = 0, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

20.2 The Five Canonical DP Categories

20.3 DP Strategy in Five Steps

1. Define the state: what does dp[i][j] mean in plain English?
2. Write the recurrence: how does the current state relate to smaller states?
3. Identify base cases.
4. Determine the iteration order (dependencies must be computed first).
5. Optimize space: often only the previous row/column is needed.

21. Greedy Algorithms

A greedy algorithm makes the locally optimal choice at each step, hoping it leads to a globally optimal solution. It works only when the problem has the greedy-choice property + optimal substructure.

When greedy works, it's usually faster and simpler than DP. When it doesn't, it produces wrong answers silently — always prove correctness (exchange argument, matroid theory, or induction).

22. Graph Algorithms

22.1 Traversals: BFS & DFS

from collections import deque
def bfs(g, src):
    seen, q = {src}, deque([src])
    while q:
        u = q.popleft()
        for v in g[u]:
            if v not in seen:
                seen.add(v); q.append(v)

def dfs(g, u, seen):
    seen.add(u)
    for v in g[u]:
        if v not in seen:
            dfs(g, v, seen)

22.2 Shortest-Path Algorithms

22.3 Minimum Spanning Tree

• Kruskal's — sort edges, add if it doesn't form a cycle (Union-Find). O(E log E).
• Prim's — grow tree from a vertex, pick lightest crossing edge (heap). O(E log V).

22.4 Topological Sort

Linear ordering of a DAG such that every edge u→v has u before v. Used in: build systems (Make, Bazel), course prerequisites, dependency resolution (npm, pip).

• Kahn's algorithm (BFS): repeatedly remove zero-in-degree nodes.
• DFS-based: reverse post-order of DFS.

22.5 Strongly Connected Components & Network Flow

• Tarjan / Kosaraju — find SCCs in O(V+E).
• Ford–Fulkerson / Edmonds–Karp / Dinic's — max flow, min cut, bipartite matching.

23. Fifteen coding patterns I still drill

Most interview (and plenty of contest) problems still snap to one of these shapes. Naming the shape early beats rewriting from scratch.

24. Problem-Solving Strategy & Interview Playbook

24.1 The UMPIRE Framework

24.2 How to Approach Any New Problem

1. Restate & clarify — what are inputs, outputs, constraints? n = 10? 10⁵? 10⁹?
2. Brute force first — get any correct algorithm, even if O(n²) or O(2ⁿ).
3. Identify the bottleneck — what's the slow step in brute force?
4. Optimize with a data structure or pattern that attacks the bottleneck.
5. Verify edge cases: empty input, one element, duplicates, negatives, overflow, max size.
6. Test with examples: walk through paper or in REPL.

24.3 Constraint-Based Algorithm Hints

24.4 Interview Communication Checklist

• Think out loud — silence is the enemy.
• Discuss tradeoffs before committing to one approach.
• State complexity before coding (so you can adjust if it's not good enough).
• Name variables semantically: left, right, count beats a, b, c.
• Pre-emptively call out edge cases.
• After coding, test on at least one normal + one edge case.

• Don't jump to code before clarifying the problem.
• Don't over-optimize prematurely; correctness first.
• Don't ignore complexity discussion — it's half the grade.
• Don't write deeply nested code — extract helpers.

25. Data Structure Picker — Decision Tree

26. Mastery Roadmap — Beginner to Expert

26.1 Practice Strategy

• Quality over quantity: 200 deeply understood problems > 1000 skimmed.
• Pattern-driven: pick a pattern, solve 8–12 problems in it, then move on.
• Spaced repetition: re-solve old problems after 1 week / 1 month / 3 months.
• Time-boxed: 30 minutes brainstorming, then read the editorial — don't grind for hours.
• Re-implement: code each pattern from scratch at least 3 times until muscle memory.
• Mock interviews: at least 10 timed full-difficulty mocks before a real interview.

26.2 Curated Problem Tracks

• NeetCode 150 / 250 — pattern-organized; the gold standard.
• Blind 75 — minimum viable preparation.
• Striver's SDE Sheet — broad, balanced.
• LeetCode Top Interview 150 — frequency-weighted.
• Codeforces / AtCoder — for algorithmic depth beyond interviews.

26.3 Recommended Languages

27. References & Further Reading

Narrative and diagrams in §1–§26 are my own synthesis unless noted inline; §27 is where I point people for primary texts and courses. Author: Linh Truong · LinhTruong.com.

27.1 Foundational Textbooks

• Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms (CLRS), 4th ed.
• Sedgewick & Wayne — Algorithms, 4th ed.
• Tim Roughgarden — Algorithms Illuminated, vols. 1–4.
• Skiena — The Algorithm Design Manual, 3rd ed.
• Kleinberg & Tardos — Algorithm Design.
• Erickson — Algorithms (open-access).

27.2 Interview-Focused

• Gayle Laakmann McDowell — Cracking the Coding Interview.
• Aditya Bhargava — Grokking Algorithms.
• Educative — Grokking the Coding Interview Patterns.
• Antti Laaksonen — Competitive Programmer's Handbook (free).

27.3 Online Resources

• cp-algorithms.com — canonical competitive programming reference.
• neetcode.io — pattern-driven video explanations.
• visualgo.net — interactive algorithm visualizations.
• USACO Guide — structured curriculum from bronze to platinum.
• MIT OCW 6.006 / 6.046 — free university courses.

27.4 Beyond Interviews

• Demaine — Advanced Data Structures (MIT 6.851).
• Goodrich, Tamassia — Data Structures and Algorithms in C++/Java/Python.
• Mehlhorn & Sanders — Algorithms and Data Structures: The Basic Toolbox.
• Knuth — The Art of Computer Programming, vols. 1–4A.