Build fluency in the vocabulary of committing to the locally best choice at every step without reconsidering.
0 / 5 completed
1 / 5
At standup, a dev mentions an algorithm that, at every step, picks whichever option looks locally best right now, without ever reconsidering that choice later, and this happens to still produce the globally optimal answer for the problem at hand. What is this technique called?
A greedy algorithm picks whichever option looks locally best at each individual step and never reconsiders that choice afterward, which for certain problems, like making change with a well-behaved coin system or building a minimum spanning tree, happens to still produce the globally optimal overall answer. Dynamic programming is a related but distinct technique that stores and reuses overlapping subproblem answers rather than committing irrevocably to one choice per step. This never-reconsider property is exactly what makes a greedy algorithm fast, but also exactly why it only works correctly on problems where the locally best choice is provably always part of some globally optimal solution.
2 / 5
During a design review, the team proves the problem has the greedy-choice property, meaning a locally optimal choice at each step is always part of some globally optimal solution. Which capability does this proof unlock?
Proving the greedy-choice property unlocks applying a greedy algorithm safely, since it guarantees that committing permanently to the locally best choice at every single step is still guaranteed to lead to a globally optimal overall answer, with no need to ever backtrack and reconsider an earlier decision. Applying a greedy approach to a problem that hasn't been shown to have this property is risky, since the locally best choice at some step might not actually be part of any globally optimal solution. This is exactly why proving the greedy-choice property, not just observing that a greedy approach seems to work on a few test cases, is what justifies trusting a greedy algorithm's correctness.
3 / 5
In a code review, a dev notices a greedy algorithm is applied to a problem that hasn't actually been proven to have the greedy-choice property, and the implementation passes every test case the team happened to write. What does this represent?
This is a correctness risk, since passing every test case the team happened to write says nothing about whether the greedy-choice property genuinely holds for every possible input, and a greedy algorithm applied without that proof can silently produce a suboptimal, or outright wrong, answer on some input the tests simply never happened to cover. A cache eviction policy is an unrelated concept about discarded cache entries. This gap between passing tests and having an actual correctness proof is exactly why a greedy approach needs to be justified analytically, not just empirically, before being trusted in production.
4 / 5
An incident report shows a resource-allocation service using a greedy algorithm occasionally produced a noticeably suboptimal allocation in production, even though it passed every test case the team had written, because the greedy-choice property had never actually been proven for this particular allocation problem. What practice would prevent this?
Proving the greedy-choice property actually holds for the specific allocation problem, or switching to a technique like dynamic programming that doesn't rely on that unproven assumption, is exactly the fix for the occasional suboptimal allocations described in this incident. Continuing to treat a passing test suite as sufficient proof is exactly what let the flawed greedy approach reach production and misbehave on inputs the tests didn't happen to cover. This analytical proof step, done once up front, is the standard safeguard against exactly this kind of silent, input-dependent correctness gap.
5 / 5
During a PR review, a teammate asks why the team insists on an analytical proof of the greedy-choice property instead of just trusting a greedy algorithm that has performed well on every test case run so far. What is the reasoning?
A greedy algorithm can look entirely correct across every test case the team happens to think of while still silently failing on some untested input the tests never covered, since passing a finite set of examples is a fundamentally weaker guarantee than a mathematical proof covering every possible input. A proof of the greedy-choice property instead guarantees the locally best choice is always part of some globally optimal solution, for every input the problem could ever present, not just the ones already exercised by tests. The tradeoff is the upfront analytical effort of actually constructing or finding that proof, which is a real cost, but one that's far cheaper than discovering a correctness gap in production after the fact.