Algorithms—Choose wisely, don't just recall

An algorithm is not a magic spell to recite at an interview. It is a decision you make every day: use std::map or std::unordered_map, write recursion or a loop, sort beforehand or search linearly. The cost of a wrong choice is not theoretical—it is measured in milliseconds of latency and megabytes of memory.

In C++ the choice of algorithm is especially visible, because the language does not hide the cost. You see recursion growing the stack, you see an extra allocation miss the cache, you see O(n²) on sorted input turn fast code into a hang. To understand algorithms means not to memorize pseudocode, but to grasp the cost of each choice and decide consciously.

Complexity analysis

Complexity (Big-O) describes how runtime or memory grows as the input size n grows. It is a growth rate, not absolute speed: O(n) with a large constant can lose to O(n²) on small inputs.

Three estimates exist: worst case (O), average case (Θ), and best case (Ω). In an interview, worst case is the default unless stated otherwise. The main classes in order of growth:

• O(1) — constant: array index access, hash table insertion (average case).
• O(log n) — binary search, height of a balanced tree.
• O(n) — linear scan.
• O(n log n) — lower bound for comparison-based sorting.
• O(n²) — nested loops over the input.
• O(2ⁿ) — full enumeration, naive Fibonacci recursion.

Don't forget space complexity: recursive algorithms often trade time for stack depth. And hash table operations are O(1) only on average; in the worst case, collisions give O(n).

Recursion

Recursion is a function calling itself. Each call pushes a new frame onto the call stack, so recursion must have a base case—a stopping condition. Without it, or with recursion too deep, the stack overflows.

// Naive Fibonacci recursion: O(2ⁿ) — fib(40) takes seconds
long long fib_slow(int n) {
    if (n < 2) return n;                  // base case
    return fib_slow(n - 1) + fib_slow(n - 2);
}

// Memoization: each fib(k) computed once → O(n)
long long fib_memo(int n, std::vector<long long>& cache) {
    if (n < 2) return n;
    if (cache[n] != -1) return cache[n];   // cached answer
    return cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache);
}

Recursion vs. iteration is a tradeoff. Recursion is shorter and clearer for trees and divide-and-conquer; iteration does not grow the stack and is predictable in memory. Memoization turns exponential recursion into linear by caching subproblem results—naive fib(40) takes seconds, memoized is instant.

Sorting and searching

Comparison-based sorting cannot be faster than O(n log n)—this is a proven lower bound. Three algorithms to know:

• Quicksort — in-place, average O(n log n), but with a poor pivot choice (e.g., always the first element) it degrades to O(n²) on sorted input.
• Merge sort — stable, guaranteed O(n log n), but needs O(n) extra space.
• Introsort — what std::sort uses: quicksort that switches to heapsort if recursion gets too deep, and insertion sort on small subarrays.

Stability means elements with equal keys preserve their original relative order. This matters when sorting by a secondary key: std::stable_sort is stable (at the cost of O(n) memory), std::sort is not.

Binary search runs in O(log n), but only on sorted data.

int binary_search(const std::vector<int>& v, int target) {
    int low = 0, high = (int)v.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;   // not (low+high)/2 — overflow
        if (v[mid] == target) return mid;
        if (v[mid] < target) low = mid + 1;
        else                 high = mid - 1;
    }
    return -1;
}

Two classic traps: mid = (low + high) / 2 overflows on large indices—write low + (high - low) / 2 instead; and the loop bound while (low <= high) vs. < high changes semantics—an off-by-one error here gives a wrong result.

Data structures

Linked list — nodes connected by pointers. Insertion and removal at a known position is O(1), but random access is O(n). When reversing a list, save the next pointer before overwriting next:

Node* reverse(Node* head) {
    Node* prev = nullptr;
    while (head) {
        Node* next = head->next;   // save BEFORE overwrite
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;                   // return prev, not head — head is nullptr now
}

Trees. A binary search tree (BST) maintains an invariant: smaller values to the left, larger to the right. Search is O(log n) on a balanced tree and O(n) on a degenerate one (BST guarantees value order but not balance). Traversals: pre-order, in-order, post-order, and level-order; in-order traversal of a BST yields values in sorted order.

Hash table maps a key to a bucket via a hash function: average-case search is O(1), worst case is O(n) on collisions. When the load factor is exceeded, the table rehashes into a larger array.

Stack (LIFO) and queue (FIFO)—the simplest data structures. A fixed-size queue is cleanly implemented as a circular buffer; the main trap there is distinguishing empty from full (a separate size counter or sacrifice one cell).

Graph algorithms

A graph is vertices and edges; in memory it is represented as an adjacency list (compact for sparse graphs) or a matrix. Two basic traversals:

• BFS (breadth-first search) uses a queue, explores level-by-level, and finds the shortest path in an unweighted graph.
• DFS (depth-first search) uses a stack or recursion, goes deep—the foundation of topological sorting and reachability analysis.

In any traversal, mark visited vertices—otherwise, a cyclic graph will loop forever.

Dijkstra's algorithm finds shortest paths in a weighted graph with non-negative edges; a priority queue makes it efficient. On graphs with negative edges, Dijkstra gives wrong results—use Bellman-Ford instead.

Cycle detection depends on the graph type: in directed graphs, DFS with three-color marking (a back edge reaches a "gray" vertex on the current path); in undirected graphs, a union-find (disjoint-set) structure.

Dynamic programming

Dynamic programming (DP) applies when a problem decomposes into overlapping subproblems and has optimal substructure. Two styles:

• Memoization (top-down)—normal recursion plus a cache of solved subproblems.
• Tabulation (bottom-up)—iteratively fill a table from base cases to the answer.

When the recurrence only depends on the last row of the table, memory can be compressed from O(n²) to O(n). And a memoization cache is better kept in an array than std::map—O(1) vs. O(log n) per lookup.

String algorithms

Naive substring search is O(n·m); the Knuth-Morris-Pratt (KMP) algorithm does it in O(n + m) by reusing information about the prefix already matched. Calling std::string::find in a loop is a classic way to accidentally get O(n²).

Palindrome checking does not need to reverse the string and waste O(n) space—use two pointers moving toward each other. And remember: string comparison in C++ is O(n), not O(1) like pointer comparison. Work with non-ASCII text by Unicode code points, not bytes.

Bitwise operations

Bitwise operations (&, |, ^, shifts)—compact and fast. A few tricks beloved by interviewers:

// Count set bits — Kernighan's trick: O(number of bits), not O(32)
int count_bits(unsigned n) {
    int count = 0;
    while (n) { n &= (n - 1); ++count; }   // n & (n-1) clears the lowest set bit
    return count;
}

n & (n - 1) clears the lowest set bit—hence the count runs in the number of set bits, not word width. In C++20 this is a one-liner: std::popcount. Another classic—XOR: if all array elements appear twice except one, XOR all of them to get the unique element in O(1) space. For bitwise work, use unsigned types—signed types have undefined behavior on shift and overflow.

STL algorithms

The standard library provides <algorithm>—std::sort, std::find, std::transform, std::accumulate, and dozens more. Their advantage over manual loops: correctness, optimization, and clarity—intent reads at a glance.

Key pitfalls:

• Erase-remove idiom. std::remove and std::remove_if do not physically shrink the container—they shift "survivors" and return a new end; erase actually removes. In C++20, std::erase_if is cleaner.
• Iterator requirements. std::sort needs random access—it won't compile on std::list, which has its own list::sort() method. std::binary_search, lower_bound, upper_bound require a sorted range.
• Execution policy (C++17). Passing std::execution::par asks the algorithm to parallelize. But par does not make code thread-safe by itself—shared state still needs protection; and on small inputs the thread overhead eats the speedup.

Common traps and mistakes

Relevance for interviews

Algorithms are the core of technical interviews at any C++ level. But the interviewer is not checking memorized pseudocode—they are checking engineering judgment: can you estimate complexity, choose a data structure, and spot a trap?

What the interviewer checks:

• Time and space complexity estimation, difference between worst and average case
• Recursion vs. iteration, and the role of memoization
• Sorting choices: quicksort, merge sort, introsort—and what stability means
• Correct binary search without overflow or off-by-one errors
• Data structures: linked lists, trees, hash tables—their complexities
• Graph traversals (BFS vs. DFS) and limits of Dijkstra
• Knowledge of <algorithm>: erase-remove idiom, iterator requirements

Typical questions:

1. What is Big-O complexity and how do you determine it?
2. What is the difference between memoization and tabulation?
3. Compare quicksort and merge sort by complexity, stability, and memory.
4. When do you choose BFS over DFS?
5. How does Dijkstra work, and why does it break on negative edges?
6. Why does the erase-remove idiom exist?

Common mistake: writing code without estimating its complexity or naming edge cases (empty input, single element, overflow). The interviewer is looking for someone who picks an algorithm consciously and sees traps beforehand—not someone who recites a memorized solution.