Algorithms

You're laying fiber to connect 10,000 cell towers using the minimum total cable. The candidate trench segments form a sparse graph with about 30,000 edges, each with a cost. What's the right approach?

On sparse graphs Kruskal's runs in O(E log E) by sorting edges and unioning components, which is ideal here. Dense Prim's with a matrix would cost O(V^2) and dominates when V is large and E is small. Dijkstra solves shortest path, not minimum spanning tree.

A chip designer needs the minimum-cost wiring tree over 2,000 pads where nearly every pair has a candidate route, giving roughly two million edges. Memory is tight and edge sorting would be expensive. What's the right approach?

Dense Prim's with an adjacency matrix runs in O(V^2) and avoids sorting ~2M edges. Kruskal's would pay O(E log E) just to sort, which beats Prim's only when E is much smaller than V^2.

You have 500 interns and 500 projects, with a bipartite graph of who can work on what. You need the largest set of assignments where each intern gets at most one project and each project gets at most one intern. What's the right approach?

Maximum bipartite matching reduces to max flow with a source feeding interns and projects feeding a sink, all unit capacities; Edmonds-Karp (BFS-based augmenting paths) is the textbook solution. Greedy by degree gives suboptimal matchings on non-trivial graphs.

You're analyzing a microservice call graph to find groups of services that mutually depend on each other (so you can flag the cyclic clusters). The graph has ~200k nodes and ~1M directed edges. What's the right approach?

Tarjan's finds all SCCs (Strongly Connected Components) in a single DFS (Depth-First Search) pass in O(V+E) using lowlink values. Union-find works on undirected connectivity and would group services that aren't mutually reachable. Topological sort would simply fail or skip nodes inside cycles.

An analytics service tracks per-minute revenue and serves two query types: 'add X to minute i' and 'sum of revenue from minute L to minute R'. Both happen millions of times per day over a fixed-size timeline. What's the right approach?

A Fenwick tree gives O(log n) point updates and O(log n) prefix-sum queries with a tiny constant. A plain prefix-sum array is O(1) to query but O(n) per update, which collapses under frequent writes. Sparse table doesn't support updates.

Given a permutation of 2 million user-ranking scores, you need the exact count of inversions (pairs i<j with a[i]>a[j]) to measure how reordered a feed became. An O(n^2) double loop is too slow. What's the right approach?

Modified merge sort counts cross-inversions during the merge step in O(n log n); equivalently you can scan right-to-left and query/update a Fenwick tree on compressed values. Counting swaps in heap sort doesn't equal the inversion count.

You have a fixed array of one million sensor readings and need to answer 'min reading in [L, R]' for ten million queries. The data never changes after load. What's the right approach?

For idempotent ops like min/max with no updates, a sparse table answers each query in O(1) after O(n log n) preprocessing. A segment tree also works but pays O(log n) per query, which adds up over 10M queries.

You're scanning DNA strings up to 10 million bases and need the longest palindromic substring of each. A naive O(n^2) DP is too slow. What's the right approach?

Manacher's finds the longest palindromic substring in O(n) by reusing mirror information around the current rightmost palindrome. Expand-around-center is O(n^2) worst case. KMP (Knuth-Morris-Pratt) on reversed text finds longest palindromic prefix, not the global longest palindrome.

A content moderator needs to scan each chat message for any match against a dictionary of 50,000 banned phrases. Messages arrive at high throughput; the dictionary is mostly static. What's the right approach?

Aho-Corasick builds a trie with failure links once and then scans each message in O(n + matches), independent of pattern count. Running KMP (Knuth-Morris-Pratt) per pattern costs O(k * (n + m)) and scales badly with 50k patterns.

You're comparing five large source files (each ~1MB) and need the longest substring that appears in all of them. A pairwise dynamic programming table would be huge. What's the right approach?

Concatenate the files with distinct separators, build a suffix array plus LCP array, then slide a window over suffix ranks that touches all five sources and take the max LCP. Edit-distance DP (Dynamic Programming) solves a different problem (alignment cost) and is O(n*m) per pair.

You have a static org-chart tree of 200,000 employees and must answer 'who's the lowest common manager of employees u and v' for a million queries. What's the right approach?

Binary lifting precomputes 2^k-th ancestors in O(n log n) and answers each LCA (Lowest Common Ancestor) query in O(log n). Naive root-walks are O(n) per query, which is 2*10^11 ops over a million queries. Union-find can't query ancestors that way.

A streaming pipeline emits log lines forever and you must keep a uniformly random sample of exactly 1,000 lines at any moment, without knowing the total count in advance and without buffering everything. What's the right approach?

Algorithm R fills a reservoir of size k, then for the i-th item (i>k) keeps it with probability k/i, giving a uniform sample over the stream so far in O(1) memory per item. Min-hash sampling gives a different distribution (uniform over distinct items, biased by hash collisions) and isn't what 'uniformly random sample of lines' means.