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 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.

A cloud scheduler tracks reserved CPU across one million time slots. Each reservation adds c cores to every slot in [L, R], and each admission check asks for the peak reserved CPU over [L, R]. Both operations run hundreds of thousands of times. What's the right approach?

A segment tree stores the max of each node's range and defers range additions as lazy tags pushed down only when needed, so both range add and range max run in O(log n). A Fenwick tree handles range sums but can't maintain a range max under range updates. A sparse table is static, and a difference array makes updates O(1) but max queries O(n).

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 per pattern costs O(k * (n + m)) and scales badly with 50k patterns.

A network appliance scans a byte stream for one fixed 4 KB signature. Bytes arrive once and can't be re-read, buffer space is limited to roughly the signature size, and attackers can craft traffic to trigger worst-case behavior. What's the right approach?

KMP precomputes a failure table for the signature and never moves backward in the input, giving O(n + m) in the worst case with only O(m) extra memory. Rabin-Karp degrades to O(n * m) when an attacker forces hash collisions. Boyer-Moore compares right to left and jumps ahead, which needs a window of buffered input, and its basic form is also O(n * m) in the worst case.

A deduplication tool needs to know whether any 64-byte chunk at any offset of a 500 MB firmware image also appears anywhere in a second 500 MB image. Every byte offset is a candidate chunk. What's the right approach?

Rabin-Karp updates the hash of a sliding 64-byte window in O(1) per step, so hashing every offset of both images is linear. Verifying each hash hit with a byte comparison rules out false matches. Hashing every window from scratch costs 64 times the work, and running KMP per chunk means hundreds of millions of separate scans.

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 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 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.

A CI system runs 5,000 build targets with declared dependencies. It needs an order where every target runs after its dependencies, wants to start all ready targets in parallel waves, and must name the targets stuck in a cycle when the graph is broken. What's the right approach?

Kahn's algorithm repeatedly removes targets with zero remaining in-degree, so each batch of zero in-degree targets is a parallel wave. If targets remain once the queue empties, those targets are exactly the ones in or behind a cycle. Depth from the root breaks when a target is reachable by both a short and a long path, since it can land before a dependency on the long path.

An identity service ingests a stream of 50 million 'these two accounts belong to the same person' links. Links are never removed, and between links the service must answer 'are accounts A and B the same person?' in near constant time. What's the right approach?

Union-find merges two sets on each link and answers same-set queries by comparing roots. With path compression and union by rank, each operation costs O(α(n)) amortized, which is effectively constant. A BFS per query is O(V + E), and recomputing components after every link repeats that work 50 million times.

A league splits 3,000 players into two teams, with a list of 20,000 rival pairs who must land on opposite teams. You need to report whether a valid split exists and, if so, produce one. What's the right approach?

The split exists exactly when the rivalry graph is bipartite. BFS from each uncolored player assigns alternating colors, and any edge joining two same-colored players proves an odd cycle, so no split exists. Alternating by input order ignores the edges entirely, and a minimum cut minimizes crossing edges without guaranteeing every rival pair is separated.

A nightly job loads 50 million request latencies into an in-memory array and needs the exact p99. It computes one percentile per run, and memory is too tight for a second copy of the array. What's the right approach?

Quickselect partitions around a pivot and recurses into only the side that holds the target rank, giving O(n) expected time in place. Sorting does O(n log n) work to answer a single rank. The top 1% heap is correct but holds 500,000 extra values and pays O(n log k). Binary search needs sorted data.

A trading dashboard stores ten years of daily profit and loss per strategy, with both gains and losses. For each of 100,000 strategies, it must find the contiguous run of days with the largest total. What's the right approach?

Kadane's keeps the best sum ending at the current day, either extending the previous run or starting fresh, and tracks the best seen. That is one O(n) pass with O(1) state. Prefix sums over all pairs are O(n^2), the two-pointer window needs non-negative values to know when to shrink, and sorting destroys contiguity.

A search box suggests corrections by ranking candidate terms against the typed query. The cost should count the fewest single-character insertions, deletions, and substitutions needed to turn one string into the other, and terms differ in length. What's the right approach?

Levenshtein DP fills a table where each cell takes the cheapest of insert, delete, or substitute from its neighbors, which is exactly the stated cost. LCS only models insertions and deletions, so a substitution counts as two edits. Hamming distance requires equal lengths, and bigram overlap is a similarity score with no edit semantics.

An analytics job scans 2 million trades in time order and needs the length of the longest chain of trades with strictly rising prices, where trades can be skipped. An O(n^2) DP would take trillions of steps. What's the right approach?

Keep an array where tails[k] is the smallest ending price of any rising chain of length k + 1. For each trade, binary search for the first tail that is at least its price and replace it, or append if none exists. The array length is the answer in O(n log n). The longest consecutive run and Kadane's both require contiguous trades.

A courier leaves the depot, must visit 15 stops exactly once, and returns to the depot. A billing contract requires the exact minimum total distance, and the distance matrix is known. What's the right approach?

Held-Karp stores the cheapest path that visits a subset of stops (a bitmask) and ends at a given stop, building each subset from smaller ones. For 15 stops that is about 2^15 * 15^2, or roughly 7 million steps. Every permutation is 15!, over a trillion, and nearest neighbor and the MST walk are approximations with no guarantee of optimality.

A mobile app ships with a 50 MB download budget and 200 optional assets, each with a size in whole KB and a value score. Assets can't be split, and the goal is the highest total value that fits within 50,000 KB. What's the right approach?

The 0/1 knapsack DP tracks the best value for every capacity from 0 to 50,000 KB, iterating capacity downward so each asset is used at most once. That is 200 * 50,000, or 10 million steps. Greedy by value density is optimal only when items can be split, and every subset is 2^200.

A consensus layer logs 100 million leader votes, and a candidate wins only with a strict majority. The log can be read twice, there could be millions of distinct candidate IDs, and the checker must run in constant memory. What's the right approach?

Boyer-Moore keeps one candidate and a counter, incrementing on a match and decrementing otherwise. A strict majority always survives as the candidate, and a second pass counts its votes to confirm it actually holds over half. A hash map needs memory per distinct ID, sorting needs the data in memory, and a count-min sketch only gives approximate counts.

A scheduler must split an ordered queue of one million jobs with known durations into at most 24 contiguous shifts. Jobs must stay in order, and the goal is to minimize the length of the longest shift. What's the right approach?

Feasibility is monotonic: if every shift fits within length L, it also fits within any larger L. Binary search over L between the longest job and the total duration, and check each candidate with a greedy pass that opens a new shift when the next job would overflow. The DP is correct but costs O(n^2 * k), the average-length greedy can overshoot, and sorting breaks the required order.

An autoscaler tracks the maximum CPU reading over the trailing 300 samples for each of 200,000 hosts, recomputed every second as a new sample arrives. What's the right approach?

The deque drops smaller values from the back before each push, since they can never be the maximum again, and drops the front once it leaves the window. The front is always the window max, and each sample enters and leaves once, so updates are O(1) amortized. The heap works at O(log k) with extra bookkeeping, rescanning is O(k), and prefix maxima can't forget old values.

A monitoring agent must report the exact median response time after every request across an unbounded stream. Inserts arrive constantly and the median is read after each one. What's the right approach?

Two heaps split the values at the median, rebalanced so their sizes differ by at most one. Each insert is O(log n) and the median is read from the heap tops in O(1). A sorted array costs O(n) per insert from shifting, quickselect costs O(n) per read, and a reservoir sample gives an approximate median.

A shared lab room receives 20,000 booking requests for next quarter, each with a fixed start and end time. You must accept the largest possible number of bookings with no overlaps. What's the right approach?

Sorting by end time and taking each booking that starts after the last accepted one ends is optimal. By an exchange argument, finishing earliest leaves the most room for everything after it. Earliest start fails when one long booking blocks many short ones, shortest duration fails when a short booking straddles two compatible ones, and fewest conflicts has known counterexamples.

Firmware with a 2 KB stack must emit the keys of a 100,000-node binary search tree in sorted order. The tree may be badly unbalanced, nodes have only left and right pointers, and the tree may be modified during the walk as long as it's restored. What's the right approach?

Morris traversal links each node's inorder predecessor back to it, walks the thread to return upward, and removes the link on the second visit. That uses O(1) extra memory and O(n) time, since each edge is crossed a constant number of times. Recursive and stack-based traversals need O(h) memory, which is O(n) on a skewed tree, and copying needs O(n) as well.

A cache tier of 400 nodes scales up and down every hour. Clients must compute each key's owner locally with no shared directory, and a node joining or leaving should move as few keys as possible while keeping load even. What's the right approach?

Placing nodes at many points on a hash ring and assigning each key to the next point clockwise means a join or leave moves only about 1/N of keys. Virtual nodes smooth out the load. Modulo hashing remaps nearly every key whenever N changes, range partitioning needs a shared range map and rebalancing for skew, and a directory violates the local-computation requirement.

A web crawler must skip URLs it has already fetched across one billion URLs, with a 2 GB memory budget. Occasionally skipping a new URL is acceptable, but refetching a URL already crawled is not. What's the right approach?

A Bloom filter has no false negatives, so a fetched URL is always recognized, and its false positives only cause the acceptable occasional skip. At 1% it needs about 9.6 bits per URL, roughly 1.2 GB for a billion URLs with 7 hash functions. A hash set of full URLs needs around 100 GB, the sorted hash array needs 8 GB and O(n) inserts, and HyperLogLog only estimates how many distinct URLs exist.