Data Structures & Algorithms in C++

Crack the coding interview in C++, the language of competitive programming: build every data structure and master every pattern from scratch, from arrays and hashing to graphs and dynamic programming, compiled and graded with g++.

10 projects, 305 hands-on levels, run in your browser.

Syllabus

Complexity, Arrays & Hashing: Every interview starts here. Reason about cost with Big-O, get fluent with the array techniques that show up everywhere (prefix sums, Kadane, in-place two pointers), then unlock the single most useful interview tool: the hash map. In C++ that means std::vector, std::unordered_map, and std::unordered_set. By the end you turn brute-force O(n^2) scans into clean O(n) solutions.
Two Pointers & Sliding Window: Two of the highest-yield interview patterns, in depth. Two pointers walk an array from both ends or in the same direction to replace nested loops with a single O(n) pass. Sliding windows track a contiguous run that grows and shrinks, turning substring and subarray problems from O(n^2) into O(n). This project works through the opposite-end and in-place two-pointer moves, fixed and variable windows, windows backed by frequency maps, and a synthesis chapter of the classics.
Stacks & Queues: Two simple structures with outsized interview value. A stack (last in, first out) powers matching, parsing, and the monotonic-stack pattern that answers 'next greater' questions in O(n). A queue (first in, first out) and a deque drive streaming and sliding-window problems. Build them with std::stack, std::queue, and std::deque, and use them to solve the classics.
Binary Search & Sorting: Halving the search space is the second great interview idea after hashing. Master binary search and its boundary variants, the powerful 'binary search on the answer' pattern, search in rotated and 2D arrays, the classic sorting algorithms built from scratch, and the problems that sorting unlocks. Deepened with extra chapters on answer-search and harder variants.
Linked Lists: Pointers, made concrete. A linked list is nodes joined by next-pointers, and the interview classics live here: reversal, the fast-and-slow two-pointer trick for cycles and midpoints, merging sorted lists, and careful in-place reordering. You will build a ListNode and manipulate pointers directly, the skill that pointer-heavy interviews probe.
Binary Trees: The deepest project: binary trees and binary search trees, where most recursion intuition is built. Work through the traversals, tree properties, BST operations, root-to-leaf paths and side views, structural transforms (invert, symmetry, lowest common ancestor), construction from traversals, and tree dynamic programming. Seven chapters of the recursion that interviews lean on hardest.
Heaps & Tries: Two specialized structures with sharp uses. A heap (priority queue) keeps the smallest or largest element one cheap step away, the engine behind top-K, scheduling, and running-median problems. A trie stores strings as shared character paths, making prefix queries and autocomplete fast. Build both with std::priority_queue and a custom trie, and apply them to the interview classics.
Graphs: The most general structure, and the one interviews probe hardest. Represent a graph as an adjacency list, traverse it breadth-first and depth-first, detect cycles and order a directed graph with topological sort, manage connectivity with union-find, solve the grid-as-graph classics (islands, flood fill, rotting oranges), and compute shortest paths with Dijkstra. Seven chapters covering the graph patterns that show up again and again.
Backtracking & Greedy: Two opposite strategies. Backtracking explores every valid possibility by choosing, recursing, and un-choosing, the skeleton behind subsets, permutations, combinations, and constraint puzzles. Greedy makes the locally best choice and never looks back, fast and simple when local optimum leads to global optimum, as in interval scheduling and jump games. This project builds the backtracking template thoroughly, then the greedy classics.
Dynamic Programming: The capstone of the track. Dynamic programming solves problems with overlapping subproblems by computing each one once and reusing it. Build the whole toolkit: one-dimensional DP, coin and unbounded-knapsack problems, the great subsequence problems (LIS, LCS, edit distance), grid DP, the 0/1 knapsack family, string DP, and the stock and interval classics. Seven chapters of the pattern that separates strong candidates from the rest.

Key concepts

Adjacency list: A graph representation mapping each node to a list of its neighbors (a vector of vectors). Compact for sparse graphs and the input to almost every graph algori…
Amortized complexity: The average cost per operation over a sequence, even if a single operation is occasionally expensive. std::vector's push_back is amortized O(1): most are c…
Backtracking: Explore every valid possibility by choosing, recursing, and un-choosing, pruning branches that cannot succeed. The skeleton behind subsets, permutations, combi…
Big-O notation: A way to describe how an algorithm's running time or memory grows with the input size n, ignoring constants. O(1), O(log n), O(n), O(n log n), and O(n^2) a…
Binary search: Halving a sorted search space each step to find a value in O(log n). The boundary variants (first occurrence, last occurrence, lower bound) and 'binary sea…
Binary search on the answer: When the answer is a number in a range and you can cheaply test 'is this value feasible?', binary search the range itself. Powers Koko-eating-bananas,…
Binary search tree: A binary tree keeping left subtrees smaller and right subtrees larger than each node, so search, insert, and ordered queries run in O(height). An inorder trave…
Binary tree: A tree where each node has up to two children. Its traversals (inorder, preorder, postorder, level-order) are the skeletons of nearly every tree algorithm.
Breadth-first search: A traversal that explores a graph level by level using a queue, visiting nearest nodes first. In an unweighted graph it finds the shortest path by number of ed…
Depth-first search: A traversal that dives as deep as possible before backtracking, usually via recursion or a stack. The natural tool for connectivity, components, cycle detectio…
Dijkstra's algorithm: Finds shortest weighted paths from a source with non-negative weights, using a min-heap to always expand the closest unfinished node. O(E log V).
Divide and conquer: Solve a problem by splitting it into independent subproblems, solving each recursively, and combining the results. Merge sort, quicksort, and binary search are…
Dynamic programming: Solve problems with overlapping subproblems by computing each subproblem once and reusing it, via a table (bottom-up) or memoized recursion (top-down). The too…
Edit distance: The minimum insertions, deletions, or substitutions to turn one string into another (Levenshtein distance), via a 2D DP. Powers spell-check and fuzzy matching.
Fast and slow pointers: Two pointers moving at different speeds (one step vs two) to find a list's midpoint, detect a cycle, locate its start, or test a palindrome, all in O(1) ex…
Graph: A set of nodes joined by edges, directed or undirected, weighted or not. Usually stored as an adjacency list. The most general structure and the one interviews…
Greedy algorithm: Make the locally best choice at each step and never reconsider. Fast and simple when a local optimum leads to a global one, as in interval scheduling, jump gam…
Heap: A complete binary tree (stored in an array) where every parent outranks its children. It gives O(1) access to the extreme element and O(log n) insertion and re…
In-place algorithm: An algorithm that transforms its input using only O(1) extra space, rewriting the data rather than allocating a copy. List reversal, array partitioning, and th…
Interval DP: Dynamic programming over a range [i, j] that combines answers from sub-ranges split at every interior point. Matrix-chain multiplication and palindrome partiti…
Knapsack: A family of DP problems about choosing items under a capacity to maximize value (0/1 knapsack, each item once) or count ways. Subset-sum, equal partition, and…
Linked list: Nodes joined by next-pointers rather than stored contiguously. Insertion and deletion are O(1) given the node, but access is sequential. The home of reversal,…
Longest common subsequence: The longest subsequence shared by two strings, computed with a 2D DP table. The basis of diff tools and a sibling of edit distance.
Longest increasing subsequence: The length of the longest strictly increasing subsequence of an array. The O(n^2) DP and the O(n log n) patience-sorting variant are both standard interview ma…
Lower bound: The first position where a value could be inserted to keep a sorted array ordered, i.e. the first element not less than the target. The basis of insertion poin…
Memoization: Caching the result of each distinct recursive call so it is never recomputed. Top-down dynamic programming: write the natural recursion, then add a cache.
Merge sort: A divide-and-conquer sort: split in half, sort each half, merge them. O(n log n) in every case and stable, at the cost of O(n) extra space.
Monotonic stack: A stack kept in increasing or decreasing order, resolving 'next greater', 'previous smaller', and span queries in a single O(n) pass. One of th…
Pointer: A variable holding the address of another object. C++ data structures (lists, trees, graphs) are wired together with pointers; nullptr marks the end of a chain…
Prefix sum: A precomputed array where entry i holds the sum of everything up to i, so any range sum is one subtraction. The same idea (a running cumulative plus a hash map…
Quicksort: Partition around a pivot so smaller elements go left and larger go right, then recurse. Averages O(n log n) and sorts in place; the same partition step gives q…
Recursion: A function defined in terms of itself, reducing a problem to smaller instances with a base case to stop. The natural language for trees, divide-and-conquer, an…
Sliding window: A contiguous range that grows and shrinks as it scans, maintaining a running aggregate (sum, count, frequency map). It turns many substring and subarray proble…
std::deque: A double-ended queue allowing O(1) push and pop at both ends. A monotonic deque finds the maximum of every sliding window in O(n).
std::priority_queue (heap): A binary heap exposed as a priority queue: the largest (or smallest, with std::greater) element is always one O(1) peek away, with O(log n) push and pop. The e…
std::queue: A first-in, first-out container, the engine of breadth-first search and streaming problems. A std::deque (double-ended queue) extends it for sliding-window ext…
std::stack: A last-in, first-out container. It matches brackets, evaluates expressions, and powers the monotonic-stack pattern that answers next-greater and span questions…
std::unordered_map: A hash table giving O(1) average lookup, insert, and erase. The main tool for counting frequencies, remembering seen values, and collapsing nested searches int…
std::unordered_set: A hash table of unique keys with O(1) average membership tests. Used for de-duplication, cycle detection, and 'have I seen this before' checks.
std::vector: C++'s dynamic array: a contiguous, index-able, growable sequence. It is the default container for DSA problems, backing scans, prefix sums, two-pointer swe…
Topological sort: An ordering of a directed acyclic graph's nodes so every edge points forward. Kahn's algorithm (repeatedly removing an in-degree-zero node) produces it…
Tree traversal: An order for visiting every node: inorder (left, node, right), preorder (node first), postorder (node last), or level-order (breadth-first with a queue).
Trie (prefix tree): A tree that stores strings as shared character paths from a root, so words with a common prefix share nodes. Lookups and prefix queries cost O(length), indepen…
Two heaps: A max-heap of the lower half plus a min-heap of the upper half, kept balanced, so the running median is always at the tops. The standard pattern for streaming…
Two pointers: Two indices walking an array, either from both ends inward or in the same direction, to replace a nested loop with a single O(n) pass. Behind sorted-pair sums,…
Union-find (disjoint set): A structure tracking connectivity under merges in near-constant time with path compression. The go-to tool for connected components, cycle detection while addi…