Master Data Structures and Algorithms

The Python building blocks every DSA solution is written with: collections, functions, classes, iterators, and the math that shows up in interviews.

Big O, Ω and Θ, best/average/worst cases, amortized analysis, recursive complexity and the Master Theorem — the language every interview answer is graded in.

Contiguous memory, O(1) indexing, and the traversal, insertion, rotation and Kadane techniques that power a third of all interview questions.

Immutable character arrays: palindromes, anagrams, frequency counting, substring vs subsequence, and the classic pattern-matching algorithms.

Nodes and pointers instead of contiguous memory: O(1) splicing, reversal, fast/slow pointers, cycle detection, and the LRU-cache design pattern.

Last-in-first-out in O(1): balanced parentheses, expression evaluation, min-stack design, and the gateway to monotonic-stack patterns.

First-in-first-out processing: deque mechanics, circular buffers, queue-with-stacks, priority-queue preview, and why BFS is a queue wearing a trench coat.

O(1) average lookup by key: hash functions, collision handling by chaining and open addressing, and the frequency/two-sum/grouping patterns built on top.

Functions that call themselves: base cases, the call stack, recursion trees, memoization, divide & conquer — and the discipline that stops infinite loops.

From bubble to quick sort with side-by-side animations: how each algorithm moves data, when O(n²) is fine, why O(n log n) is the wall, and how counting sort tunnels under it.

Linear scan to binary search and beyond: lower/upper bounds, search-insert position, rotated arrays, and 'binary search on the answer'.

Systematic trial-and-error over a decision tree: choose, explore, un-choose. Subsets, permutations, combinations, N-Queens, and Sudoku — with pruning that turns brute force into feasible.

Take the locally optimal choice at each step and prove it stays globally optimal: interval scheduling, jump game, Huffman coding — and how to know when greedy is even valid.

Break a problem into overlapping subproblems and reuse their answers: the memoization → tabulation → space-optimization progression, taught on Fibonacci, coin change, knapsack, LCS and edit distance.

Integers as arrays of bits: AND/OR/XOR/shifts, the classic tricks (clear lowest set bit, XOR to cancel pairs), bitmasks, and O(1) set operations.

The vocabulary every tree question assumes: root, leaf, height vs depth, levels, subtrees, and balanced vs complete vs full shapes.

At most two children per node — and the traversal toolkit (pre/in/post/level order), height, diameter, LCA, and view problems built on it.

The ordering invariant — left < node < right — and the O(h) search/insert/delete, validation, kth-smallest, and floor/ceiling operations it unlocks.

Complete trees in arrays with parents ≤ children: O(1) minimum, O(log n) push/pop, O(n) heapify — and the top-k / k-way-merge / running-median patterns.

One character per edge, shared prefixes shared once: O(L) insert/search independent of dictionary size, prefix search, autocomplete, and XOR tries.

Vertices, edges, adjacency lists — and the two traversals (BFS, DFS) that solve connected components, shortest unweighted paths, cycle detection, and topological sort.

Near-O(1) dynamic connectivity: merge groups and query membership with path compression and union by rank — the engine behind Kruskal, account merging, and cycle detection.

Weighted-graph machinery: Dijkstra, Bellman-Ford, Floyd-Warshall, Prim and Kruskal MSTs — plus a map of SCCs, bridges, and articulation points.

Two indexes replacing nested loops: converging ends on sorted data, read/write partitioning, and fast/slow traversal — O(n²) → O(n).

Maintain a contiguous window and update its state incrementally: fixed-size averages to variable-size 'longest substring' problems, all in O(n).

Precompute running totals once, answer any range-sum in O(1) — plus the hash-map trick for subarray-sum counting and the difference array for bulk range updates.

A stack kept sorted by evicting violators: next-greater-element, daily temperatures, and histogram problems in one O(n) pass.