Greedy Algorithms Coding Interview: Justify the Choice

In a greedy algorithms coding interview, the code is rarely the hard part. The hard part is saying why the choice you made is safe. Interviewers use greedy problems to see whether you can tell a correct greedy from one that merely looks plausible, and whether you notice when the whole approach should be abandoned. This article gives you a four-step script — state, justify, test, analyse — and walks it through the greedy problems that come up most often.

What a Greedy Algorithm Actually Is (and What It Is Not)

A greedy algorithm builds a solution step by step, always taking the option that looks best right now, and never revisiting that choice. That single sentence is the whole pattern. Everything else in an interview is about whether the pattern is safe here.

It helps to place greedy next to the approaches it gets confused with:

• Brute force tries every combination. It is always correct and usually too slow.
• Dynamic programming also builds a solution step by step, but it keeps multiple candidate states because an early choice may need to be undone. It pays for that flexibility with memory and time.
• Divide and conquer splits the input into independent parts, solves each, then combines. Greedy does not split; it commits.

The two conditions that make greedy correct

For a greedy algorithm to be correct, two things must hold.

The greedy choice property. The option you pick first can be part of some optimal solution. Not every optimal solution, necessarily — just one. If taking the earliest-finishing interval can never rule out the best answer, the choice is safe.

Optimal substructure. After you commit to that choice, what remains is a smaller instance of the same problem. Solve it the same way and you are done.

In plain language: the first choice never hurts, and the rest of the problem looks like the problem you started with.

Greedy is a strategy, not a data structure

The same problem can be solved greedily or not, depending on the constraint. Coin change is greedy-friendly for many real currency systems and greedy-hostile for arbitrary denominations. Fractional knapsack is greedy; 0/1 knapsack is not. Saying "this is a greedy problem" is less useful than saying "this is greedy because of this constraint."

That distinction is what the interviewer is listening for.

The Four-Step Script: State, Justify, Test, Analyse

When a greedy idea occurs to you, do not start typing. Run this script out loud. It gives you something useful to say while you are still thinking.

Step 1 — State the greedy choice explicitly

One sentence, with the sort key or comparison named: "At each step I take the interval that finishes earliest." Vagueness here is the most common failure. "I'll be greedy about it" tells the interviewer nothing, and it usually means you have not decided yet.

Step 2 — Justify with an exchange argument

An exchange argument is shorter than it sounds. Show that swapping any optimal solution's first choice for the greedy one does not make the solution worse. Two sentences is enough in most interviews: "Suppose an optimal solution picks a different first interval. Mine finishes no later, so it leaves at least as much room for everything after it. Swapping them keeps the rest valid."

Step 3 — Test with a counterexample attempt

Try to construct a small case where the greedy choice loses. Say the attempt out loud even when it fails: "Let me try to break this. What if two intervals start at the same time?" A failed attempt is evidence, and it shows the interviewer you are checking rather than hoping.

Step 4 — Analyse time and space

Name the dominant step first, then the notation. "The sort dominates, so it is n log n; the scan is linear and gets absorbed. Extra space is constant."

Why this order helps

State, justify, test, analyse is also a good order under pressure. If you have stated the choice, you have already said something concrete. If the justification is shaky, the counterexample step will usually surface it before you write twenty lines of code around a broken idea.

Worked Example 1: Interval Scheduling (Activity Selection)

Problem. Given a set of intervals, choose the maximum number that do not overlap.

Greedy choice. Sort by end time. Take each interval whose start is at or after the end of the last interval you took.

Why the obvious alternatives fail. Two choices look equally reasonable and both are wrong.

• Earliest start. Take [0, 10], [1, 2] and [3, 4]. Picking [0, 10] first blocks both of the others, so you get one interval instead of two.
• Shortest interval. Take [0, 5], [4, 6] and [5, 7]. The shortest is [4, 6], but taking it blocks both [0, 5] and [5, 7], so you get one interval instead of two.

The exchange argument in plain words. The interval that finishes earliest leaves the most room for everything after it. Any other first choice ends at the same time or later, so it can only reduce what remains available.

Complexity. O(n log n), dominated by the sort. Extra space is O(1) beyond the input and the output, assuming an in-place sort; a sort that copies the input can cost O(n) extra.

If asked for a more formal proof. Say: consider an optimal solution O. Let g be the earliest-finishing interval. If O's first interval is g, done. Otherwise replace O's first interval with g. Because g finishes no later, the remaining intervals in O still start after g ends, so the replacement is still a valid solution of the same size. Repeating this exchange turns O into the greedy solution without shrinking it.

Worked Example 2: Coin Change With Canonical Denominations

Greedy choice. Repeatedly take the largest coin that fits.

The trap. This is correct for many real currency systems, but not in general. Take denominations 1, 3, 4 and an amount of 6. Greedy takes 4, then 1 and 1: three coins. The optimal answer is 3 and 3: two coins. Same problem, different denomination set, and greedy is now wrong.

How to phrase the caveat honestly. "This is greedy-correct for canonical systems. If the denominations are arbitrary, I would reach for dynamic programming instead." That sentence is worth more than a confident wrong answer.

Complexity. Sorting the denominations is O(k log k) for k coin types. The greedy loop then takes O(number of coins emitted) time, which is bounded by O(amount) in the worst case (all 1s). The dynamic-programming alternative is O(amount × k) time and O(amount) space — worth naming, because it is the fallback when the denominations are not canonical.

The lesson. Naming the condition under which your approach breaks is a strength, not a weakness. Interviewers are checking calibration, and this is the cheapest place to show it.

Worked Example 3: Jump Game and Minimum Refuelling Stops

Jump Game: greedy that looks forward

Track the furthest index reachable so far while scanning once. For each index i, if i is greater than the current reach, return false; otherwise set the reach to the larger of its current value and i plus the jump length at i. Return true at the end. One pass, O(n) time, O(1) space. The invariant to narrate: "After processing index i, the reach is the furthest index reachable using only indices up to i."

Minimum refuelling stops: greedy that defers

You have a fuel tank, a target, and a list of stations. The greedy that works is not "stop at the next station" — it is "drive as far as you can, and when you run out, retroactively decide you stopped at the best station you have passed." Add each station you pass to a max-heap; when fuel runs out, pop the largest until you can continue, counting each pop as a stop. If the heap empties before you can continue, the target is unreachable.

Contrast the two

Both commit to a final set of choices without backtracking, but they commit differently: one decides eagerly at each step and looks forward, the other defers the commitment until it is forced. Being able to say which style you are using is a strong signal.

Talking About Time Complexity Without Reciting Big-O

Start with where the cost lives, not with the symbol. Saying "the sort is the expensive part, so the whole thing is n log n" tells the interviewer more than a bare "O(n log n)", because it shows you know which line of code is doing the work.

Then be precise about which case you mean:

• Worst case is the default in interviews. Say so if you are quoting average instead.
• Average case matters when you rely on hashing or randomised pivots.
• Data structure costs are part of your answer. Heap pushes and pops are log n each; a hash lookup is expected constant time, not guaranteed.

For space, state whether you are counting the input and whether you are counting the output. "O(1) extra space, ignoring the input and the output list" is a complete answer. "O(1) space" on its own is not.

If asked to optimise, name the bottleneck before proposing a change. Guessing wastes interview time and usually produces a slower solution. A common follow-up is "can you do it in one pass?" — for Jump Game the answer is yes. For interval scheduling the sort is the bottleneck, so the best you can do is O(n log n) unless the input arrives pre-sorted, in which case a single linear pass suffices.

Common Greedy Algorithms Coding Interview Questions and What Each One Tests

In a greedy algorithms coding interview, the follow-ups matter as much as the first answer. Here is the one sentence a strong candidate says first for each of the classics.

• Interval scheduling and meeting rooms. "I sort by end time, because the earliest finish leaves the most room." Tests whether you can justify a sort key rather than picking one by habit.
• Huffman coding. "I repeatedly merge the two lowest-frequency nodes: the two lowest-frequency symbols can be made siblings at maximum depth in some optimal tree, so merging them first is safe." Tests whether you can explain a greedy that builds a tree.
• Fractional knapsack versus 0/1 knapsack. "Fractional is greedy by value-to-weight ratio; 0/1 is not, because taking an item whole can block a better combination." Tests whether you know where greedy stops working.
• Dijkstra's algorithm. "I settle the closest unsettled node next, which is safe because edge weights are non-negative." Tests whether you understand why that assumption matters.
• Gas station / circular tour. "I track a running tank and reset the start whenever it goes negative, because a deficit cannot be fixed by starting later within the same stretch." Tests whether you can argue a single-pass invariant.
• Minimum spanning tree (Kruskal, Prim). "Kruskal takes edges in weight order and skips any that would form a cycle." Tests whether you can connect greedy to a known proof.

Notice that none of these answers is a definition. Each is a choice plus a reason.

When Greedy Is the Wrong Answer — and How to Say So

Watch for three signals that greedy will not work:

1. Overlapping subproblems. The same subproblem appears in several branches, which is the fingerprint of dynamic programming.
2. A choice that affects future options in a non-monotone way. If taking the best option now can make a later option strictly worse in a way you cannot bound, greedy is unsafe.
3. A counterexample you can construct in seconds. If you found one that fast, there are probably more.

Pivot as a decision, not a failure: "I would not trust greedy here because of this case; let me switch to DP." Then say what the DP state would be. Interviewers reward this because calibration is harder to teach than any single algorithm, and because it shows you are testing your own reasoning instead of defending it.

The same honesty applies in the other direction. If you can state the greedy choice and the exchange argument cleanly, say so and move on — do not invent doubt you do not have.

Practising the Reasoning, Not Just the Code

Rehearse out loud. State the choice, justify it, test it, analyse it — the same four steps every time, until the order is automatic.

Three habits make the difference:

• Record yourself on two or three problems and listen for the moment your justification goes vague. That moment is your actual weak spot, and it is usually the same one every time.
• Use a timer. Aim to produce the justification in under a minute before you write any code. If you cannot, the idea is not ready.
• Keep a one-page log. For each greedy problem you have explained aloud, write the choice, the justification in one line, and the counterexample you tried. Reviewing that log before an interview is faster than re-reading solutions.

For a related read on stating trade-offs out loud, see Python Interview Questions: Concepts and Trade-Offs, and browse our blog for more.

The takeaway: greedy problems are scored on your reasoning, not your typing. Say the choice, defend it in two sentences, try to break it, then give the complexity — and when it breaks, say so early and switch.

Frequently asked questions

How do I know whether a problem is meant to be solved greedily?

Look for a local choice that never needs to be undone. If the best option now cannot make the remaining problem harder, greedy is a candidate. If the same subproblem keeps reappearing, or a choice visibly changes later options in a non-monotone way, dynamic programming is usually the intended route. Saying which of these two situations you are in is most of the answer.

Do I need to prove the greedy choice is correct in an interview?

You need to justify it, which is lighter than a formal proof. A two-sentence exchange argument — swapping an optimal solution's first choice for the greedy one does not make it worse — is normally enough. Keep the fuller version ready in case the interviewer asks for more rigour.

What is the difference between greedy and dynamic programming in an interview answer?

Greedy commits to one choice and never revisits it. Dynamic programming keeps several candidate states because an early choice may need to be undone. The practical test is whether subproblems overlap: if they do, DP is usually the safer answer.

Which greedy algorithms interview questions come up most often?

Interval scheduling and meeting rooms, Huffman coding, fractional versus 0/1 knapsack, Dijkstra's algorithm, gas station or circular tour, and minimum spanning tree via Kruskal or Prim. Each one tests a slightly different part of your reasoning, so practise the justification rather than the code.

How do I explain time complexity for a greedy solution without rambling?

Lead with the dominant step rather than the notation: 'the sort dominates, so it is n log n'. Say which case you mean, mention the cost of any heap or hash operations you rely on, and state whether your space figure counts the input and the output.

What should I say if my greedy approach turns out to be wrong?

Name the counterexample, then pivot as a decision: 'I would not trust greedy here because of this case; let me switch to DP.' Interviewers tend to reward that calibration more than a defended wrong answer.

Read our Python interview walkthrough on stating trade-offs out loud.