Greedy Algorithm Interview Questions: When Greedy Works, When It Fails

You write the greedy loop in two minutes. Then the interviewer asks why it works, and that is the actual question. A greedy algorithm builds an answer one irrevocable choice at a time, always taking whatever looks best right now: the earliest finish time, the largest coin, the nearest unsettled node. It is correct only when some optimal solution starts with that move (the greedy choice property) and the remainder is a smaller copy of the same problem (optimal substructure). Interval scheduling by earliest finish, fractional knapsack, Huffman coding, and Dijkstra all clear that bar. Coin change and 0/1 knapsack look nearly identical and do not. Miss the distinction and greedy returns a fast, confident, wrong answer.

Every section below opens with a question someone was actually asked. Three of them have a greedy answer you can defend in a sentence. The rest punish the instinct.

Key Takeaways

• Greedy is a two-part obligation. State the local rule in one sentence, then show an optimal solution can be bent to begin with it. If you only do the first half, you have a heuristic, and the interviewer knows it.
• The fastest signal that greedy will fail is a shared budget: a deletion allowance, a knapsack capacity, a coin total. Budgets make choices interact, and interacting choices break the greedy choice property.
• "Fewest moves" is not a greedy signal. BFS minimizes a count while making no locally optimal choice at all. Dijkstra is the shortest-path algorithm that genuinely is greedy, and only because edge weights are non-negative.
• Read the constraint bounds before choosing a technique. A bound like n ≤ 2^61 − 1 rules out any table indexed by value, which forces you either to prove the greedy rule or to memoize on the reachable states.
• Hunt counterexamples at n = 2 or 3, shaped as one attractive item blocking two modest ones. If nothing surfaces in a couple of minutes, write the DP and offer greedy as an optimization on top.

When a greedy algorithm is provably correct (and how to argue it)

Three proof shapes cover nearly every greedy algorithm an interviewer will accept:

• Exchange argument. Show that any optimal solution can be nudged, one swap at a time, into one that begins with your greedy choice without getting worse. The full recipe lives in the Amazon scheduling section below, which runs it end to end.
• Greedy stays ahead. Show that after k choices, greedy's partial solution is at least as good as any other k-choice prefix. Earliest-finish-time interval scheduling is usually taught this way, though the video further down proves the same result with an exchange instead; both arguments are valid.
• Matching lower bound. Prove that no solution can beat some bound, then show greedy achieves it. The Meta parenthesis question below is settled this way, in two sentences.

Two neighbouring situations look like greedy correctness questions and are not. Sometimes the greedy rule only answers feasibility — "can we finish at speed x?" — and the real optimization is a monotone search over x. That is binary search on the answer, and the proof burden shifts from an exchange to monotonicity of the predicate. And sometimes "repeatedly take the current best" is just the implementation, running on a heap, with no optimality claim attached; Top K Frequent Elements is the standard drill for that machinery.

There is also greedy shipped knowingly without a proof, as a named heuristic.

Asked at Microsoft — Implement greedy decoding and beam search You get a scoring function that returns log-probabilities for the next token given a prefix, plus an end-of-sequence token and a length cap. Implement greedy decoding, which always takes the single highest-scoring next token, and then beam search, which carries the k best partial sequences forward at every step instead of one.

Greedy decoding is the purest greedy loop most engineers ever ship, and it is not optimal: the highest-probability sequence can begin with a token that is not the highest-probability first step. Beam search exists precisely because that guarantee is missing; it widens the frontier from one candidate to k and still proves nothing. Saying "this is a heuristic, and here is why that is acceptable" is a legitimate interview answer, as long as it is a decision rather than an oversight.

A greedy sweep is one pass plus an invariant you can defend

Asked at Meta — Solve two string algorithm tasks Two parts; the first is the greedy one. Given a string of up to 100,000 characters containing only ( and ), report the fewest parentheses you would have to insert, at any positions, to make it balanced. The prompt asks for an O(n) algorithm and, explicitly, for the correctness justification alongside it.

The rule is one line: walk left to right, match every ) against the nearest ( that is still free, and count whatever cannot be matched.

def min_insertions_to_balance(s: str) -> int:
    open_unmatched = 0   # '(' still waiting for a partner
    inserts = 0          # ')' that arrived with nothing to match
    for ch in s:
        if ch == '(':
            open_unmatched += 1
        elif open_unmatched:
            open_unmatched -= 1
        else:
            inserts += 1
    return inserts + open_unmatched

O(n) time, O(1) space, which is the tighter of the two budgets the question allows.

Trace "())((". The first ( raises the counter to 1, the first ) drops it back to 0, the second ) finds nothing to consume so inserts becomes 1, and the last two ( leave open_unmatched at 2. Answer 3, and wrapping the string as ( + "())((" + )) produces (())(()), which is balanced with exactly three additions.

The proof has two halves, and neither is an exchange argument. The sweep computes the maximum number of pairs that can be matched inside s, so every character it fails to match needs its own inserted partner: that is a lower bound. Inserting exactly one partner per leftover character produces a valid string: that is achievability. Lower bound equals achieved count, so the answer is optimal. Interviewers accept this in about two sentences, and candidates who skip it get asked for it anyway.

Where the technique stops: add a second bracket type and the counter is no longer enough. ([)] has perfectly balanced counts for both types and is still invalid, because a counter cannot see nesting order. That needs a stack, and the insertion question stops being well posed in the same way.

The exchange argument, run on a schedule where you can see the swap

Asked at Amazon — Compute minimum delivery days You have N distribution centers numbered 1 through N, and a list of orders each tagged with a destination city. A center whose own number matches the city clears every outstanding order for that city in one day. A center whose number differs needs two consecutive days and is tied up for both. Each center handles at most one city per day. Report the fewest calendar days that clear the whole list.

The exchange argument is the workhorse proof for greedy, and it is mechanical. Take an arbitrary optimal solution. Find the first place it disagrees with your greedy rule. Swap greedy's choice in. Show the result is still feasible and still just as good. Induct.

Here the greedy rule is "serve city c from center c whenever center c exists." Suppose an optimal schedule instead has center j spending two consecutive days on city c, while center c spends two consecutive days on some other city k. Reassign: center c takes city c for a single day, and center j takes city k on the two days it had already reserved. Center j is free on those days precisely because we lifted city c off it. Total center-days fall from four to three and the makespan cannot increase, so the swapped schedule is at least as good.

That settles the assignment, and it settles nothing else. You still owe the calendar: how the remaining two-day jobs pack into N centers running in parallel, given that a center freed after a one-day job becomes available the next morning. This is the mistake worth naming out loud. Proving the greedy choice is not the same as proving the greedy algorithm, and a candidate who conflates them has proved a third of what they think they have.

Two other techniques cover the cases exchange does not. "Greedy stays ahead" shows that after k steps greedy's partial solution is at least as good as anyone else's first k steps. Dijkstra uses neither; its correctness is an inductive invariant on the set of settled nodes. There is also a clean characterization behind all of this — an independence system is a matroid exactly when greedy finds a maximum-weight basis under every weight function — but no interviewer will ask you for it, and neither problem above is a matroid instance.

When the greedy rule is hiding in the input's bit structure

Asked at Salesforce — Minimize steps to reduce integer Start from a positive integer n as large as 2^61 − 1. If n is even you may halve it; if n is odd you may add one or subtract one. Reach 1 in as few steps as possible. The prompt asks you to justify how you choose between n+1 and n−1 on every odd step, which is the whole problem.

Read the bound first. At 2^61 − 1 you cannot build a table indexed by value, and you cannot BFS over reachable values as a set. The bound is not decoration; it eliminates an entire family of answers before you write anything.

Halving is free progress, so the only real decision is which even neighbour to land on when n is odd. Both n−1 and n+1 are even, and the one divisible by 4 buys a second halving before the next decision. That is settled by the low two bits: if n ≡ 1 (mod 4) then n−1 is divisible by 4, and if n ≡ 3 (mod 4) then n+1 is. The single exception is n = 3, where n−1 = 2 reaches 1 in one more step while n+1 = 4 needs two.

def min_steps(n: int) -> int:
    steps = 0
    while n > 1:
        if n % 2 == 0:
            n //= 2
        elif n == 3 or n % 4 == 1:
            n -= 1
        else:
            n += 1
        steps += 1
    return steps

O(log n) time, O(1) space. On n = 7 the rule sends you up to 8 and then down through 4 and 2, four steps, tying the 7→6→3→2→1 route. On n = 15 it sends you to 16 and finishes in five, beating the downward route by one. On 2^61 − 1 it answers 62.

If that argument will not come out cleanly under pressure, memoized recursion costs you almost nothing and is provably right:

from functools import lru_cache

@lru_cache(maxsize=None)
def min_steps_memo(n: int) -> int:
    if n == 1:
        return 0
    if n % 2 == 0:
        return 1 + min_steps_memo(n // 2)
    return 1 + min(min_steps_memo(n - 1), min_steps_memo(n + 1))

The reason this survives a 61-bit input is worth saying out loud. Every branch is followed by a halving, so the values reachable after d halvings sit in a narrow window around n / 2^d rather than spreading out. On 2^61 − 1 the memo holds 181 entries. A dictionary, not an array, is what makes that possible.

A shared budget is where greedy stops being defensible

Asked at Meta — Decide palindrome within k deletions Given a string s and a budget k, decide whether deleting at most k characters can turn s into a palindrome. The follow-ups ask for the minimum number of deletions actually required, a DP with its time and space trade-offs, and what you would do as the string grows.

The two-pointer trick from the single-deletion version is the trap. With one deletion allowed you can compare the ends, and on the first mismatch simply test both repairs in O(n) each, because after spending the budget there is nothing left to decide. With a budget of k, testing both branches at every mismatch is 2^k work. The greedy version — always skip the same side — has no argument behind it, because which side to spend on depends on what the rest of the string will need from the remaining budget.

The budget is the tell, and the fix is a DP that never makes a local commitment:

minimum deletions to make s a palindrome = len(s) − LPS(s)

where LPS is the longest palindromic subsequence, not substring. The recurrence is the standard interval DP: lps[i][j] = lps[i+1][j-1] + 2 when s[i] == s[j], otherwise max(lps[i+1][j], lps[i][j-1]). O(n²) time, and O(n) space if you roll the rows. The decision the question asks for is then just len(s) − LPS(s) ≤ k.

The scaling follow-up has an honest answer: no substantially subquadratic algorithm is known for this, so O(n²) with rolling rows is the bar, and what you optimize is the constant and the memory, not the exponent.

Under time pressure the decision looks like this:

Minimizing a count does not make a problem greedy

Asked at Pinterest — Find minimum shuttle transfers You get a set of shuttle loops, each given as the list of stops it cycles through forever. Board a shuttle at any stop on its loop and ride to any other stop on that loop; switching loops costs one more boarding. Given a source stop and a target stop, return the fewest shuttles you must board, or −1 if the target is unreachable. Up to 100,000 stops across all loops.

"Fewest" pulls candidates straight into a greedy frame, and the rule they reach for is "board the loop that reaches the most new stops." It fails, and the reason generalizes. The set of stops reachable after one boarding is an arbitrary set, not an interval and not anything a single boundary value can summarize. Without a frontier that advances monotonically, there is nothing for a greedy sweep to be greedy about, and a loop that adds two new stops may be the only bridge to the loop that serves the target.

The right model is BFS where loops are the edges and boardings are the levels.

Build a stop → loops index once, mark each loop used the first time you expand it, and each loop and each stop is touched once. O(S) time and O(S) space for S total stops, which is what makes 100,000 stops routine. Handle s == t before the loop; the answer is 0, and the question calls it out.

Solve Open the Lock BFS from Snapchat is the same lesson in different clothes. Turning each wheel toward the target digit is a local heuristic that a single deadend on the direct route invalidates. The state space is 10,000 combinations, so BFS over states is both correct and cheap.

Dijkstra is the greedy shortest-path algorithm; BFS never was

Asked at DoorDash — Compute delivery times on a grid A grid marks warehouses, customers, obstacles and open road. Moves go up, down, left or right at a cost of one step each. For every customer cell, report the fewest steps from any warehouse, or −1 if no warehouse can reach it. The follow-ups scale it to millions of cells and then make the cost vary per road cell.

Uniform cost means BFS, and the phrase "from any warehouse" means multi-source BFS: seed the queue with every warehouse cell at distance 0 and run one pass. O(mn) time and O(mn) space. The common mistake is running a separate BFS per customer, which multiplies the work by the number of customers and is what makes the millions-of-cells follow-up fail.

The second follow-up is the one that separates people. Once road cost varies per cell, the layer structure BFS depends on is gone and you switch to Dijkstra, O(mn log mn) with a binary heap (the Python idioms and traps for that heap are in Python heapq for Coding Interviews). Dijkstra is genuinely greedy: it permanently settles the nearest unsettled cell and never reconsiders it, and that commitment is safe only because costs are non-negative, so no later path can undercut a settled distance. Introduce one negative edge and the commitment breaks, which is exactly why Bellman-Ford exists at O(VE).

BFS, by contrast, is not greedy at all. It expands every cell at distance k before touching distance k+1 and discards nothing. Getting that distinction right out loud reads as someone who has thought about correctness rather than memorized patterns.

Sounds greedy, isn't: a reference table

The two knapsack rows are the cleanest illustration of the budget rule. Fractional items let you spend the last unit of capacity partially, so choices never block each other. Whole items share a fixed capacity, one attractive item can crowd out two modest ones whose combined value is higher, and the same rule that was optimal becomes a heuristic.

Practice these on PracHub

Real, company-tagged questions with runnable consoles, grouped by what each one drills.

Greedy you can actually prove

• Solve two string algorithm tasks (Meta) — Part A is the parenthesis sweep above; Part B, the shortest substring covering all of t, drills a sliding window that also commits as it advances.
• Compute Minimum Production Days (solution premium, console free) — earliest-legal-day scheduling under a cooling gap. One pass with a last-seen-day map, day = max(day + 1, last[x] + space + 1); on [1, 3, 1, 3, 2] with space = 2 the answer is 6.
• Minimize steps to reduce integer (Salesforce) — practice at deriving a greedy rule from the input's structure instead of guessing at it.

Where the greedy instinct is the trap

• Decide palindrome within k deletions (Meta) — the moment a local rule stops being defensible as a budget grows.
• Solve four algorithm design tasks (TikTok) — task 1 asks you to compare greedy and DP for wildcard matching directly, which is the rare case where greedy is right but only with a rollback pointer.
• Compute minimum delivery days (Amazon) — cost a single assignment before optimizing anything, then notice that the exchange argument leaves the calendar unfinished.

Name the model before you write code

• Find minimum shuttle transfers (Pinterest) — spotting that a "minimum count" objective is layered search, not a sweep.
• Solve Open the Lock BFS (Snapchat) — calibration for how quickly a plausible local heuristic dies on an obstacle.
• Compute delivery times on a grid (DoorDash) — the BFS-to-Dijkstra boundary, stated as a rule about cost uniformity rather than memorized.

Work the trap questions first.

FAQ

What is a greedy algorithm?

A greedy algorithm constructs a solution incrementally, taking the choice that looks best at each step and never undoing it. It is optimal only when the problem has the greedy choice property, meaning some optimal solution begins with the greedy move, and optimal substructure, meaning the rest of the problem is a smaller version of the same problem. Sorting or a single linear pass with a running invariant is the usual implementation shape.

How do I prove a greedy algorithm is correct?

Use an exchange argument: take any optimal solution, find the first choice where it differs from greedy, swap greedy's choice in, and verify the result is still feasible and still just as good. If that swap always works, greedy is optimal by induction. The other standard technique is "greedy stays ahead," showing greedy's first k choices are at least as good as anyone else's first k. A few problems need neither, including the parenthesis sweep, which is proved by a matching lower bound.

When does a greedy algorithm fail?

When choices interact, which in practice almost always means they share a budget: a knapsack capacity, a coin total, a fixed number of allowed deletions. A budget makes an early commitment change what is affordable later, and that is exactly the greedy choice property failing. Deciding whether a string is a palindrome within k deletions is the canonical interview version, and it needs DP.

Why does greedy fail for coin change?

Because taking the largest coin can leave a remainder that only small coins can fill. With denominations 1, 3 and 4 and a target of 6, greedy takes a 4 and then two 1s for three coins, while two 3s do it in two. With denominations 3 and 4 it is worse: greedy spends the 4, cannot fit a 3 into the remaining 2, and reports failure at 6 even though 3 + 3 works exactly. Greedy happens to be optimal for typical real currency systems, which is why the wrong intuition is so durable.

Is Dijkstra's algorithm greedy? Is BFS?

Dijkstra is greedy: it permanently settles the nearest unfinished node, and that commitment is safe only because non-negative edge weights guarantee no later path can beat it. BFS is not greedy, since it expands every node at distance k before touching distance k+1 and makes no locally optimal selection at all. Add a single negative edge and Dijkstra's commitment breaks, which is why Bellman-Ford exists.

Should I reach for greedy or dynamic programming in an interview?

Look for a shared budget or capacity. A knapsack limit, a coin total, a fixed number of allowed deletions, anything that makes one choice change what is affordable later, points to DP. Independent local decisions with a monotone objective point to greedy. When you are unsure, write the DP: a correct quadratic solution you can defend beats a linear one you cannot.