Search
⌘K
Common Patterns
Greedy & Bin Packing
When local optimization leads to global solutions — greedy strategies, bin packing heuristics, and the tradeoffs interviewers expect you to reason about.
Problems involving resource allocation, scheduling, interval management, and bin packing are natural fits for multi-file coding challenges because they're easy to state but surprisingly tricky to get right. This almost always leads us to greedy algorithms as a candidate solution. The part that makes them interesting interview material is the tradeoff between correctness and speed: a greedy approach runs fast, but does it actually give you the right answer?
Interviewers are not testing whether you've memorized the a problem from your algorithms class. They want to see you reason about why a greedy approach works for a given problem, or catch when it doesn't. The AI will happily generate a greedy solution for almost anything you throw at it. Your job is to know when that's correct and when it's dangerously wrong.
You don't need deep prior expertise with greedy algorithms going into these interviews. Interviewers expect you to assimilate the core ideas quickly and apply them to unfamiliar problems. What matters is your reasoning process, not whether you've seen the exact problem before.
The greedy paradigm
The idea behind greedy algorithms is simple: at each step, make the choice that looks best right now, and never look back. No backtracking, no reconsidering. You commit to each local decision and hope (or prove) that the sequence of locally optimal choices leads to a globally optimal solution.
This works when two properties hold:
- Greedy choice property means that making the locally optimal choice doesn't prevent you from finding the globally optimal solution. In other words, you never need to undo a decision.
- Optimal substructure assumes after making a greedy choice, the remaining problem is a smaller instance of the same type of problem.
When both hold, greedy gives you the optimal answer and usually runs much faster than alternatives like dynamic programming. When either fails, greedy gives you something that looks reasonable but might be arbitrarily far from optimal.
Intuitively, you're usually going to disprove a greedy approach by counterexample than create a rigorous mathematical proof of these two properties. So being able to go "aha, if I make that choice first, then I'll miss the optimal solution in this way" is how most engineers will reason through whether greedy applies or not. Don't get hung up on a formal proof!
An example: coin change
Consider making change for 36 cents with coins of denominations 25, 10, 5, and 1. The greedy approach picks the largest coin that fits at each step: 25, then 10, then 1. Three coins total. And that happens to be optimal.
But change the denominations to 1, 3, and 4 and try making 6 cents. Greedy picks 4, then 1, then 1 which is three coins. The optimal answer is 3 + 3, just two coins. The greedy choice property doesn't hold here because picking the largest coin first backed us into a corner so we can disprove it with a counterexample.
Interval scheduling
Interval scheduling is probably the most common greedy pattern you'll see. Given a set of intervals (meetings, tasks, jobs), select the maximum number of non-overlapping intervals, or find the minimum number of resources to handle all of them.
If you've seen interval questions before you know the answer: sort intervals by end time, then greedily pick the earliest-ending interval that doesn't overlap with your last selection. This works because choosing the interval that finishes earliest leaves the most room for future intervals.
Sort by end time, then walk through: pick A (ends at 3), skip B and C (overlap), skip D (overlaps), pick E (starts at 4, ends at 7), pick F (starts at 7) which yields us three intervals selected, which is the maximum.
Maximum Non-Overlapping Intervals
Python
def max_non_overlapping(intervals):
intervals.sort(key=lambda x: x[1])
selected = []
last_end = float('-inf')
for start, end in intervals:
if start >= last_end:
selected.append((start, end))
last_end = end
return selected
The time complexity is O(n log n) for the sort, then O(n) for the scan. This is one of those patterns where the greedy proof is clean and well-known, so if you or your AI produces this approach, you can be confident it's correct.
A closely related variant asks for the minimum number of rooms (or machines, or servers) to handle all intervals. That's a different problem with a different greedy strategy. You track active intervals and count the maximum overlap at any point.
Minimum Rooms (Meeting Rooms II)
Python
import heapq
def min_rooms(intervals):
if not intervals:
return 0
intervals.sort(key=lambda x: x[0])
heap = []
for start, end in intervals:
if heap and heap[0] <= start:
heapq.heapreplace(heap, end)
else:
heapq.heappush(heap, end)
return len(heap)
The trick here is maintaining a min-heap of end times for currently active intervals. When a new interval starts after the earliest ending one, you reuse that room. Otherwise you need a new room. This is O(n log n) and is a completely different greedy strategy from the max-non-overlapping version above. In spite of being about the same shape, they actually have very different solutions.
Bin packing
Got it so far? Let's ramp up the complexity a bit. Bin packing is where greedy gets really practical. You have items of various sizes and bins of fixed capacity and need to pack all items into as few bins as possible and this could be anything: allocating containers to servers, fitting tasks into time slots, memory management, even distributing load across worker nodes.
The bad news is that optimal bin packing is NP-hard (which makes it a perfect AI coding question!). The good news is that greedy heuristics get surprisingly close to optimal, and in an interview context, that's usually what's being asked for. You'll start with a greedy baseline and then make incremental optimizations as the problem allows.
The main strategies
So what can we do? There's a few main strategies to consider, starting with the most naive:
First-Fit: For each item, scan bins from left to right and place the item in the first bin that has room. Simple, fast, and decent.
Best-Fit: For each item, place it in the bin where it fits most tightly (least remaining space after placement). Slightly better packing, slightly more work to find the right bin.
The problem with both of these is that they often lead to fragmented bins where you fill the bin with small items and then have nowhere to put the big ones. A better solution?
First-Fit Decreasing (FFD): Sort items largest-first, then apply First-Fit.
What we're doing here is trying to greedily place our biggest items first, because we know intuitively that we'll be able to find room for the smaller items. This is probably the strategy you used if you needed to move your belongings between apartments.
FFD has a proven worst-case guarantee: it never uses more than (11/9) * OPT + 6/9 bins, where OPT is the optimal number. In practice, it usually does better than that. No interviewer is going to quiz you on this exact guarantee, but knowing that it exists is a helpful thing to have in your back pocket.
Let's look at some code:
First-Fit Decreasing Bin Packing
Python
def first_fit_decreasing(items, bin_capacity):
items_sorted = sorted(items, reverse=True)
bins = []
for item in items_sorted:
placed = False
for i, current_load in enumerate(bins):
if current_load + item <= bin_capacity:
bins[i] += item
placed = True
break
if not placed:
bins.append(item)
return len(bins), bins
This runs in in the worst case (n items, each scanning all existing bins). You can improve it to O(n log n) with a balanced BST or heap to track bin remaining capacities, but the version is totally fine for an interview unless the problem explicitly requires better.
In an interview, if you're asked a bin packing variant, start by stating the approach clearly: "I'll sort items in decreasing order and use first-fit, which gives a guaranteed approximation ratio." This shows you understand it's a heuristic and aren't claiming it's optimal. Interviewers appreciate that nuance. Follow this up with a simple benchmark (AI is really good at hammering these out!) and then you can optimize it further where needed.
Real-world framing
Interview problems rarely say "solve bin packing." Instead they're dressed up as practical scenarios:
- Server allocation: You have N tasks with memory requirements and servers with fixed RAM. Minimize the number of servers.
- Container packing: Ship items in boxes of fixed volume. Minimize boxes used.
- Job scheduling with deadlines: Assign jobs to machines where each machine has a capacity per time window.
- Disk partition management: Files of various sizes need to go onto fixed-size partitions.
The translation step is part of what's being tested. Recognizing that "minimize the number of servers needed" is just bin packing in disguise is valuable, and it's something the AI might not explicitly tell you. Even being able to use the language "hey this looks like a bin packing problem" is a strong signal, so long as you're right.
Multi-dimensional bin packing
Things get trickier when items have multiple dimensions. A server might have both CPU and memory limits. A shipping box has length, width, and height. In these cases, simple one-dimensional heuristics don't directly apply, and the problem becomes significantly harder.
The good approach for interviews is to reduce multi-dimensional packing to a series of one-dimensional decisions where possible. For instance, if servers have both CPU and memory, you could pack by the "tighter" or more constrained resource first (the one that will run out sooner) and check the other constraint as a feasibility filter. This isn't optimal, but it's practical, and stating the tradeoff explicitly shows maturity.
2D First-Fit Decreasing (CPU + Memory)
Python
def first_fit_decreasing_2d(items, cpu_cap, mem_cap):
items_sorted = sorted(items, key=lambda x: max(x[0]/cpu_cap, x[1]/mem_cap), reverse=True)
bins_cpu = []
bins_mem = []
for cpu, mem in items_sorted:
placed = False
for i in range(len(bins_cpu)):
if bins_cpu[i] + cpu <= cpu_cap and bins_mem[i] + mem <= mem_cap:
bins_cpu[i] += cpu
bins_mem[i] += mem
placed = True
break
if not placed:
bins_cpu.append(cpu)
bins_mem.append(mem)
return len(bins_cpu)
The sort key here uses the maximum normalized resource demand, essentially asking "which dimension of this item is proportionally largest relative to capacity?" That's a reasonable heuristic, though there are others. Remember, the point isn't to memorize this.
Interviewers don't expect you to have multi-dimensional bin packing algorithms memorized. What they want to see is that you can take a known technique, adapt it to new constraints, and clearly communicate what guarantees you're giving up. Saying "this is a heuristic and I'm not certain it's optimal" is exactly right.
When greedy is wrong (not just approximate)
By now you've seen greedy "fail" in two different senses, and conflating them is what trips people up.
For bin packing, greedy heuristics often can't hit the true optimum — but FFD gets close, has a known approximation bound, and that's usually what the interviewer wants. You state the tradeoff and move on.
The cases below are different. Greedy doesn't just miss optimality by a little. It returns an answer that's incorrect, and no amount of "better heuristic" fixes it. These are the problems where you need DP, backtracking, or something else entirely and where an AI-generated greedy solution will look plausible until a hidden test case breaks it.
The mechanism is the same as the coin-change counterexample: a locally optimal choice at one step constrains later steps so badly that the overall result is wrong. Here are the shapes you'll see most often:
The 0/1 knapsack problem. This is the cousin of bin packing. It has the same shape (items with sizes, capacity-limited containers, NP-hard), but it's a different question. Bin packing: pack everything, minimize bins. Knapsack: pick a subset, maximize value in one bag. Subtle, but important!
FFD on bin packing always returns a valid packing; it might use more bins than optimal, but nothing is left behind and nothing overflows. Greedy-by-ratio on 0/1 knapsack also returns a valid subset that fits, but the value can be far below the true maximum. In interviews, bin packing often accepts "good enough" (state the approximation) whereas knapsack usually means "find the exact max" which makes it a DP problem.
Shortest path with negative edges. In the graph search & pathfinding pattern, Dijkstra's is the greedy go-to — always expand the nearest unvisited node. It works when edge weights are non-negative. Throw in a negative edge and it falls apart. You need Bellman-Ford instead.
Non-standard coin denominations. This has the same coin-change trap from earlier. US coins happen to work with greedy, arbitrary sets don't.
Task scheduling with dependencies. If tasks depend on each other, greedily picking the shortest task next can violate dependency constraints and produce an invalid schedule. You need topological sorting or DP.
If you're worried about this, adding test cases where the greedy approach might fail is a great way to make sure it's not a disaster. The AI is often really good at creating these.
The general rule of thumb: if the problem forces you to reason about combinations of choices (think: exponential) and not just "pick the best next item" then greedy probably isn't exact. Either reach for DP/backtracking, or (for NP-hard packing-style problems) reach for a greedy heuristic and say so out loud. Don't treat those as the same thing.
Quick diagnostic
When you see a new problem, ask yourself these questions before going greedy:
- Can I make a choice and never need to undo it? If not, greedy won't work.
- After making one choice, does the remaining problem look like a smaller version of the same thing? If not, optimal substructure doesn't hold.
- Can I construct a small counterexample where greedy gives the wrong answer? If yes, you've just proved greedy is wrong. If you can't find one after a couple of minutes, greedy is probably fine, but that's not a proof.
What interviewers expect
Interviewers asking greedy problems in AI coding interviews are testing a few specific things, and none of them are "can you recite the proof that activity selection is optimal."
Recognizing the pattern. Can you look at a problem and identify that it has greedy structure? This means noticing things like: the problem asks for a maximum or minimum, there's a natural ordering (by end time, by size, by ratio), and making a locally optimal choice doesn't seem to constrain future choices.
Reasoning about correctness. This is the big one. Can you articulate why greedy works for this specific problem, or identify when it doesn't? The gold standard is constructing a quick exchange argument: "If we had a non-greedy optimal solution, we could swap in the greedy choice without making it worse." You don't need to write a formal proof, but you should be able to sketch the reasoning.
Verifying AI output. When your AI generates a greedy solution, what do you do? Blindly accept it? That's a red flag. The interviewer wants to see you:
- State what the greedy strategy is (e.g., "this sorts by end time and picks non-overlapping intervals")
- Consider whether the greedy choice property holds
- Test it against an edge case or two, especially adversarial ones
- Flag if you think greedy might be wrong and suggest an alternative
Knowing the limits. If the problem requires an exact optimal solution and you can't prove greedy works, say so. "I think this needs DP because the greedy choice at step k affects what's available at step k+2" is a great answer. It shows you understand the algorithm design landscape well enough to pick the right tool.
In an interview saying something like: "The AI suggested a greedy approach here. Let me verify that works by thinking about whether we can always commit to the locally optimal choice." then walking through a small example is excellent. Even if the greedy approach turns out to be correct, the fact that you questioned it and verified it tells the interviewer you think critically about generated code.
Putting it together
Greedy problems in AI coding interviews aren't about raw algorithmic knowledge. They're about judgment. The AI can write the code. It can sort intervals by end time and iterate through them faster than you can type the function signature. What it can't do reliably is decide whether greedy is the right approach in the first place.
That decision, greedy vs. DP vs. something else entirely, is yours to make. And how you make it, how you reason about it out loud, how you verify the AI's output against edge cases, etc. is what the interview is really measuring.
The strongest candidates treat greedy as a tool they reach for deliberately, not a default they fall back on because it's simpler. They can articulate why it works, catch when it doesn't, and pivot to the right alternative without losing momentum. That's the skill worth practicing.
Purchase Premium to Keep Reading
Unlock this article and so much more with Hello Interview Premium
Reading Progress
On This Page