What is a greedy algorithm? | Interview Question

Q: What is a greedy algorithm?

**Target Audience:** Beginners preparing for coding interviews — you should know lists, loops and functions in Python; everything else is explained. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First You are at a buffet with a small plate, and you want the most delicious meal you can fit. One strategy: look at what is in front of you, take the thing that looks best *right now*, and never put anything back. That strategy is fast — no planning, no regrets — and for some buffets it is perfect. But imagine the best-looking dish is an enormous lasagne that fills the who

The problem

Question presented to candidate: "What is a greedy algorithm? How do you know when a greedy approach gives the optimal answer, and can you show one example where it works and one where it fails — in Python?"

What a strong answer should cover:

A one-sentence definition: build the answer step by step with the locally best choice and never undo a choice.
The two conditions for correctness — the greedy-choice property and optimal substructure — and the exchange argument used to prove the first.
A working example, typically interval scheduling by earliest finish time: sort, then one pass, O(n log n).
A failing example with a concrete counterexample (coin change with [1, 3, 4] and amount 6, or 0/1 knapsack), and that dynamic programming is the fix.
Python details: sorted(..., key=lambda iv: (iv[1], iv[0])) with a tuple key for deterministic ties, Python's sort being stable, and functools.cmp_to_key when the natural order is a pairwise comparison.
Testing a greedy rule against a brute force on small inputs before trusting it.

Code / implementation expected: Optional — a short Python greedy (interval scheduling or coin change) and its counterexample.

greedy

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you should know lists, loops and functions in Python; everything else is explained.
Difficulty: Medium
Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

You are at a buffet with a small plate, and you want the most delicious meal you can fit. One strategy: look at what is in front of you, take the thing that looks best right now, and never put anything back. That strategy is fast — no planning, no regrets — and for som

The solution is hidden so you can try first

16 min read · 12 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonInterval scheduling: three greedy rules vs brute force

Practice

PythonGreedy coin change vs dynamic programming

Practice

PythonFractional vs 0/1 knapsack: same greedy, different verdict

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.