How do you decide whether a problem can be solved greedily, and how would you convince yourself a greedy choice actually yields the optimum?

technical-conceptual · Mid level · software-engineering

What the interviewer is really asking

Tests whether the candidate knows the two structural properties that justify greedy, can name a proof technique rather than just trusting intuition, and understands that an unproven greedy is a common source of subtly wrong solutions.

What to say

• Greedy is valid only when the problem has two properties: the greedy-choice property — a locally optimal choice at each step is part of some globally optimal solution — and optimal substructure — after making that choice, the optimal solution to what remains, combined with the choice, is optimal overall. If either fails, greedy can return a suboptimal answer.
• Don't trust intuition that the locally best move is globally best — prove it. The two standard arguments are an exchange argument (take any optimal solution and show you can swap in the greedy choice without making it worse, so a greedy-aligned optimum exists) and 'greedy stays ahead' (show greedy is at least as good as any other solution after every step). Interval scheduling by earliest finish time is the textbook example provable this way.
• Be ready with the counterexample reflex: many problems look greedily solvable but aren't — making change with arbitrary coin denominations is the classic, where picking the largest coin first can miss the minimum-coin solution that dynamic programming finds. If you can construct a counterexample, greedy is out.

What to avoid

• Assume that because a greedy approach is simple and feels right it must be correct — unproven greedy algorithms are a top source of solutions that pass small tests and fail on adversarial input.
• Confuse greedy with dynamic programming — greedy commits to one choice per step and never reconsiders, while DP explores and combines multiple subproblem solutions; using greedy where the choice isn't safe silently loses optimality.
• Claim greedy always finds the global optimum — it only does when the greedy-choice property and optimal substructure both hold.

Example answers

Strong: For a meeting-room/interval problem I picked activities by earliest finish time and justified it with an exchange argument: any optimal schedule's first activity can be swapped for the earliest-finishing one without reducing the count, so greedy is safe. I verified it against a brute-force solution on random inputs before shipping, and they always matched.

Weak: If I can take the best option at each step, I just do that — greedy is simpler than DP and it usually works.