Greedy vs Dynamic Programming in Interviews: How to Choose

Use greedy only when you can say why one local choice is safe, and switch to dynamic programming as soon as a shared budget (a capacity, a deletion allowance, a coin total) makes your choices interact. As of 2026-10-19, TrueInterview's bank holds 129 candidate-reported greedy questions from 23 big-tech companies, and 73 of them were reported in phone screens. The most-linked one is an applied scenario, Find Optimal Commute at Databricks, linked from 12 candidate write-ups. Our view: the deciding skill is defending the local rule in two sentences, or finding a small counterexample and writing the DP instead.

Disclosure: TrueInterview is an interview-preparation product and publishes this article. Facts about other products come from their public pages on the dates listed under Sources.

What is the real difference between greedy and DP?

Greedy commits to one choice per step and never revisits it; dynamic programming weighs every choice in the recurrence and stores each subproblem's answer. The UTA algorithms lecture notes say both rely on optimal substructure, where an optimal solution contains optimal solutions to its subproblems. The UTA notes add that with a greedy choice "We only need to consider one choice" instead of all of them.

That difference sets the cost: greedy is usually a sort plus one pass, while DP pays for a table with one cell per subproblem. GeeksforGeeks describes dynamic programming as solving each subproblem "only once, storing its solution", while greedy picks the locally best option "without considering the overall effect on the solution". The table puts the two side by side, with each source named in its row.

Our take: greedy wins whenever you can prove it, because the code is shorter and the interviewer gets the proof as a bonus signal. DP wins whenever you cannot, because a correct O(n·W) table beats a fast wrong answer. Do not treat them as rivals of equal standing: DP is the safe default, and greedy is an optimisation you earn with an argument.

Which signals point to greedy, and which point away?

A shared budget is the strongest signal that greedy will fail. PracHub's guide puts it in one line: "Budgets make choices interact, and interacting choices break the greedy choice property." When there is no budget and the input has a natural order (finish time, deadline, value per unit), greedy is worth testing; when there is one, test small cases before you commit.

PracHub's guide gives two habits that turn this into a routine. PracHub's guide advises reading the constraint bounds before choosing a technique, and if no counterexample appears quickly, its advice is to "write the DP and offer greedy as an optimization on top." The counterexample shape it suggests, one attractive item blocking two modest ones, is the one to try first.

Coin change shows the shape. With coins of one, three and four and a target of six, the largest-coin-first rule takes four, one and one, while three plus three uses only two coins. The attractive coin blocked two modest ones, which is the exact failure the budget check predicts. GeeksforGeeks makes the same split for knapsack: greedy gives the best answer for fractional knapsack but not for 0/1 knapsack.

Our take: the wording of the prompt is a weak signal and the constraints are a strong one. "Maximum", "minimum" and "optimal" appear in greedy and DP prompts alike. A capacity, a limit on deletions or a fixed total appears mostly in the problems where greedy breaks, so read the constraint block before the story.

Where do greedy questions show up in reported big-tech loops?

Mostly in phone screens. Of the 129 greedy questions in TrueInterview's bank, 73 were reported in phone screens, 37 onsite and 31 in online assessments; a question can be reported in more than one round. The set is current, too: 117 of the questions were last reported within the 12 months before 2026-10-19.

Phone-screen questions most often add arrays and strings, while onsite ones add sorting and heap, so the drill differs by stage.

If your next round is a phone screen, the reports point to array and string questions where the rule has to come out fast and be defended. If you have an onsite, sorting and heap each carry 7 of the 37 onsite questions, so make sort-then-sweep and priority-queue code automatic. GeeksforGeeks notes that greedy implementations "sometimes sort the array" and "sometimes also use a priority queue to get the next optimal item".

By company, Google has the most greedy questions in the bank (22), followed by Amazon (20), Uber (13), ByteDance (12) and Microsoft (12). Dated examples show the range candidates reported:

These are candidate-reported questions reconstructed for practice, not any company's official question list. Our view: the phone-screen skew is the reason to rehearse the whole sequence (rule, code, proof) under a timer, because a phone screen rarely leaves room to recover from an unproven rule.

Which reported questions should you practise first?

Start with the applied questions from Databricks, Google, Anthropic and OpenAI, then the classics. Find Optimal Commute leads with 12 write-ups, Longest-Match Tokenizer has 10 across Google and Anthropic, and Meeting Rooms / Interval Scheduling Variants has 9 at Google. The level split below uses candidates' self-reported levels on their write-ups.

The classics look busier than they are. Best Time to Buy and Sell Stock II is filed under 7 big-tech companies but linked from only 4 write-ups. Jump Game is filed under 3 companies and linked from 2 write-ups, both from senior-or-above candidates. Minimum Operations to Reduce an Integer to 0 is filed under 3 companies and linked from no write-ups at all. Being filed under many companies is not the same as being written up often, so give most of your practice time to the top four rows of the table and use the classics as short proof drills.

Three of those rows deserve a note on technique, by our reading of the titles only. Longest-Match Tokenizer names a longest-match rule, which is a greedy rule by construction, so the senior question is whether taking the longest token can strand characters a later token needed; when it can, a DP over string positions is the fallback. Data Labeling Task Scheduler and Job Scheduler are scheduler titles, where the usual tools are a sort by time and a heap of what is running, and the budget check (workers, capacity) tells you whether the choices interact.

How do you prove a greedy choice in the interview?

State the rule in one sentence, then show that an optimal solution can be changed to start with your choice without getting worse. PracHub's guide says that once the loop is written, "the interviewer asks why it works, and that is the actual question."

The standard tool is the exchange argument. The UTA lecture notes describe it as exchanging the first step of an optimal solution for the greedy choice and showing "this choice reduces the problem to a similar one but smaller". PracHub's guide is blunt about the alternative: "If you only do the first half, you have a heuristic, and the interviewer knows it."

Interviewers do ask for it. In a question PracHub's guide attributes to Meta, the prompt asked for an O(n) algorithm and an explicit correctness justification alongside it. The same guide says interviewers "accept this in about two sentences, and candidates who skip it get asked for it anyway". Rehearse those two sentences for Meeting Rooms / Interval Scheduling Variants and Jump Game until they come out without a pause.

Worked example: Meeting Rooms / Interval Scheduling Variants

This question was reported at Google in a phone screen, last reported 2026-06, and 6 of its 9 write-up links come from senior-or-above candidates. If a variant asks for the largest set of non-overlapping meetings, the greedy rule is the one the UTA notes give for activity selection: "Choose activity with the earliest finish time".

The two-sentence proof goes like this. Take any optimal schedule and swap its first meeting for the earliest-finishing one; nothing that followed is blocked, because the swapped-in meeting ends no later. What remains is the same problem on the meetings that start after it, so the argument repeats.

Now change one constraint. If the variant adds weights, or a budget that lets one meeting reduce what others can take, the choices interact. Try a two-meeting counterexample: a short meeting worth one that finishes first and overlaps a long meeting worth ten. Earliest-finish takes the one, the optimum is the ten, and the rule is broken. When earliest-finish breaks like this, sort by end time and write a DP over the sorted intervals. The UTA notes point out that activity selection itself could be solved with dynamic programming once its substructure is characterised, and that greedy's advantage is choosing an activity "without having to solve all subproblems".

What mistakes cost candidates the most?

In our view, the costliest mistake is stopping when the code passes the sample cases, because a rule that survives the samples is a guess until you prove it or fail to break it with two or three items. Two other mistakes show up in PracHub's guide, and each has a direct fix.

First, treating fewest moves or minimum steps in the prompt as a greedy signal. PracHub's guide notes that "BFS minimizes a count while making no locally optimal choice at all." A minimum count over states points to BFS or DP as often as to greedy.

Second, proving only half the algorithm. PracHub's guide names the mistake directly: "Proving the greedy choice is not the same as proving the greedy algorithm". After the exchange step, say why the remaining problem has the same shape, or the argument has a gap.

Our take: plan for a constraint change before the interviewer makes one. When you finish a greedy solution, name the constraint that would break it (weights, a capacity, a limit on deletions) and say which DP you would switch to.

What changes at senior and staff level?

Candidate write-ups link these greedy questions 99 times from candidates who reported a senior, staff-plus or manager level and 114 times from junior, new-grad or intern candidates. Several of the most-linked applied questions skew senior against that near-even baseline: Longest-Match Tokenizer is 8 to 2, Data Labeling Task Scheduler 6 to 2 and Meeting Rooms / Interval Scheduling Variants 6 to 3. Dynamic-programming-tagged links lean the other way, 2 senior-or-above to 6 junior-or-below.

The DP figure rests on 8 links, so treat it as a lean rather than a rule. Smaller applied questions point the same way as the big ones: Split Stay Booking is linked from 3 senior-or-above write-ups and 1 junior one, and Account Balancing from 3 and 1. Role matters a little too: intervals account for 22% of greedy write-up links from machine-learning, AI, research and data-science candidates against 10% from software engineers, but on 18 links against 192.

Our take: at senior level, expect the greedy rule to sit inside a realistic scenario (a commute, a tokenizer, a task scheduler) and expect to be judged on the justification and on what breaks when a constraint changes. Recalling a textbook DP table is less of the signal. Before you code, say which constraint would force a DP, and say it unprompted.

Down-leveling note (our view): because most of these questions surface in phone screens, a greedy question is more likely to decide whether you reach the onsite than which level you are offered. In our view the level is set later, by design depth, the project deep dive and the scope of your behavioral stories. A greedy rule you cannot defend still matters at senior level: it reads as guessing, and it can end the loop before the rounds that carry the level.

How we counted

Counts come from TrueInterview's question bank as of 2026-10-19 and cover 129 greedy-tagged practice questions that candidates reported at big-tech companies. Every question in the set carries the greedy tag by selection, so co-tag counts describe what greedy appears with, not how common greedy is. Level splits count write-up links by each candidate's self-reported level, and a link count measures what candidates wrote up, not how often a company asks a question.

FAQ

Is Dijkstra greedy or dynamic programming?

Dijkstra's algorithm is greedy. At each step it settles the closest unsettled vertex and never revisits it, which is safe only because non-negative edge weights mean no later path can make that vertex closer. Bellman-Ford, which relaxes every edge repeatedly and handles negative weights, is the dynamic-programming counterpart. If an interviewer adds negative edges to a Dijkstra prompt, that is the constraint change that breaks the greedy choice, and naming it before you are asked is the senior-level answer.

Is BFS or DFS greedy?

Neither. BFS explores states level by level and finds the fewest steps on an unweighted graph, and DFS explores one branch fully before backtracking; neither commits to a locally best choice. PracHub's guide makes the point about BFS directly: it minimises a count "while making no locally optimal choice at all". When a prompt asks for minimum moves between states, think BFS first, then DP if the state space has overlapping subproblems.

Why does greedy fail for coin change and 0/1 knapsack but work for fractional knapsack?

Fractional knapsack lets you take part of an item, so the UTA notes' rule, "Take as much of the article with the highest value per pound", never wastes capacity. PracHub's guide notes that coin change and 0/1 knapsack "look nearly identical" to greedy-solvable problems "and do not" work that way. In both, items are all-or-nothing and draw on one shared total, so an attractive early pick can block a better pair.

Should you write the DP first if you are unsure?

Yes, if a few minutes of counterexample hunting has not settled it. A correct DP with a stated recurrence is a complete answer, and you can then offer the greedy rule as an optimisation with its proof. Writing greedy first and discovering the counterexample after coding costs more time, because you rebuild the solution instead of trimming it. The exception is a prompt with no shared budget and an obvious sort order, where greedy with a short proof is faster.

Your practice plan

A three-week plan for someone working full time:

1. First week, rule-plus-proof drill. These two are chosen for their clean proofs, not their frequency. Solve Meeting Rooms / Interval Scheduling Variants and Jump Game. For each, say the rule in one sentence and the exchange argument in two, aloud and under a timer.
2. First week, lower-bound proof. Solve Best Time to Buy and Sell Stock II and explain why summing every positive day-to-day gain cannot be beaten. This is a proof by matching an upper bound rather than by exchange.
3. Second week, shared-budget drill. Work coin change and 0/1 knapsack against fractional knapsack: break the greedy rule with a two- or three-item counterexample, then write the DP table; GeeksforGeeks lists both as problems where DP, not greedy, gives the best solution.
4. Second week, the tokenizer. Solve Longest-Match Tokenizer with the longest-match rule, then ask whether a dictionary exists where longest-first fails, and sketch the DP over positions you would fall back to.
5. Third week, the applied set. Solve Find Optimal Commute and Data Labeling Task Scheduler under phone-screen timing, and run the budget check before writing code.
6. Third week, onsite only. If you have an onsite, add the onsite-reported Job Scheduler from Lyft and Mining Block from Coinbase, and keep your sort-then-sweep and priority-queue code fast, since sorting and heap are the most common onsite co-tags.
7. Throughout. TrueInterview says every question has a reference solution and that coding answers are judged on hidden tests that show the case you failed; use the failed case as a free counterexample to your greedy rule.

Sources

• TrueInterview question bank — greedy at big-tech companies — counted 2026-10-19
• Greedy Algorithms — checked 2026-10-19
• Greedy Approach vs Dynamic programming - GeeksforGeeks — checked 2026-10-19
• Greedy Algorithm Interview Questions: When Greedy Works, When It Fails | PracHub Knowledge Hub — checked 2026-10-19
• Greedy Algorithms Tutorial - GeeksforGeeks — checked 2026-10-19
• Interview prep compared: your application, end to end · TrueInterview — checked 2026-10-19

Last reviewed: 2026-10-19.