Data Structures & Algorithms

The six growth classes every interview mentions — O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) — and how to spot each one in code.

Time isn't the only cost — memory grows too. In-place vs copying, O(1) vs O(n) space, and the space-for-time trade at the heart of this course.

No new concepts — just reps. Classify real code snippets by time and space complexity until it's automatic.

Where a Python list's items actually live in memory, and why grabbing items[5000000] takes exactly one step.

append vs insert(0), pop() vs pop(0), and why `in` quietly scans everything — the complexity of every list operation you use.

Why building a string with += in a loop is secretly O(n²), and how ''.join() fixes it — the most common real-world performance bug.

Your first named interview pattern: two index variables walking an array — palindromes in O(n) time and O(1) space, pair-hunting in sorted data.

Best 7-day sales streak in a year of data — without recomputing each window. The add-one-drop-one pattern that turns O(n·k) into O(n).

No new concepts — mixed reps across list costs, string building, two pointers, and sliding windows, unlabeled like a real interview.

Why `key in my_dict` is O(1) while `x in my_list` is O(n) — the hash function, the coat-check ticket, and the structure behind Python's dict and set.

The counting pattern behind a hundred interview problems: build a value→count dictionary in one pass with .get(key, 0).

The set as a yes/no memory: first-duplicate in O(n), dedupe, and the seen-set pattern that will follow you to graph algorithms.

The most famous interview question in the world, and the mindset shift that solves it: store what you've seen, look up what you need.

Why O(1) says 'on average', what happens when two keys hash to one slot, and why a list can't be a dictionary key.

No new concepts — frequency maps, seen sets, complements, canonical keys, and the O(n²)→O(n) upgrade, all unlabeled.

A structure with no lockers at all: each item points to the next, wherever it lives. The Node class, and the trade every structure makes.

The while-loop template that underlies every linked-list algorithm: current = head, walk until None, don't lose the head.

The O(1) payoff: insert at the head, splice into the middle, and delete by skipping — plus the order-of-operations rule that prevents lost chains.

The most famous linked-list interview question, solved in place with three pointers: prev, current, and the lifeline next_node.

The tortoise and the hare: find the middle in one pass, and detect infinite cycles with two runners and zero extra memory.

No new concepts — traversal, pointer surgery, reversal, and runners, mixed into interview-style traces.

The plate stack: push and pop from the top only. Why undo, back buttons, and function calls all run on LIFO discipline.

The valid-parentheses problem — the interview's favorite stack question — and the open-push, close-pop-and-match choreography that solves all nesting problems.

First in, first out: fair lines, the list's front-removal trap (again), and collections.deque — O(1) at both ends.

The queue's superpower: processing anything in waves — round-robin scheduling, and the level-by-level exploration that becomes BFS.

No new concepts — LIFO vs FIFO discipline, bracket matching, deque choices, and exploration order, unlabeled.

Russian dolls: solve a problem by solving a smaller copy of it. Base cases, recursive cases, and your first recursive functions.

Where waiting calls physically live: stack frames, the before/after print trick, RecursionError, and recursion's hidden memory bill.

Recursion's home turf: nested data that loops can't flatten, two-branch fibonacci, and how innocent code explodes into O(2ⁿ).

The notebook trick: cache every answer in a dict, check before computing — and watch fib collapse from O(2ⁿ) to O(n).

Generating every subset with include/exclude decisions — the choose, explore, un-choose choreography behind mazes, Sudoku, and N-Queens.

No new concepts — base cases, stack traces, memo hits, and undo choreography, mixed and unlabeled.

The guessing game from lesson 1 becomes a real algorithm: O(log n) search — and the sorted-data contract that makes it legal.

Knuth called it 'surprisingly hard to get right'. The three classic landmines — <= vs <, mid±1, and the infinite loop — defused one by one.

Selection, bubble, and insertion sort — why they're quadratic, why insertion sort refuses to die, and what 'stable' means.

Split in half, sort each half, merge — recursion delivers O(n log n). Plus Timsort: the insertion/merge hybrid inside sorted().

Sorting as a strategy: paying O(n log n) to unlock two pointers, neighbor checks, and binary search — and recognizing when a hash map is better.

No new concepts — binary search traces, sort mechanics, complexity arithmetic, and hash-vs-sort strategy calls.

Folders, org charts, HTML, and family trees share one shape. Roots, leaves, parents, children — and the TreeNode class.

Visiting every node in a structure that forks: preorder, inorder, postorder — one function, three placements of a single line.

The queue meets the tree: level-order traversal, grouping nodes by level, and the DFS-vs-BFS decision.

The tree that stays sorted: the BST rule, O(log n) search and insert, the inorder payoff, and the balance catch.

No new concepts — traversal traces, BST reasoning, height computation, and DFS/BFS strategy calls, unlabeled.

Subway maps, friendships, the web: nodes and edges without tree rules. Directed vs undirected, and the adjacency list.

Recursion + the visited set: reachability, the visited-check placement, and why graph DFS is O(nodes + edges).

The wave meets the network: BFS distance tracking, why the first arrival is the shortest route, and degrees of separation.

The interview's favorite disguise: 2-D grids where neighbors are computed, not stored — flood fill, island counting, and maze escapes.

How many separate networks hide in one graph? The scan-and-claim pattern, friend circles, and a cycle-detection preview.

No new concepts — adjacency lists, DFS/BFS choices, grid adapters, components, and costume-spotting, unlabeled.

Dynamic programming demystified: the staircase problem, top-down memo vs bottom-up table, and why you already know half of DP.

DP's most useful shape: at each element, take it or skip it — max() enters the recurrence, and a whole problem family unlocks.

The two fingerprints — overlapping subproblems and optimal substructure — plus the trigger phrases and a four-step recipe for any DP problem.

Grab the best now and never look back: the coin-change trap, why US coins hide it, and how to tell safe greed from wishful thinking.

The six-phase method for any coding interview: clarify, example, brute force first, optimize with pattern triggers, code narrating, test adversarially.

The whole course as a decision guide: trigger → pattern → complexity, plus drills to make the mapping reflexive.

One real FAANG question walked through the full playbook — brute force to O(n²) to O(n) — with every module signing its contribution. Then: where to go next.