A strong answer
A greedy algorithm makes the locally best choice at each step and never revisits it. It is optimal when the problem has two properties: the greedy-choice property, that some optimal solution makes the same first choice as the greedy rule, and optimal substructure, that after that choice the rest is a smaller instance of the same problem. Then the argument repeats until the problem is solved.
To prove the greedy-choice property I use one of two techniques. An exchange argument takes any optimal solution and swaps elements to make it agree with the greedy one without making it worse, as for shortest-job-first or Huffman coding. Greedy stays ahead shows by induction that after every step the greedy solution is at least as good as any other on some measure, as for interval scheduling by earliest end time.
To disprove one, I look for a small counterexample, ideally by comparing against brute force on small random inputs. Classic failures: largest-coin-first with coins 1, 3, 4 (6 = 3 + 3, not 4 + 1 + 1); value-per-weight for 0/1 knapsack, where indivisible items make a dense heavy item block two lighter ones that are better together, though it is optimal for fractional knapsack where items can be split.
When choices interact like that, I switch to dynamic programming, which tries every option for the last choice. Greedy algorithms that are correct include Dijkstra's shortest paths with non-negative weights, Prim's and Kruskal's minimum spanning trees, Huffman coding and interval scheduling.
What the interviewer is listening for
- The two properties and what they mean.
- Exchange and stays-ahead proofs, with examples.
- A habit of looking for counterexamples, and knowing when to use DP instead.
Common mistakes
- Assuming a plausible greedy rule is correct without proof or testing.
- Confusing fractional and 0/1 knapsack.
- Thinking greedy and DP are interchangeable.