Before you commit to a greedy solution in an interview, how do you convince yourself the greedy choice is safe?

## The failure this question exists to prevent The most common way a candidate loses a paradigm question is not writing a wrong loop. It is writing a *plausible* greedy, watching it pass the two examples printed in the statement, and declaring it correct. Greedy heuristics agree with the optimum on most random inputs; that is exactly why they are tempting and exactly why sample cases do not test them. A discipline for deciding is therefore worth more than any single remembered verdict. ## Move one: the exchange argument The greedy-choice property says that the first move greedy makes is contained in *some* optimal solution. The standard way to establish it is an exchange argument, and it has a fixed shape: 1. Let `OPT` be any optimal solution that does *not* contain the greedy choice `g`. 2. Show a transformation of `OPT` that inserts `g` and removes something else. 3. Show the transformed solution is still legal (respects the constraints). 4. Show its objective value is no worse. If all four steps hold, then an optimal solution containing `g` exists, greedy's first move is safe, and the same reasoning applies recursively to what remains - that recursion is the optimal-substructure half of the story. Step 3 is where these proofs actually die, and it is where you should look first. In the divisible-cargo problem, swapping one unit of weight for another keeps the load legal because the weight is unchanged; make the items indivisible and the swap must move a whole item, the weight changes, and the argument collapses. The proof does not fail vaguely - it fails at an identifiable line, and being able to point at that line is the senior version of this answer. ## Move two: hunt the counterexample Run the two moves in parallel, because the counterexample search often finishes first. Two properties make it cheap: - **Counterexamples are tiny.** Greedy's failures show up at two or three items, or at small amounts. The change-making failure at denominations 1, 3, 4 needs an amount of 6. The whole-crate failure needs two crates. - **Brute force is available at that size.** Enumerate every subset or every decomposition for inputs that small and compare against the greedy answer. In an interview, do this by hand with deliberately adversarial numbers: make one option locally attractive and globally blocking - the item that is densest but strands capacity, the coin that is largest but wrecks the remainder. If you can build such a case in under a minute, greedy is dead and you have saved yourself twenty minutes. On the job the same idea becomes a randomised differential test: generate small random inputs, compare greedy against the exact method, and keep the first disagreement as a permanent regression case. ## Move three: read the statement for the load-bearing word Paradigm choice usually hangs on one clause, and interviewers flip it on purpose to see whether you re-derive or recite. Words that carry the property: - **"May be split" / "whole units only."** Divisibility makes the unit-for-unit exchange legal, which is the difference between a provable greedy and a hard optimisation. - **"All the same size / weight / duration."** Uniformity often collapses a hard problem into a counting one where greedy is trivially right. - **"Already sorted" or "arrives in order."** Ordering can supply the very structure the exchange argument needs. - **"Choose at most one from each group" / "unlimited copies."** Reuse rules change which exchanges are available. When the interviewer changes one of these mid-problem, the correct reaction is not to patch your greedy. It is to say which step of your proof just stopped holding, and therefore which paradigm now applies. That single sentence is often the whole point of the follow-up. ## What a good answer sounds like "My greedy choice is the densest item. To justify it I would take any optimal load without that item and swap weight into it - that keeps the load legal only because items can be split, so the argument depends on divisibility. If items were whole, I would expect a two-item counterexample, and I would look for one where the densest item strands capacity. Failing to find either a proof or a counterexample quickly, I would formulate the exact method rather than ship an unjustified greedy." That answer demonstrates the thing the question is testing: paradigm choice as a decision procedure with evidence, not as a guess with confidence attached. ## Two claims to avoid First, greedy and an exact method are not interchangeable implementations of the same idea, with greedy merely faster - when the greedy-choice property fails, greedy is simply wrong, at any speed. Second, an exchange argument that works for one problem does not transfer by resemblance; near-identical statements differing in one clause land on opposite sides of the line, which is precisely why the check has to be re-run every time.