Greedy algorithm interview questions with worked solutions
Last updated 2026-11-19
A greedy algorithm makes the locally best choice at each step and never reconsiders it. It is fast and short when it works, and wrong when it does not, so the interview skill is not writing the loop but justifying the choice: why does picking this option now never hurt the final answer?
The ten problems below come with the argument that makes each greedy step safe, ordered from direct to subtle. For selection problems on ranges, see interval questions; when a greedy choice fails because of weights or overlapping sub-problems, move to dynamic programming. Pair this page with the DSA coding round guide.
| Problems | 10, easy to hard |
|---|---|
| Languages | Python and Java |
| Proof tools | Exchange argument, stays ahead |
How to justify a greedy choice
The standard argument is an exchange argument: take any optimal solution that does not use your greedy choice, and show you can swap in the greedy choice without making it worse. The second is a stays-ahead argument: show that after each step the greedy solution is at least as good as any other on the quantity you care about.
In an interview, test your idea on a small counterexample before coding. Coin change with coins 1, 3, 4 and amount 6 is the classic case where greedy picks 4 + 1 + 1 but 3 + 3 is better.
- Sort first: many greedy problems are "sort, then scan".
- Track the farthest or best reachable value as you scan.
- Use a heap when the best choice changes as you go.
- If weights or dependencies make local choices unsafe, use DP.
Typical signals
Words such as "minimum number of", "maximum number of", "earliest", "fewest" with a simple local rule are common. A greedy solution usually has an O(n log n) sort or an O(n) scan. If you cannot explain why the rule is safe, that is a reason to suspect it.
Greedy algorithm interview questions with worked solutions: questions with worked answers
1 Assign cookies: maximise the number of children who receive a cookie at least as large as their greed.
easySort both lists. Walk through the cookies from smallest to largest and give each cookie to the least greedy unsatisfied child if it is big enough. Using the smallest sufficient cookie for the least demanding child wastes nothing. The count of satisfied children is the answer. Time O(n log n + m log m), space O(1).. Edge cases: no cookies or no children (0), every cookie too small, more cookies than children.
pythondef find_content_children(g, s): g.sort() s.sort() i = 0 for cookie in s: if i < len(g) and g[i] <= cookie: i += 1 return ijavaimport java.util.*; class Solution { static int findContentChildren(int[] g, int[] s) { Arrays.sort(g); Arrays.sort(s); int i = 0; for (int cookie : s) if (i < g.length && g[i] <= cookie) i++; return i; } }2 Lemonade change: each customer pays 5, 10 or 20 for a 5-dollar drink; can you always give change?
easyTrack the count of 5 and 10 notes. A 10 needs one 5. A 20 needs 15 in change: prefer one 10 and one 5, because 5s are more flexible and can substitute for a 10 later, otherwise use three 5s. Preferring the 10 is the greedy step. Time O(n), space O(1).. Edge cases: first customer pays 10 or 20 (false), a 20 when only 5s remain, long runs of 5s.
pythondef lemonade_change(bills): five = ten = 0 for b in bills: if b == 5: five += 1 elif b == 10: if not five: return False five -= 1 ten += 1 else: if ten and five: ten -= 1 five -= 1 elif five >= 3: five -= 3 else: return False return Truejavaimport java.util.*; class Solution { static boolean lemonadeChange(int[] bills) { int five = 0, ten = 0; for (int b : bills) { if (b == 5) five++; else if (b == 10) { if (five == 0) return false; five--; ten++; } else { if (ten > 0 && five > 0) { ten--; five--; } else if (five >= 3) five -= 3; else return false; } } return true; } }3 Best time to buy and sell stock with unlimited transactions.
easyAny rise between consecutive days can be captured by buying the day before and selling the day after, and the sum of all rises equals the best total. So add every positive day-to-day difference. No need to find the actual buy and sell days. Time O(n), space O(1).. Edge cases: prices only falling (0), one day, flat prices.
pythondef max_profit(prices): return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, len(prices)))javaimport java.util.*; class Solution { static int maxProfit(int[] p) { int profit = 0; for (int i = 1; i < p.length; i++) if (p[i] > p[i - 1]) profit += p[i] - p[i - 1]; return profit; } }4 Jump game: can you reach the last index if each element is the maximum jump length from that position?
mediumScan once, tracking the farthest index reachable so far. If the current index is beyond that, you are stuck and the answer is false. Otherwise update farthest with i + a[i]. You do not need to choose a specific jump, only to know the reachable frontier. Time O(n), space O(1).. Edge cases: a zero in the middle that can be jumped over versus one that cannot, single element (true), all zeroes except the first.
pythondef can_jump(a): far = 0 for i, x in enumerate(a): if i > far: return False far = max(far, i + x) return Truejavaimport java.util.*; class Solution { static boolean canJump(int[] a) { int far = 0; for (int i = 0; i < a.length; i++) { if (i > far) return false; far = Math.max(far, i + a[i]); } return true; } }5 Jump game II: the minimum number of jumps to reach the last index (reachable guaranteed).
mediumThink in layers like BFS. Track the end of the current jump range and the farthest reachable index. When you reach the end of the current range, you must jump again: increment the counter and extend the range to the farthest point. Stop before the last index. Time O(n), space O(1).. Edge cases: single element (0 jumps), every jump of length one, a big first jump.
pythondef jump(a): jumps = cur_end = far = 0 for i in range(len(a) - 1): far = max(far, i + a[i]) if i == cur_end: jumps += 1 cur_end = far return jumpsjavaimport java.util.*; class Solution { static int jump(int[] a) { int jumps = 0, curEnd = 0, far = 0; for (int i = 0; i < a.length - 1; i++) { far = Math.max(far, i + a[i]); if (i == curEnd) { jumps++; curEnd = far; } } return jumps; } }6 Gas station: find the starting station to complete a circular route, or -1.
mediumIf total gas is less than total cost, no start works. Otherwise a solution exists and is unique. Scan with a running tank; whenever it goes negative, none of the stations from the previous start up to here can be the start (each would have reached this point with at least as little fuel), so reset the start to the next station. Time O(n), space O(1).. Edge cases: total gas below total cost (-1), a single station, a start at the last index.
pythondef can_complete_circuit(gas, cost): total = tank = start = 0 for i in range(len(gas)): d = gas[i] - cost[i] total += d tank += d if tank < 0: start = i + 1 tank = 0 return start if total >= 0 else -1javaimport java.util.*; class Solution { static int canCompleteCircuit(int[] gas, int[] cost) { int total = 0, tank = 0, start = 0; for (int i = 0; i < gas.length; i++) { int d = gas[i] - cost[i]; total += d; tank += d; if (tank < 0) { start = i + 1; tank = 0; } } return total >= 0 ? start : -1; } }7 Task scheduler: the least time to run tasks when identical tasks need n idle slots between them.
mediumThe most frequent task decides the frame. If it appears maxf times and k tasks tie for that frequency, the minimum length is (maxf - 1) * (n + 1) + k: maxf - 1 full blocks of n + 1 slots, plus a final row of the k tied tasks. Other tasks fill the gaps. If there are more tasks than that, no idling is needed and the answer is the task count. Time O(n) to count, space O(26).. Edge cases: n = 0 (answer is the task count), a single task type, many types with few repeats.
pythonfrom collections import Counter def least_interval(tasks, n): cnt = Counter(tasks) maxf = max(cnt.values()) k = sum(1 for v in cnt.values() if v == maxf) return max(len(tasks), (maxf - 1) * (n + 1) + k)javaimport java.util.*; class Solution { static int leastInterval(char[] tasks, int n) { int[] cnt = new int[26]; for (char t : tasks) cnt[t - 'A']++; int maxf = 0; for (int c : cnt) maxf = Math.max(maxf, c); int k = 0; for (int c : cnt) if (c == maxf) k++; return Math.max(tasks.length, (maxf - 1) * (n + 1) + k); } }8 Queue reconstruction by height: rebuild a queue from people given as [height, number of taller-or-equal people in front].
mediumSort by height descending, and for equal heights by the front-count ascending. Then insert each person at index equal to their count. Taller people are placed first, so inserting a shorter person later never changes the count of taller people in front of anyone already placed. Time O(n^2) because of list insertions, space O(n).. Edge cases: equal heights (tie-break matters), count 0 for everyone, a single person.
pythondef reconstruct_queue(people): people.sort(key=lambda p: (-p[0], p[1])) res = [] for p in people: res.insert(p[1], p) return resjavaimport java.util.*; class Solution { static int[][] reconstructQueue(int[][] people) { Arrays.sort(people, (a, b) -> a[0] != b[0] ? Integer.compare(b[0], a[0]) : Integer.compare(a[1], b[1])); List<int[]> res = new ArrayList<>(); for (int[] p : people) res.add(p[1], p); return res.toArray(new int[0][]); } }9 Candy: distribute the fewest candies so each child gets at least one and a higher-rated child gets more than a neighbour.
hardDo two passes. Left to right, give a child one more than the left neighbour if their rating is higher. Right to left, do the same against the right neighbour, keeping the maximum of the two requirements. Each pass enforces one side of the rule without breaking the other. Time O(n), space O(n).. Edge cases: equal ratings (no extra candy needed), strictly increasing or decreasing ratings, a single child.
pythondef candy(r): n = len(r) c = [1] * n for i in range(1, n): if r[i] > r[i - 1]: c[i] = c[i - 1] + 1 for i in range(n - 2, -1, -1): if r[i] > r[i + 1]: c[i] = max(c[i], c[i + 1] + 1) return sum(c)javaimport java.util.*; class Solution { static int candy(int[] r) { int n = r.length; int[] c = new int[n]; Arrays.fill(c, 1); for (int i = 1; i < n; i++) if (r[i] > r[i - 1]) c[i] = c[i - 1] + 1; for (int i = n - 2; i >= 0; i--) if (r[i] > r[i + 1]) c[i] = Math.max(c[i], c[i + 1] + 1); int sum = 0; for (int x : c) sum += x; return sum; } }10 Minimum number of refuelling stops to reach a target, given stations with positions and fuel.
hardDrive as far as possible without stopping, remembering the fuel amount of every station you pass in a max-heap. When you run out before the next point, retroactively refuel at the passed station with the most fuel and count a stop. If the heap is empty while fuel is negative, the target is unreachable. A final virtual station at the target flushes the last leg. Time O(n log n), space O(n).. Edge cases: target reachable with the starting fuel (0 stops), unreachable (-1), a station exactly at the point fuel runs out.
pythonimport heapq def min_refuel_stops(target, fuel, stations): heap, stops, prev = [], 0, 0 for pos, f in stations + [[target, 0]]: fuel -= pos - prev while heap and fuel < 0: fuel += -heapq.heappop(heap) stops += 1 if fuel < 0: return -1 heapq.heappush(heap, -f) prev = pos return stopsjavaimport java.util.*; class Solution { static int minRefuelStops(int target, int fuel, int[][] stations) { PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder()); int stops = 0, prev = 0; for (int i = 0; i <= stations.length; i++) { int pos = i < stations.length ? stations[i][0] : target; int f = i < stations.length ? stations[i][1] : 0; fuel -= pos - prev; while (!heap.isEmpty() && fuel < 0) { fuel += heap.poll(); stops++; } if (fuel < 0) return -1; heap.add(f); prev = pos; } return stops; } }
Frequently asked questions
How do I know a greedy solution is correct?
Prove it with an exchange argument (swap the greedy choice into any optimal solution without loss) or a stays-ahead argument. Also test it on small cases against brute force.
What is a classic case where greedy fails?
Coin change with coins 1, 3, 4: for 6, greedy picks 4, 1, 1 (three coins) but 3 + 3 uses two. Such cases need dynamic programming.
Is sorting always part of a greedy solution?
Often, because sorting exposes the order in which local choices are safe. But scans such as jump game and gas station are greedy without sorting.
How is greedy different from dynamic programming?
Greedy commits to one choice per step and never revisits it. DP tries all choices and combines sub-results. Greedy is faster but applies to fewer problems.
Which interval problems are greedy?
Non-overlapping intervals and balloon arrows are classic sort-by-end greedy problems. See interval questions.
Related guides
- Interval interview questions with worked solutions
- Dynamic Programming Interview Questions
- Sorting algorithm interview questions with worked solutions
- Top K elements interview questions with worked solutions
- Merge intervals pattern questions with worked solutions
- Kadane algorithm interview questions with worked solutions
More in DSA Interview Questions
- Grid and Matrix DP Interview Questions
- Hashing interview questions with worked solutions
- Heap and Priority Queue Interview Questions
- Interval DP Interview Questions
- Interval interview questions with worked solutions
- Kadane algorithm interview questions with worked solutions
- KMP and string matching interview questions with solutions
- Knapsack DP Interview Questions
- Linked list interview questions with worked solutions
- Longest Common Subsequence (LCS) Interview Questions
- Longest Increasing Subsequence (LIS) Interview Questions
- LRU Cache and Design Data Structure Interview Questions