Micro-questions over the greedy module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The failure mode
1. Give the mountain trail illustration.
Answer
Two branches: +150m, or +200m leading to −300m. Greedy takes +200 and ends at −100m; the optimal choice takes +150. A locally attractive choice locks out a better long-term outcome.
2. Name two problems where greedy works and two where it fails.
Answer
✅ Activity selection (take the job that finishes earliest) and Huffman coding (merge the two lowest-frequency nodes).
❌ Coin change with arbitrary denominations and 0/1 knapsack (value-per-weight ignores capacity interactions).
B. The vocabulary
3. What is a greedy choice?
Answer
The locally optimal decision made at each step without reconsidering past choices.
4. What is an exchange argument?
Answer
A proof showing that swapping any greedy choice for any alternative can never improve the outcome.
5. Is a greedy algorithm a heuristic?
Answer
No. A greedy algorithm is an exact algorithm producing the globally optimal answer when applicable — not an approximation.
6. What property do both greedy and DP require?
Answer
Optimal substructure — an optimal solution composed of optimal solutions to subproblems.
C. The coin change trap
7. Coins , amount 11 — does greedy work?
Answer
Yes: = 3 coins, which is optimal.
8. Coins , amount 6 — what happens?
Answer
Greedy takes 4 first, leaving 2, needing two 1s — 3 coins. Optimal is = 2.
9. State the failure precisely.
Answer
Taking 4 greedily closes off the path. The locally largest coin blocks the globally best combination.
10. What does that tell you about the problem statement?
Answer
Nothing in it distinguishes the two coin sets — which is why greedy must be proved, not felt.
D. A provably correct greedy
11. State the canoe pairing problem.
Answer
Pair people of known weights into canoes of maximum capacity . Minimise the number of canoes.
12. State the greedy strategy.
Answer
Always try to pair the heaviest remaining person with the lightest remaining person. If they exceed capacity, the heaviest goes alone.
13. Give the exchange argument.
Answer
Consider the heaviest person . If can share with anyone, they can share with the lightest person — because if an optimal solution pairs with a heavier , swapping and can only maintain or improve the result, since fits anywhere did.
14. What does that licence you to do?
Answer
Commit to the greedy choice and reduce the problem to the remaining people — which is exactly the inductive proof structure for correctness.
15. What familiar pattern does the implementation use?
Answer
Two pointers — left at the lightest, right at the heaviest, converging from both ends of the sorted array.
16. Why does right -= 1 happen unconditionally?
Answer
The heaviest person is always seated — either paired with the lightest, or alone. Only the left pointer is conditional.
E. Choosing
17. Give the three-row decision guide.
Answer
| Signal | Use |
|---|---|
| Locally best provably never worse (exchange argument holds) | Greedy — fastest when it applies |
| Choices interact — “best now” can block a better future | Dynamic programming |
| Small problem, need a correct baseline | Brute force |
18. State the key test.
Answer
“Can I prove the greedy choice is at least as good as any alternative using an exchange argument?” If yes, greedy is safe. If not, switch to DP.
19. What is the typical complexity of a greedy algorithm?
Answer
time — dominated by the sort that establishes the greedy criterion — and auxiliary space, since no memo table is needed.
20. What step do people most often miss?
Answer
The sort. Most greedy algorithms require first sorting by the greedy criterion — finishing time, weight, cost-per-unit.
21. Summarise the lesson in one sentence.
Answer
Greedy is exact when an exchange argument shows the local choice is never worse — and without that proof it is just a guess that happens to work on your examples.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- When Greedy Works — the module
- Selection & Scheduling — Question Bank
- What Makes a Problem DP — Question Bank
Software engineering
Infrastructure & security
Computer science
Hardware & engineering