DSA & Coding Patterns — Arrays, Trees, Graphs, DP
A deep-dive on DSA & Coding Patterns — part of a 36-topic evergreen learning series.
Why this session matters
Part of a 36-topic learning series on engineering, ML, and LLM systems. Each session is a 90-minute deep-dive on one topic — designed so anyone can pick it up cold. Every two topics are followed by a revision session with recall prompts and hands-on drills.
Session 03 · SW track 🧩
DSA gets a bad rap as 'interview theater', but the patterns matter: knowing when a problem is really BFS-in-disguise, when to reach for a monotonic stack, or how to spot an interval-scheduling problem, translates directly to writing better production code. This session covers the 15-20 patterns that solve ~80% of real-world algorithm problems.
Pre-read (30 min before session)
Watch 1–2 of these before the deep-dive:
Then skim the NeetCode Roadmap.
Deep-dive (90 min)
1. The 20 patterns (30 min tour)
Two-pointers, sliding window, fast-slow pointers, merge intervals, cyclic sort, in-place linked list reversal, BFS/DFS on trees, topological sort, binary search variants, subsets/permutations, modified binary search, top-K elements, K-way merge, 0/1 knapsack DP, unbounded knapsack DP, LIS, LCS, matrix DP, monotonic stack, prefix sums.
2. Deep-dive: DP (30 min)
Recognizing DP problems (overlapping subproblems + optimal substructure). Bottom-up vs top-down. Space optimization (O(n²) → O(n) with rolling arrays). Classic patterns: 0/1 knapsack, LCS, edit distance, LIS variants.
3. Deep-dive: graph BFS/DFS + topological sort (20 min)
When to use BFS (shortest path in unweighted) vs DFS (path existence, cycle detection). Topological sort via Kahn's or DFS. Union-find for connectivity. Dijkstra for weighted shortest path.
4. Interview strategy (10 min)
Clarify → examples → brute force → optimize → code → test. Talk through your thinking. Ask about constraints (input size determines allowed complexity).
Reading list
- Cracking the Coding Interview — Gayle McDowell (pattern reference)
- NeetCode 150 — https://neetcode.io/practice
- Grokking the Coding Interview patterns (Educative)
Research links
- Competitive Programmer's Handbook (free PDF)
- Codeforces educational rounds
Hands-on drill
Solve NeetCode's Longest Increasing Subsequence — brute force O(2^n) → DP O(n²) → binary search O(n log n). Talk through each step.
Post-session checklist
- Can you explain the sliding-window pattern in 60 seconds?
- Can you explain when to reach for DP vs greedy in 60 seconds?
- Can you explain topological sort via Kahn's algorithm in 60 seconds?
- Did you complete the hands-on drill above?
- Did you write 3 flashcards for tomorrow's recall?
- What's the one thing you'd want to revisit in the next revision session?
What's next
Session 04 continues the series. See the hub page for the full sequence and revision pattern.