A compact C++20 review library for interview fundamentals. It favors explainable implementations, edge-case tests, and complexity notes over a large dump of copied problem solutions.
| Category | Implementations | Time complexity |
|---|---|---|
| Search/sort | binary search, merge sort, quick sort, heap sort | O(log n) search; O(n log n) sort average/guaranteed as documented in code |
| Data structures | binary min-heap, trie, disjoint set, LRU cache | heap O(log n); trie O(k); DSU amortized O(alpha(n)); LRU O(1) |
| Graphs | BFS, DFS, Dijkstra, topological sort, cycle detection, connected components | O(V + E) except Dijkstra O((V+E) log V) |
| Arrays/strings | two sum, sliding-window maximum, longest unique substring, KMP | O(n) |
| Dynamic programming | coin change, LIS, 0/1 knapsack, edit distance | from O(n log n) LIS to O(mn) edit distance |
| Trees | BST validation, level-order traversal, BST lowest common ancestor | O(n) or O(h) |
There are 25 focused implementations across two header files. The tests cover normal behavior, duplicates, missing values, graph cycles, deep BST violations, and cache eviction.
cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --config Release
ctest --test-dir build -C Release --output-on-failureThe GitHub Actions matrix runs on both Linux and Windows.
include/portfolio/data_structures.hpp— heap, trie, disjoint set, and LRU cache.include/portfolio/algorithms.hpp— search, sorting, graphs, arrays, strings, DP, and tree algorithms.tests/test_main.cpp— dependency-free executable test harness.
- Selected a bounded set of fundamentals relevant to new-graduate SDE interviews.
- Implemented each algorithm from first principles in modern C++20.
- Added explicit edge-case behavior and a cross-platform warning-enabled build.
- Documented complexity and kept the test harness dependency-free for quick review.
For each implementation I practice explaining the invariant, complexity, failure cases, and one alternative—not memorizing the source. This repository supports interview preparation; it is not a substitute for timed problem solving.