15 scenarios with the right algorithm, grouped by topic. Click any to expand.
You're building a ride-share ETA service. Roads have positive travel times that vary by segment, and you need the fastest route from a driver to a pickup point. The graph has ~50k intersections and ~200k road segments. What's the right approach?
You're routing packets across a peering network where some carriers pay you to take their traffic, so a few links have negative cost. You need the cheapest path and must also flag any negative-cost cycles. What's the right approach?
A logistics planner needs the shortest delivery time between every pair of 400 warehouses, given a dense distance matrix with positive and a handful of negative adjustments. The query needs to answer any pair instantly afterwards. What's the right approach?
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?
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?
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?
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?
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?
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?
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?
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?
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?
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?
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?
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?