Algorithms for Interviews and Contests in C++

What you will be able to do

• Read a problem's constraints and pick an algorithm whose running time fits
• Implement BFS, DFS, Dijkstra, minimum spanning trees and union-find correctly and from memory
• Formulate dynamic programming solutions from a state, a transition and an order
• Use binary search on the answer, two pointers, prefix sums, Fenwick trees and segment trees
• Apply hashing, KMP and the Z-function to string problems
• Test a solution against a brute force with a stress test before trusting it
• Follow a repeatable process for problems you have never seen

Who it is for

• Students and job-seekers preparing for coding interviews
• Contest beginners moving towards Codeforces, AtCoder, USACO or ICPC-style problems
• Developers who want to refresh their algorithms in modern C++ rather than in older dialects
• Anyone who can code a loop but freezes when a problem has no obvious solution

Before you start

• C++ Fundamentals
• STL & Algorithms
• Templates & Generic Programming

The course project

Instead of one big program, you build a personal solution notebook. Every lesson ends with original problems (statement, constraints, a solution in modern C++ and a stress test against a brute force). Each program takes its input from an embedded sample, so it runs in the browser exactly as it would on a judge reading standard input. The last lesson turns the notebook into a process for problems you have not seen.

Lessons

1. 1Complexity in Practice: Reading Constraints and Choosing an AlgorithmFree sampleRead a problem's limits before you think about code, turn them into a step budget, and pick the algorithm that fits, with operation counts instead of guesses.45 min
2. 2Fast I/O, Contest Templates and Stress TestingRead and write large inputs without wasting time, keep a small modern C++ template, and catch wrong answers before the judge does with a stress-test harness.40 min
3. 3Graphs: BFS, DFS, Connected Components and Topological SortStore a graph the right way, then use breadth-first and depth-first search for fewest-step routes, grids, components, two-colorings, build orders and cycles, all in O(V + E).40 min
4. 4Shortest Paths: Dijkstra, 0-1 BFS, Bellman-Ford and Floyd-WarshallFour shortest-path algorithms, the constraints that pick one, and the bugs that make them slow or wrong without any visible error, each shown failing and then fixed.50 min
5. 5Union-Find and Minimum Spanning TreesA disjoint-set structure that answers "are these connected?" in nearly constant time, and the Kruskal and Prim algorithms that use it to connect a graph at minimum cost.40 min
6. 6Dynamic Programming I: PatternsA five-step method for dynamic programming and the patterns it produces, from coin change and knapsack to LIS, LCS, edit distance and grid paths, each checked against a brute force.40 min
7. 7Dynamic Programming II: Bitmasks, Intervals, Trees and DigitsFour state shapes that cover most hard DP problems (a set as a bitmask, an interval, a subtree and a digit position), each with code, an operation count and a stress test.40 min
8. 8Binary Search on the Answer, Two Pointers and SweepingBinary search written from one invariant, searching over the answer instead of an array, sliding windows, meet in the middle and sweep lines, each stress tested against a brute force.40 min
9. 9Prefix Sums, Fenwick Trees and Segment TreesAnswer many range queries fast. Prefix sums and difference arrays, a sparse table for minimums, a Fenwick tree, and segment trees over any monoid with lazy propagation, all stress tested.30 min
10. 10String Algorithms: Hashing, KMP and the Z-FunctionFind every occurrence of a pattern in linear time, read periods off the prefix function, and compare substrings in O(1) with a rolling hash that is hard to break.45 min
11. 11Number Theory and Bit TricksModular arithmetic without overflow, inverses, sieves, binomial coefficients modulo a prime, the Chinese remainder theorem and the C++20 bit functions, each checked against brute force.45 min
12. 12The Playbook: A Process for Problems You Have Not SeenA checklist for unfamiliar problems, a table from problem signals to the techniques of this course, and four original problems solved out loud, dead ends included.30 min