Algorithms & Data Structures¶

Complexity & Theory¶

complexity analysis - Big-O notation, time/space complexity, analysis patterns for loops and recursion
amortized analysis - Average cost per operation over sequences, dynamic array example
complexity classes - P, NP, NP-complete, NP-hard, reductions between problems

sorting algorithms - Comparison table of all sorts, insertion/merge/quick/radix sort with code
searching algorithms - Linear search, binary search, KMP string matching
two pointer technique - Two-sum, subsequence check, convergent and parallel pointer patterns

dynamic programming fundamentals - DP concepts, memoization vs tabulation, recurrence identification
dp sequence problems - LCS, edit distance, LIS, word break, interleaving strings
dp optimization problems - Knapsack, coin change, house robber, rod cutting, matrix chain
dp grid problems - Partition problem, maximal square, counting paths, combinatorics DP

graph representation - Adjacency list vs matrix, terminology, operation complexity trade-offs
graph traversal bfs dfs - DFS and BFS with code, implicit graphs, multi-source BFS, grid problems
trees and binary trees - Tree definitions, binary tree traversals, spanning trees

shortest path algorithms - Dijkstra, Bellman-Ford, Floyd-Warshall, DAG shortest path, Johnson's
minimum spanning trees - Prim's and Kruskal's algorithms, cut property
topological sort - DFS-based and Kahn's algorithm, critical path, DAG applications
network flow - Max-flow min-cut, Ford-Fulkerson, Edmonds-Karp, Dinic's, bipartite matching
union find - Disjoint set union with path compression and union by rank

graph coloring - Chromatic number, bipartite check, greedy coloring, NP-completeness
eulerian hamiltonian paths - Euler trails/circuits, Hamiltonian paths, Hierholzer's algorithm
traveling salesman problem - TSP exact (Held-Karp) and approximation (nearest neighbor, Christofides)

backtracking - Systematic exploration of solution space by building candidates incrementally and abandoning
bit manipulation - Operations on individual bits of integers
data structures fundamentals - Core data structure operations and complexity analysis - arrays, sorted arrays with binary search
dynamic programming - Recursion fundamentals, memoization (top-down), bottom-up tabulation, and recognizing DP
greedy algorithms - Build solutions incrementally by making the locally optimal choice at each step
hash tables - Data structure mapping keys to values via hash function
heap priority queue - Binary heap: complete binary tree satisfying heap property
problem patterns - Systematic approach to algorithm problems - the 7-step interview process, common patterns
recursion fundamentals - Function that calls itself to solve smaller instances of the same problem
sliding window - Maintain a window (contiguous subarray/substring) that slides across input, expanding and shrinking
string algorithms - Algorithms for string searching, matching, and manipulation
trees and graphs - Binary search trees, heaps/priority queues, tries (prefix trees), graph representation, and