DSA Interview Prep
A personal study log of DSA interview prep, tutored by Claude. Each lesson covers a topic through concept explanation, hands-on implementation, and classic interview problems.
Lessons
-
Lesson 1: Diagnostic Assessment
Eight classic interview problems across heaps, graphs, DP, and data structure design — used to identify gaps before building a study plan. Result: strong first-principles reasoning, weak pattern recognition.
-
Lesson 2: Heaps
Heap internals (array representation, sift-up/down, O(n) heapify) plus a generic TypeScript implementation. Applied to Meeting Rooms II and Find Median from Data Stream, with a lightning round to calibrate heap vs. heap-adjacent patterns.
-
Lesson 3: BFS and DFS on Graphs and Grids
Covered BFS (queue) and DFS (recursion/stack) traversal patterns on graphs and grids. Key takeaway: BFS guarantees shortest path in unweighted graphs because distance from source equals level depth; mark nodes visited on enqueue, not dequeue.
-
Lesson 4: Dynamic Programming
Introduced DP fundamentals — overlapping subproblems, optimal substructure, recurrence — and solved Climbing Stairs and House Robber. Key takeaway: define dp[i] precisely and derive the recurrence before coding.
-
Lesson 5: Dynamic Programming (continued): Coin Change & Circular House Robber
Covered unbounded knapsack via Coin Change and extended House Robber to a circular layout. Key takeaway: DP state must represent the best answer to a complete subproblem, not a constrained one.
-
Lesson 6: 2D Dynamic Programming (LCS)
Reviewed K Closest Points (heaps) and Walls & Gates (multi-source BFS), then introduced 2D DP with Longest Common Subsequence — derived the two-case recurrence and filled the table correctly.
-
Lesson 7: 2D Dynamic Programming — Unique Paths & Edit Distance
Covered Unique Paths (with and without obstacles) and derived the Edit Distance recurrence. Key insight: 2D DP tables need a +1 row and column for empty-string base cases.