Top 4 Greedy Interview Questions
Browse 4 real-world technical and behavioral interview questions about Greedy. Review scenarios, edge cases, and architectural best practices.
Shipping packages within D days minimises a maximum. Now place m sensors at fixed positions so the closest pair is as far apart as possible. What changes in the binary search?
It is still binary search on the answer, over the gap rather than the positions, but the predicate flips. A gap that works means every smaller gap works, so you want the last feasible value, which needs lo = mid with a ceiling midpoint. Sort first, check each gap greedily, and the cost is O(n log n + n log R).
Given package weights in a fixed order, find the smallest ship capacity that delivers them all within D days
When you cannot construct the answer but can cheaply test a candidate, and that test is monotone, binary search the answer's numeric range instead of the input. The feasibility check here is greedy day-packing, giving O(n log S) time, and the whole implementation hinges on one loop invariant. It also connects monotonicity to the point an interviewer is testing.
Given a list of meetings with start and end times, pick the largest set of them that do not overlap.
Sort by finishing time and take every meeting that starts no earlier than the last one you took. Earliest start and shortest duration both look reasonable and both give provably smaller answers, and the exchange argument for earliest finish is what the question is really asking for.
How do you know a greedy choice is safe and not merely plausible?
A greedy choice is safe when you can show at least one optimal solution contains it, usually via an exchange argument that swaps an optimum's first choice for yours without losing anything. Interval scheduling by earliest finish time admits that swap; coin change with arbitrary denominations does not.