DSA Demo Examples

Runnable Go programs, one file each, grouped by roadmap phase. Every demo is commented line by line to explain the reasoning, prints its own results, and checks itself where possible. Run any file with go run <file>.go (Go 1.23 or newer); no module setup is needed.

How to use: open a demo with View, read the header comment (it states the problem and the idea), predict the output, then download and run it. Each lesson's Practice Lab suggests a modification to try. Demos are numbered in study order; later phases are added here as they are published.

Phase 1: Foundations

Specification and invariants, complexity by counting and by measurement, recursion and the call stack, and Go's built-in structures. Lessons: Thinking in Algorithms, Complexity Analysis, Recursion, Data Structures Map.

#	Description	Link
1	Find the maximum: specification, loop invariant, table of test cases	View
2	Two Sum three ways: brute force, sort + two pointers, hash map — verified and timed	View
3	Growth rates: operation counts for O(1) through O(2ⁿ)	View
4	Doubling experiment: measure O(n²) vs O(n) and extrapolate	View
5	Recursion trace: watch stack frames push and pop	View
6	Fast power: divide and conquer, O(n) vs O(log n) calls, modular form	View
7	Tower of Hanoi: recursive leap of faith with independent move verification	View
8	Recursion to iteration: explicit stack over a file tree, one million levels deep	View
9	Built-in structures: arrays, slices, maps, container/list, heap, ring	View
10	Choosing a structure: blocklist as slice, sorted slice, and map, timed per workload	View

Phase 2: Core Data Structures

Arrays and array techniques, linked lists, stacks and queues, hash tables, binary trees, and heaps — each built from scratch in Go and verified against a brute-force oracle or invariant check. Lessons: Arrays & Slices, Linked Lists, Stacks & Queues, Hash Tables, Binary Trees & BST, Heaps.

#	Description	Link
11	Slice operations: insert, delete, filter in place, rotate — by hand and with the slices package	View
12	Two pointers: palindromes, pair sum, dedupe, merge, Dutch flag, max water vs brute force	View
13	Sliding window: fixed and variable windows, longest unique substring, shortest sum range	View
14	Prefix sums: O(1) range queries, subarray-sum counting with a map, 2D sums, difference arrays	View
15	Generic singly linked list with head/tail, removal edge cases, and a range iterator	View
16	List techniques: reversal, middle, Floyd cycle detection, remove n-th from end, merge, palindrome	View
17	Doubly linked list with a sentinel: O(1) move-to-front playlist with invariant checks	View
18	Stack applications: bracket matching, RPN evaluation, shunting-yard, undo/redo	View
19	Ring-buffer queue and deque vs the naive slice queue, with allocation counts	View
20	Monotonic stack and deque: next greater, histogram rectangle, window maximum	View
21	Hash map from scratch: FNV-1a, separate chaining, resizing, good vs bad hash	View
22	Hash set with linear probing and tombstones, measured under churn	View
23	Hashing patterns: counting, seen sets, grouping by canonical key, longest consecutive run	View
24	Tree traversals: pre/in/post-order recursive and iterative, level order, sideways print	View
25	Generic BST: insert, three-case delete, ceiling, range queries, shape vs height	View
26	Subtree thinking: diameter, balance, path sum, LCA, mirror, serialize/deserialize	View
27	Binary heap from scratch: sift up/down, O(n) heapify, heapsort with random checks	View
28	container/heap: scheduler with heap.Fix, top-k, k-way merge, running median	View

Phase 3: Core Algorithms

Binary search and its variants, the classic sorting algorithms, graph traversal, and weighted graph algorithms, each checked against a brute-force or slower oracle on random inputs. Lessons: Searching, Sorting, Graph Traversal, Shortest Paths & MST.

#	Description	Link
29	Linear vs binary search: invariant, step-by-step trace, comparisons and timings	View
30	Search bounds: first-true template, lower/upper bound, rotated arrays, peak finding	View
31	Binary search on the answer: integer square root, ship capacity, eating speed, cube root	View
32	Bubble, selection, and insertion sort: comparisons, moves, adaptivity, stability	View
33	Merge sort: recursion trace, bottom-up version, inversion counting, timings	View
34	Quicksort: Lomuto partition, random pivot, three-way partition, quickselect	View
35	Counting sort and LSD radix sort vs slices.Sort	View
36	Sorting in Go: multi-key comparators with cmp.Or, stable sorts, index sorting, the a - b bug	View
37	Graph representations: edge list, adjacency matrix, adjacency list, implicit grid	View
38	BFS: shortest paths, path reconstruction, maze solver, multi-source BFS	View
39	DFS: recursive and iterative, components, directed cycles, bipartite check, islands	View
40	Topological sort: Kahn and DFS postorder, cycle detection, critical path of a build	View
41	Union-find with union by size and path compression vs the naive version	View
42	Dijkstra with container/heap, route reconstruction, Floyd-Warshall oracle, negative-edge failure	View
43	Bellman-Ford: negative weights, negative-cycle extraction, currency arbitrage	View
44	A* vs Dijkstra on a grid: expanded cells drawn, admissible and weighted heuristics	View
45	Minimum spanning tree: Kruskal and Prim vs brute force, 2,000-point complete graph	View

Phase 4: Advanced Algorithms

Algorithm design techniques for optimization problems and the specialised structures behind them. Every demo checks its answers against brute force on random inputs. This section grows one lesson at a time.

Greedy Algorithms

Lesson: Greedy Algorithms.

#	Description	Link
46	Interval scheduling: activity selection vs three wrong rules, fewest rooms, merging, stabbing points	View
47	When greedy fails: coin systems, fractional vs 0/1 knapsack, a 1/2-approximation	View
48	Scheduling by exchange argument: Smith's rule, earliest deadline first, deadlines and profits with union-find	View
49	Huffman coding: tree building, encode and decode, optimality via Kraft's inequality, Shannon-Fano comparison	View

Dynamic Programming

Lesson: Dynamic Programming.

#	Description	Link
50	Memoization and tabulation: Fibonacci call counts, grid paths, cheapest path with route, house robber	View
51	Knapsack family: 0/1 knapsack, loop direction, coin change, combinations vs sequences, subset sum	View
52	Sequence DP: longest increasing subsequence (O(n log n)), LCS, diff, edit distance with script	View
53	Interval and partition DP: matrix chain, burst balloons, word break, palindrome cuts	View
54	Bitmask and state-machine DP: travelling salesman, assignment, stock trading with cooldown	View

Backtracking

Lesson: Backtracking.

#	Description	Link
55	Backtracking template: subsets, permutations, duplicates, combination sum with pruning, parentheses, the aliasing bug	View
56	N-Queens (arrays and bit masks) and Sudoku: pruning, most-constrained-cell order, a puzzle that defeats brute force	View
57	Word search, prefix pruning, letter combinations, palindrome partitions, walking every cell vs a bitmask DP	View
58	Branch and bound: graph colouring with symmetry breaking, knapsack with a fractional bound at capacity over 10^9	View

Advanced Trees

Lesson: Advanced Trees.

#	Description	Link
59	AVL tree: rotations, the four imbalance cases, height bound from Fibonacci, sorted input vs a plain BST	View
60	Treap: split and merge, k-th smallest, rank and range count, sequence mode (insert, delete, rotate at any index)	View
61	Trie: prefix counts, autocomplete, delete, wildcard search, and a binary trie for the largest XOR pair	View
62	Fenwick tree: prefix sums with updates, range add, k-th item, counting inversions	View
63	Segment tree over any operation, lazy range add, descent search, and a sparse table for static minimum	View

String Algorithms

Lesson: String Algorithms.

#	Description	Link
64	Pattern matching: naive, KMP with the prefix function, Z-function, Horspool, smallest period, comparison counts	View
65	Rolling and prefix hashes: Rabin-Karp, arithmetic modulo 2^61-1, longest repeated and common substring, O(1) palindrome test	View
66	Palindromes: expand around centers, Manacher's algorithm, counting, shortest palindrome by adding in front	View
67	Suffix array by prefix doubling, Kasai LCP, pattern search, distinct substrings, longest repeated and common substring	View
68	Aho-Corasick automaton: fail and output links, many patterns in one pass, censoring	View

Advanced Techniques

Lesson: Advanced Techniques.

#	Description	Link
69	Bit manipulation: lowest-bit identities, submask and Gray code enumeration, Gosper's hack, XOR puzzles, a bitset sieve	View
70	Randomized algorithms: biased vs Fisher-Yates shuffle, reservoir sampling, quickselect, Miller-Rabin, Freivalds' check	View
71	Bloom filter and Count-Min sketch: sizing, measured error against theory, heavy hitters in a Zipf stream	View
72	HyperLogLog: distinct counts in 16 KB, accuracy against memory, merging sketches for unions	View

Production Structures

Lesson: Production Structures.

#	Description	Link
73	LRU cache: map plus doubly linked list, TTL with an injected clock, hit ratio against capacity, the scan problem	View
74	Rate limiters: fixed window, sliding log, sliding counter, token bucket, the boundary attack	View
75	Consistent hashing: ring with virtual nodes, keys moved on add and remove, balance, replicas, rendezvous hashing	View
76	Concurrent structures: mutex and atomic counters, sharded map, lock-free stack, worker pool, call collapsing	View