| Activity Selection / Interval Scheduling | Sort by finish time; always take the earliest-finishing compatible interval |
| Minimum Spanning Tree (Kruskal) | Sort edges by weight; add an edge if its endpoints are in different components (cut property) |
| Minimum Spanning Tree (Prim) | Always extend the growing tree with the cheapest edge crossing the current frontier |
| Dijkstra's Shortest Path | Always finalize the closest unvisited vertex; requires non-negative edge weights |
| Huffman Coding | Repeatedly merge the two lowest-frequency nodes into a new parent node |
| Job Sequencing with Deadlines | Sort by profit descending; slot each job into the latest still-free day ≤ its deadline |
| Coin Change (Greedy) | Optimal only for canonical denomination systems; fails otherwise and needs DP |
| Gas Station / Jump Game | Track feasibility in one linear pass; reset the candidate start greedily on failure |
Greedy Algorithms Coding Interview Questions & Answers
Q1. What is a greedy algorithm and how does it approach optimization problems?
A: A greedy algorithm builds a solution incrementally, at each step making the choice that looks best right now according to some local criterion, and never revisiting that choice later. It never backtracks or re-evaluates earlier decisions in light of new information. Greedy algorithms are attractive because they are typically simple to implement and run in O(n log n) or better, but they are only correct on problems whose structure guarantees that local optimality composes into global optimality.
Q2. What is the "greedy choice property" and why must a problem exhibit it for greedy to work?
A: The greedy choice property says that a globally optimal solution can always be reached by making a locally optimal (greedy) choice first, then solving the remaining subproblem optimally — without ever needing to reconsider that first choice. If a problem lacks this property, some greedy-looking first move can permanently lock you out of the true optimum, and no amount of clever subproblem-solving afterward can recover it. Proving this property (usually via an exchange argument) is the mandatory first step before trusting any greedy algorithm.
Q3. What is "optimal substructure" and how does greedy's use of it differ from dynamic programming's?
A: Optimal substructure means an optimal solution to a problem contains optimal solutions to its subproblems. Both greedy and DP rely on it, but DP explores many subproblems (often overlapping ones) and combines their optimal answers via a recurrence, whereas greedy commits to exactly one subproblem — the one left over after the greedy choice — and never looks at the alternatives. That single-subproblem commitment is what makes greedy fast, and also what makes it fragile: it only works when the greedy choice property additionally holds.
Q4. What is the exchange argument and how is it used to prove a greedy algorithm correct?
A: An exchange argument assumes there exists some optimal solution that disagrees with the greedy choice, then shows you can "exchange" a piece of that optimal solution for the greedy choice without making the solution any worse. Repeating this exchange transforms any optimal solution into one that agrees with greedy at every step, without decreasing its value. Since the transformed solution is still optimal and now matches greedy exactly, greedy itself must also be optimal — this is the standard template used to prove correctness for activity selection, Kruskal's algorithm, and Huffman coding.
Q5. What is the "greedy stays ahead" proof technique?
A: "Greedy stays ahead" proves correctness by showing, via induction, that after each step the greedy algorithm's partial solution is at least as good as any other valid partial solution's corresponding measure at that same step. Because greedy never falls behind at any prefix of the process, it cannot be beaten at the final step either. This technique is often easier to apply than a full exchange argument for problems with a natural step-by-step progress metric, such as interval scheduling (greedy's chosen finish time is always ≤ any other valid strategy's finish time at the same step count).
Q6. What is a matroid, informally, and why do many greedy-solvable problems have matroid structure?
A: A matroid is a pair (a ground set of elements, a family of "independent" subsets) satisfying two axioms: any subset of an independent set is independent (hereditary property), and if independent set A is smaller than independent set B, some element of B can be added to A while keeping it independent (exchange property). The matroid greedy theorem guarantees that picking elements greedily by weight, skipping any that would violate independence, always yields a maximum-weight independent set. Spanning forests in a graph (for MST), and "can I still meet all deadlines" constraints (for job sequencing), both satisfy these axioms — which is exactly why greedy works cleanly for both.
Q7. What are the telltale signs that a problem will NOT yield to a greedy algorithm?
A: Warning signs include: the "obvious" local choice can be undone or regretted only by looking arbitrarily far ahead; a small counterexample with 3-4 elements breaks your proposed rule; the problem has an explicit capacity/budget constraint that couples otherwise-independent choices (like 0/1 knapsack); or multiple plausible greedy criteria exist and none dominates the others in all cases. When any of these appear, reach for dynamic programming (if choices are independent-ish with reusable subproblems) or backtracking/search (if the space must be explored exhaustively).
Q8. Why does a greedy approach fail for the 0/1 knapsack problem?
A: A natural greedy rule — sort by value-to-weight ratio and take the best-ratio items until the capacity is full — fails because items cannot be split; taking a slightly-lower-ratio item might free up exactly the right amount of remaining capacity to fit a very valuable combination later, while the greedy pick leaves capacity stranded. Concretely, with capacity 10 and items (weight 6, value 10) and (weight 5, value 6) twice, greedy picks the single ratio-best item worth 10, but two of the weight-5 items together are worth 12 and still fit. Because the decision to include an item is all-or-nothing and interacts with the shared capacity constraint, 0/1 knapsack needs DP, not greedy (fractional knapsack, where items can be split, is greedy-solvable).
Q9. Why does naive greedy coin selection fail for arbitrary coin denominations?
A: Repeatedly taking the largest denomination ≤ the remaining amount assumes large coins are always "safe" to use in full, but for non-canonical denomination sets that assumption can strand you with a suboptimal remainder. For example, with coins {1, 3, 4} and target 6, greedy takes 4 then two 1s (3 coins), while 3+3 uses only 2 coins. The greedy choice property simply does not hold for general coin systems, so correctness must be re-derived (or abandoned in favor of DP) for every new denomination set.
Q10. What is the fundamental difference between greedy algorithms and dynamic programming?
A: Greedy makes one irrevocable choice per step and solves exactly one resulting subproblem, achieving speed but requiring a correctness proof up front. DP considers all relevant choices at each step, computes optimal answers to every distinct subproblem (memoized or tabulated), and combines them via a recurrence, guaranteeing correctness whenever optimal substructure holds but paying for it with extra time and space to explore the overlapping subproblems. A useful mental model: DP is "try everything, remember the best"; greedy is "commit early, never look back."
Q11. What is the fundamental difference between greedy algorithms and backtracking?
A: Greedy commits to a single choice at each step and never undoes it, producing one candidate solution in typically linear or near-linear time. Backtracking explores the space of choices via recursion, trying an option, recursing, and undoing ("backtracking") that option to try alternatives when a path fails or is exhausted, effectively performing a pruned exhaustive search. Backtracking is used precisely when no greedy rule can be proven correct and the problem size is small enough that exponential exploration (with pruning) is tractable.
Q12. Why are greedy algorithms generally more time-efficient than DP or backtracking when they apply?
A: Greedy algorithms typically make one pass (or one pass after a single sort), doing O(1) or O(log n) work per element, for total complexity like O(n log n). DP must fill in a table of subproblems, often O(n) or O(n²) states each taking O(1) to O(n) time to compute, and backtracking can be exponential in the worst case since it explores a branching search tree. When a valid greedy rule exists, it exploits problem structure to avoid ever revisiting a decision, which is strictly cheaper than DP's "compute every relevant subproblem" or backtracking's "explore every relevant branch."
Q13. What is the difference between a locally optimal choice and a globally optimal solution?
A: A locally optimal choice is the best option available given only the information visible at the current step (e.g., "pick the interval that finishes soonest right now"). A globally optimal solution is the best possible outcome across the entire problem instance. Greedy algorithms are a bet that a sequence of locally optimal choices composes into a globally optimal solution; this bet pays off only for problems with the greedy choice property and optimal substructure, and fails (sometimes badly) otherwise, which is why every greedy claim needs a proof, not just intuition.
Q14. Can greedy and dynamic programming be combined in a single algorithm? Give an example.
A: Yes — many practical algorithms use a greedy pass to reduce the problem size or handle an easy sub-case, then fall back to DP for the part that truly requires exploring alternatives. Huffman coding is a pure greedy example, but weighted interval scheduling is a hybrid in spirit: you greedily sort by finish time to define a useful subproblem ordering, then apply DP (with binary search for the "last compatible interval") to actually choose which intervals to include, because profit weights break the pure greedy choice property. Recognizing when a greedy preprocessing step (like sorting) can simplify a DP's state space is a valuable interview skill.
Q15. How do you formally state the "matroid greedy theorem"?
A: Given a matroid (ground set E, independent sets I) and a non-negative weight on each element, the greedy algorithm that processes elements in decreasing order of weight, adding each element to the growing independent set whenever doing so keeps it independent, always produces a maximum-weight independent set (a "base" if you keep going until no more elements can be added). This theorem is the unifying reason Kruskal's algorithm, matroid intersection problems, and certain scheduling problems are all greedy-solvable — they are all instances of weighted matroid optimization.
Q16. What is the activity selection problem?
A: Given a set of activities, each with a start and finish time, the activity selection problem asks for the maximum-size subset of mutually non-overlapping activities that can all be scheduled on a single resource (one room, one machine). Two activities are compatible if one finishes at or before the other starts. It is the canonical introductory example for proving greedy correctness via an exchange argument.
Q17. What is the greedy strategy for activity selection, and why is sorting by finish time optimal?
A: Sort all activities by finish time ascending, then scan left to right, greedily selecting any activity whose start time is ≥ the finish time of the last selected activity. This is optimal because the activity finishing earliest always leaves the most remaining time for everything else — an exchange argument shows that swapping any optimal solution's first pick for the earliest-finishing activity can never make that solution worse. The strategy runs in O(n log n) dominated by the sort.
class Activity {
int start, finish;
Activity(int s, int f) { start = s; finish = f; }
}
int selectActivities(Activity[] activities) {
Arrays.sort(activities, (a, b) -> a.finish - b.finish);
int count = 1;
int lastFinish = activities[0].finish;
for (int i = 1; i < activities.length; i++) {
if (activities[i].start >= lastFinish) {
count++;
lastFinish = activities[i].finish;
}
}
return count;
}Q18. What is the time complexity of the activity selection greedy algorithm?
A: Sorting the activities by finish time costs O(n log n), and the subsequent single linear scan that greedily selects compatible activities costs O(n). The overall complexity is therefore O(n log n), dominated entirely by the sort; the selection pass itself is O(1) extra space beyond the input array.
Q19. Why does sorting activities by start time fail to produce an optimal activity selection?
A: An activity that starts earliest may finish very late, blocking many shorter activities that could have been scheduled instead. For example, an activity [0, 10] sorted first by start time would be greedily selected and then exclude many activities like [1,2], [3,4], [5,6] that together would have given a larger count. Start time carries no information about how much room is left for future activities, which is exactly what finish time captures.
Q20. Why does sorting activities by shortest duration fail to produce an optimal activity selection?
A: A short-duration activity can still be badly positioned — for instance, sitting right in the middle of two other activities it would block, when a different ordering would leave both of those free. Duration alone ignores absolute position on the timeline, so a short activity from time 5 to 6 can still conflict with more total activities than a well-placed longer one. Only finish time reliably tells you which activity leaves the most remaining schedule open for everything else.
Q21. What is the difference between interval scheduling maximization and interval partitioning?
A: Interval scheduling maximization (activity selection) asks for the largest subset of non-overlapping intervals achievable using a single resource, discarding the rest. Interval partitioning (the meeting rooms problem) instead asks for the minimum number of resources (rooms, machines) needed to schedule every interval with no overlaps on any single resource. The first is solved by sorting on finish time and greedily keeping compatible intervals; the second is solved by sorting on start time and tracking concurrently active intervals with a min-heap of end times.
Q22. How do you find the minimum number of meeting rooms required for a set of intervals?
A: Sort meetings by start time, then use a min-heap keyed by end time to represent currently occupied rooms. For each meeting, if the room with the earliest end time frees up before (or exactly when) the new meeting starts, reuse that room by popping it from the heap; either way, push the new meeting's end time. The heap's maximum size reached during the scan is the minimum number of rooms needed, in O(n log n) time.
int minMeetingRooms(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
PriorityQueue<Integer> endTimes = new PriorityQueue<>();
for (int[] iv : intervals) {
if (!endTimes.isEmpty() && endTimes.peek() <= iv[0]) {
endTimes.poll();
}
endTimes.offer(iv[1]);
}
return endTimes.size();
}Q23. How do you find the minimum number of intervals to remove to make the rest non-overlapping?
A: This is the complement of activity selection: sort by finish time, greedily keep an interval whenever its start is ≥ the last kept interval's finish, and count every interval you must skip because it overlaps. The count of skipped intervals is the minimum number of removals. This runs in O(n log n) and is a direct application of the same exchange argument that proves activity selection optimal.
int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
int count = 0;
int lastEnd = Integer.MIN_VALUE;
for (int[] iv : intervals) {
if (iv[0] >= lastEnd) {
lastEnd = iv[1];
} else {
count++;
}
}
return count;
}Q24. How do you find the minimum number of arrows to burst all balloons (overlapping interval variant)?
A: Sort balloons by their end coordinate. Fire an arrow at the end coordinate of the first unburst balloon; that single arrow shot bursts every subsequent balloon whose start coordinate is ≤ that shot position (since their ranges overlap). Move to the next balloon whose start is beyond the current shot, increment the arrow count, and repeat — O(n log n) total, structurally identical to activity selection with the "shot position" playing the role of the last finish time.
int findMinArrowShots(int[][] points) {
Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
int arrows = 0;
int lastArrowPos = Integer.MIN_VALUE;
for (int[] p : points) {
if (p[0] > lastArrowPos) {
arrows++;
lastArrowPos = p[1];
}
}
return arrows;
}Q25. How do you find the minimum number of intervals needed to cover a target range (video stitching)?
A: This is a jump-game-flavored greedy: for every starting point within the target range, precompute the farthest reach achievable by any clip beginning there. Scan left to right maintaining the current covered boundary and the farthest reachable boundary seen so far; whenever you reach the current boundary, you are forced to "use" a clip, so increment the count and extend the boundary to the farthest reach recorded — if it cannot advance, the range is uncoverable. This runs in O(n + target) time.
int videoStitching(int[][] clips, int target) {
int[] maxReach = new int[target];
for (int[] c : clips) {
if (c[0] < target) {
maxReach[c[0]] = Math.max(maxReach[c[0]], c[1]);
}
}
int clipsUsed = 0, currentEnd = 0, nextEnd = 0;
for (int i = 0; i < target; i++) {
nextEnd = Math.max(nextEnd, maxReach[i]);
if (i == currentEnd) {
if (nextEnd <= i) return -1;
clipsUsed++;
currentEnd = nextEnd;
}
}
return clipsUsed;
}Q26. Why does the weighted interval scheduling problem require dynamic programming instead of greedy?
A: Once each interval carries an arbitrary weight (profit) instead of counting equally, "finishes soonest" is no longer necessarily the best choice — a later-finishing but far more valuable interval might be worth excluding several small ones for. The greedy choice property breaks because a locally attractive pick (by any single criterion) can block a much higher-value combination elsewhere. The standard solution sorts by finish time (a useful ordering, not a greedy rule) and applies DP: for each interval, the best profit is either skipping it or taking it plus the best profit achievable among intervals compatible with it, found via binary search.
Q27. How do you compute an employee's free time given everyone's busy intervals?
A: Merge all employees' busy intervals into one combined list, sort by start time, and greedily merge overlapping or touching intervals just like the classic merge-intervals routine. The gaps between consecutive merged intervals are exactly the periods when nobody is busy — the employee's common free time. This is O(n log n) for the sort plus O(n) for the merge-and-gap-extraction pass.
Q28. How do you find the minimum number of platforms needed at a railway station given train arrival/departure times?
A: Sort arrival times and departure times independently into two arrays, then use a two-pointer sweep: advance through arrivals and departures in time order, incrementing a running "platforms in use" counter on an arrival and decrementing it on a departure, tracking the maximum value reached. This greedy sweep-line technique runs in O(n log n) and is equivalent in spirit to the meeting-rooms min-heap approach but avoids the heap entirely since only the running count matters, not which specific interval ends first.
int minPlatforms(int[] arrivals, int[] departures) {
Arrays.sort(arrivals);
Arrays.sort(departures);
int platforms = 0, maxPlatforms = 0;
int i = 0, j = 0;
while (i < arrivals.length && j < departures.length) {
if (arrivals[i] <= departures[j]) {
platforms++;
maxPlatforms = Math.max(maxPlatforms, platforms);
i++;
} else {
platforms--;
j++;
}
}
return maxPlatforms;
}Q29. How does the greedy strategy work for the "task scheduler with cooldown" problem?
A: Count each task type's frequency; the most frequent task determines the minimum schedule length, because it needs (maxFreq - 1) full cooldown gaps of size n after each of its occurrences except the last. Greedily fill those gaps with the next most frequent remaining tasks; if there aren't enough distinct other tasks to fill every gap, the leftover slots become forced idle time. The final answer is either the raw task count (if tasks are plentiful enough to fill all gaps) or task count plus leftover idle slots, computed in O(n) after an O(1) 26-bucket frequency count.
int leastInterval(char[] tasks, int n) {
int[] freq = new int[26];
for (char t : tasks) freq[t - 'A']++;
Arrays.sort(freq);
int maxFreq = freq[25];
int idleSlots = (maxFreq - 1) * n;
for (int i = 24; i >= 0 && idleSlots > 0; i--) {
idleSlots -= Math.min(maxFreq - 1, freq[i]);
}
idleSlots = Math.max(0, idleSlots);
return tasks.length + idleSlots;
}Q30. How do you check whether a person can attend all meetings given their intervals?
A: Sort the meetings by start time, then scan consecutively adjacent pairs; if any meeting starts before the previous one ends, there's an unavoidable overlap and the answer is false. This is the simplest special case of interval scheduling — it doesn't even need to select a subset, just detect any conflict — and runs in O(n log n) for the sort plus O(n) for the scan.
boolean canAttendMeetings(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] < intervals[i - 1][1]) return false;
}
return true;
}Q31. What is a minimum spanning tree (MST)?
A: A minimum spanning tree of a connected, weighted, undirected graph is a subset of n-1 edges (for n vertices) that connects all vertices with no cycles, such that the sum of edge weights is minimized among all possible spanning trees. It is a tree because a spanning subgraph with a cycle could always drop the cycle's most expensive edge and remain connected while reducing total weight, so an optimal spanning subgraph is necessarily acyclic.
Q32. What is the "cut property" and why does it justify greedy MST algorithms?
A: The cut property states that for any partition of the graph's vertices into two non-empty groups, the minimum-weight edge crossing that partition (with no ties, or with ties broken consistently) must be part of some MST. This guarantees that whenever a greedy MST algorithm identifies the cheapest edge crossing any cut of the graph — whether it's Kruskal's "cheapest edge not yet forming a cycle" or Prim's "cheapest edge leaving the current tree" — including it can never prevent reaching an optimal MST.
Q33. What is the "cycle property" and how does it complement the cut property?
A: The cycle property states that for any cycle in the graph, the maximum-weight edge on that cycle cannot be part of any MST (as long as it's the unique heaviest edge, or ties are broken consistently), because removing it and keeping the rest still leaves the graph connected with strictly less weight. Where the cut property justifies which edges greedy algorithms should include, the cycle property justifies which edges they can safely exclude — together they fully characterize MST edge membership and underpin both Kruskal's rejection of cycle-forming edges and Prim's implicit avoidance of them.
Q34. How does Kruskal's algorithm build an MST, and how is it implemented?
A: Sort all edges by weight ascending, then process them in order, adding an edge to the MST only if its two endpoints currently belong to different connected components (checked and merged via a Union-Find/Disjoint-Set structure). Skipping an edge whose endpoints are already connected avoids creating a cycle, per the cycle property. The algorithm stops once n-1 edges have been added (or all edges are processed), running in O(E log E) dominated by the sort.
class UnionFind {
int[] parent;
UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
parent[ra] = rb;
return true;
}
}
int kruskalMST(int n, int[][] edges) {
Arrays.sort(edges, (a, b) -> a[2] - b[2]);
UnionFind uf = new UnionFind(n);
int totalWeight = 0, edgesUsed = 0;
for (int[] e : edges) {
if (uf.union(e[0], e[1])) {
totalWeight += e[2];
edgesUsed++;
if (edgesUsed == n - 1) break;
}
}
return totalWeight;
}Q35. Why does Kruskal's algorithm need a Union-Find (Disjoint Set) structure, and what is its complexity?
A: Kruskal must repeatedly answer "are these two vertices already connected?" and "merge these two components" as it processes edges, and doing this with a naive graph traversal would cost O(V) per check, making the whole algorithm too slow. A Union-Find structure with path compression and union by rank/size answers both operations in amortized O(α(n)) time (essentially O(1) in practice, where α is the extremely slow-growing inverse Ackermann function), making Kruskal's total complexity O(E log E) for the sort plus O(E × α(n)) for the union-find operations — dominated by the sort.
Q36. How does Prim's algorithm build an MST, and how is it implemented?
A: Start from an arbitrary vertex and grow a single tree by repeatedly adding the cheapest edge that connects a vertex already in the tree to a vertex not yet in the tree, using a min-heap keyed by edge weight to always find that cheapest crossing edge efficiently. Each time a vertex is added, push all of its edges to not-yet-included neighbors onto the heap. With a binary heap this runs in O(E log V); with an adjacency matrix and no heap, a simpler O(V²) version suits dense graphs.
int primMST(int n, List<int[]>[] adj) {
boolean[] inMST = new boolean[n];
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
pq.offer(new int[]{0, 0}); // {vertex, weight}
int totalWeight = 0;
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int u = cur[0], w = cur[1];
if (inMST[u]) continue;
inMST[u] = true;
totalWeight += w;
for (int[] edge : adj[u]) {
int v = edge[0], weight = edge[1];
if (!inMST[v]) pq.offer(new int[]{v, weight});
}
}
return totalWeight;
}Q37. When should you prefer Kruskal's algorithm over Prim's, and vice versa?
A: Kruskal's algorithm is preferable for sparse graphs (edges close to O(V) in count) because its cost is dominated by sorting the edge list, O(E log E). Prim's algorithm (with a heap) is preferable for dense graphs, since it's O(E log V), and it also naturally extends to streaming/incremental settings where you grow the tree from a fixed starting vertex. In practice, Kruskal's is often easier to reason about and implement correctly with Union-Find, while Prim's is closer in spirit to Dijkstra's algorithm.
Q38. How does the exchange argument prove Kruskal's algorithm produces a true minimum spanning tree?
A: Suppose an optimal MST T does not contain the cheapest edge e that Kruskal selects (and that doesn't form a cycle). Adding e to T creates exactly one cycle; that cycle must contain some other edge f with weight ≥ e's weight (otherwise T wouldn't be optimal, since swapping in e would lower its cost further — contradiction if f were strictly cheaper). Swapping e for f in T yields another spanning tree with total weight no greater than T's, and it now agrees with Kruskal's first choice; repeating this argument for every edge Kruskal picks shows some optimal MST can always be transformed to match Kruskal's output exactly, proving Kruskal is optimal.
Q39. Does MST construction still work correctly if the graph has negative edge weights?
A: Yes — unlike Dijkstra's shortest-path algorithm, both Kruskal's and Prim's algorithms remain fully correct with negative edge weights, because the cut and cycle properties that justify them don't depend on weights being non-negative, only on comparing relative weights. MST only cares about minimizing total weight among spanning trees, with no notion of "distance accumulated so far" that negative weights could exploit to create the kind of contradiction that breaks Dijkstra.
Q40. What is a "second-best" minimum spanning tree, and how would you find one?
A: A second-best MST is a spanning tree whose total weight is minimal among all spanning trees except the true MST itself (it may tie with the MST in weight if multiple MSTs exist with the same weight). A standard approach builds the MST first, then for every non-tree edge, considers adding it and removing the maximum-weight tree edge on the resulting cycle (found via a preprocessed max-edge-on-path structure), taking the best such swap across all non-tree edges — achievable in O(E log V + E log V) using techniques like binary lifting for path-max queries.
Q41. In what sense is Dijkstra's algorithm a greedy algorithm?
A: Dijkstra repeatedly selects the unvisited vertex with the smallest tentative distance and "finalizes" it, declaring that no future discovery can ever produce a shorter path to it. That finalization is an irrevocable greedy choice, exactly like Kruskal committing to an edge — the vertex is never revisited or reconsidered. This greedy commitment is only safe because, with non-negative weights, no path through an unfinalized (necessarily farther) vertex could ever shortcut back to something shorter than what's already finalized.
Q42. Why does Dijkstra's algorithm produce incorrect results on graphs with negative edge weights?
A: Dijkstra's correctness relies on the assumption that once a vertex is finalized with its shortest distance, no later-discovered path can improve it, because all remaining edges only add non-negative amounts. A negative edge can violate that: a path through a vertex that looked "farther away" at finalization time could still end up cheaper overall if it later crosses a negative edge, but Dijkstra has already locked in the (now wrong) finalized distance and will never revisit it. Graphs with negative edges (but no negative cycles) require Bellman-Ford instead, which explicitly allows relaxing distances repeatedly.
Q43. How do you implement Dijkstra's algorithm using a priority queue in Java?
A: Maintain a distance array initialized to infinity except the source (0), and a min-heap of (vertex, currentBestDistance) pairs. Repeatedly pop the vertex with the smallest recorded distance; if it's stale (a shorter distance was already finalized), skip it; otherwise relax all its outgoing edges, pushing any neighbor whose distance improves. This is O(E log V) with a binary heap since each edge can trigger at most one heap insertion.
int[] dijkstra(int n, List<int[]>[] adj, int src) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
pq.offer(new int[]{src, 0});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int u = cur[0], d = cur[1];
if (d > dist[u]) continue;
for (int[] edge : adj[u]) {
int v = edge[0], weight = edge[1];
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.offer(new int[]{v, dist[v]});
}
}
}
return dist;
}Q44. What is the time complexity of Dijkstra's algorithm with a binary heap versus a Fibonacci heap?
A: With a binary heap, each of the E edge relaxations can trigger an O(log V) heap insertion/decrease, giving O((V + E) log V) overall. With a Fibonacci heap, decrease-key operations are amortized O(1), reducing the complexity to O(E + V log V), which is asymptotically better for dense graphs but rarely used in practice due to higher constant-factor overhead and implementation complexity relative to a simple binary heap.
Q45. What is the difference between Dijkstra's algorithm and Bellman-Ford?
A: Dijkstra is a greedy algorithm restricted to non-negative edge weights, running in O(E log V) by finalizing vertices in increasing distance order and never revisiting them. Bellman-Ford is a dynamic-programming-style algorithm that relaxes every edge up to V-1 times, tolerating negative edge weights (and detecting negative cycles on a final extra pass) at the cost of O(V × E) time, since it makes no greedy assumption about which vertex is truly "done" until all rounds complete.
Q46. How does Dijkstra's algorithm relate to a plain BFS on an unweighted graph?
A: BFS on an unweighted graph is a special case of Dijkstra where every edge has weight 1: because a simple FIFO queue processes vertices in strictly non-decreasing distance order automatically (no need for a priority queue), BFS achieves the same greedy "finalize closest first" guarantee in O(V + E) without any heap overhead. If you gave Dijkstra a graph with all edge weights equal to 1, its priority queue would end up popping vertices in exactly the same order that BFS's plain queue would.
Q47. Give a concrete counterexample showing Dijkstra's greedy relaxation fails with a negative edge.
A: Consider vertices A, B, C with edges A→B weight 5, A→C weight 2, and C→B weight -10. Dijkstra finalizes C first (distance 2, since it's smaller than B's initial 5), then finalizes B with distance 5 (since it doesn't re-examine C→B once it thinks B is settled by direct comparison order) — but relaxing C→B actually gives distance 2 + (-10) = -8, far better than 5. Because Dijkstra never revisits a vertex once popped from the priority queue as "done," it misses this improvement entirely, producing the wrong answer of 5 instead of the correct -8.
Q48. How does the A* search algorithm extend Dijkstra's greedy approach?
A: A* augments Dijkstra's priority key (actual distance so far, g) with an admissible heuristic estimate of the remaining distance to the goal (h), prioritizing vertices by g + h instead of g alone. This focuses the search toward the goal rather than expanding uniformly outward in all directions, often finding the shortest path while exploring far fewer vertices. Correctness (finding the true shortest path) requires the heuristic to be admissible — never overestimating the true remaining distance — which preserves the same non-negative-weight-style greedy safety that Dijkstra depends on.
Q49. What problem does Huffman coding solve?
A: Huffman coding constructs an optimal variable-length prefix code for a set of symbols given their frequencies, minimizing the total encoded length (sum of frequency × code length across all symbols) compared to any other prefix code assignment. It's the classic algorithm behind lossless compression formats like ZIP's DEFLATE and JPEG's entropy coding stage, assigning shorter bit strings to more frequent symbols and longer ones to rarer symbols.
Q50. What is the greedy strategy behind Huffman coding?
A: Put every symbol into a min-priority-queue keyed by frequency, then repeatedly remove the two lowest-frequency nodes, merge them into a new internal node whose frequency is their sum, and reinsert that merged node into the queue. Repeat until only one node remains — the root of the resulting binary tree. The path from root to each leaf, encoded as left=0/right=1, gives that symbol's optimal prefix code.
Q51. Why does repeatedly merging the two lowest-frequency nodes guarantee an optimal prefix code?
A: An exchange argument shows that in any optimal prefix-code tree, the two lowest-frequency symbols must be siblings at the deepest level (if they weren't, swapping them with whichever symbols currently occupy the deepest sibling positions can only reduce or maintain total encoded length, since the lowest frequencies "pay less" for being placed deeper). Merging them first effectively locks in that optimal sibling relationship and reduces the problem to an identical subproblem with one fewer symbol (the merged node standing in for both), which induction shows remains optimal at every level of the recursion.
Q52. How do you build a Huffman tree in Java using a PriorityQueue?
A: Wrap each symbol and frequency in a Comparable node (ordered by frequency), seed a min-heap with all leaf nodes, then loop while more than one node remains: poll the two smallest, create a parent node whose frequency is their sum and whose children are the two polled nodes, and offer the parent back into the heap. The single remaining node after the loop is the Huffman tree's root, built in O(n log n) time for n symbols.
class Node implements Comparable<Node> {
char ch; int freq; Node left, right;
Node(char ch, int freq) { this.ch = ch; this.freq = freq; }
public int compareTo(Node other) { return this.freq - other.freq; }
}
Node buildHuffmanTree(char[] chars, int[] freqs) {
PriorityQueue<Node> pq = new PriorityQueue<>();
for (int i = 0; i < chars.length; i++) pq.offer(new Node(chars[i], freqs[i]));
while (pq.size() > 1) {
Node left = pq.poll();
Node right = pq.poll();
Node parent = new Node('\0', left.freq + right.freq);
parent.left = left;
parent.right = right;
pq.offer(parent);
}
return pq.poll();
}Q53. What is the time complexity of building a Huffman tree for n symbols?
A: Each of the n-1 merge steps performs two poll operations and one offer operation on a heap of size at most n, each O(log n), giving O(n log n) total. Building the initial heap from n symbols costs O(n) (or O(n log n) if inserted one at a time rather than heapified in bulk), so the overall complexity remains O(n log n), dominated by the repeated heap operations during merging.
Q54. Why must Huffman codes be "prefix codes," and what problem would arise otherwise?
A: A prefix code guarantees no codeword is a prefix of another, which is exactly what a binary tree's leaf-only encoding provides — every symbol lives at a leaf, so no symbol's path can be a strict prefix of another's path to a different leaf. Without this property, a decoder reading a bitstream left to right couldn't unambiguously tell when one codeword ends and the next begins (e.g., if "01" and "0" were both codewords, seeing "01..." could mean either symbol, requiring lookahead or backtracking that ruins the streaming, O(1)-per-bit decoding Huffman is designed to enable).
Q55. How does Huffman coding compare to fixed-length encoding in terms of compression?
A: Fixed-length encoding (like plain ASCII) assigns every symbol the same number of bits regardless of frequency, which is simple but wasteful when symbol frequencies are skewed. Huffman coding assigns shorter codes to frequent symbols and longer codes to rare ones, achieving a total encoded size close to the theoretical entropy limit of the source (assuming frequencies are known and symbol probabilities aren't extremely skewed non-power-of-two fractions, where arithmetic coding can do slightly better). For naturally skewed data like English text, Huffman routinely saves 20-40% over fixed-length encoding.
Q56. What are the limitations of Huffman coding compared to arithmetic or adaptive coding?
A: Huffman coding assigns each symbol a whole number of bits, so it can't perfectly capture probabilities that aren't powers of one-half (e.g., a symbol with probability 0.9 "deserves" about 0.15 bits, but Huffman must give it at least 1 bit), leaving some compression on the table versus the entropy limit. Arithmetic and range coding represent the entire message as a single fractional-precision number and can approach the entropy limit arbitrarily closely. Adaptive variants of both approaches update frequency estimates on the fly, avoiding the need to transmit a frequency table upfront and adjusting to non-stationary data.
Q57. How do you implement the (unsafe) greedy coin change algorithm in Java?
A: Sort the coin denominations descending, then for each denomination in order, take as many coins of that value as fit into the remaining amount (integer division), subtract their total value (modulo), and move to the next smaller denomination. This runs in O(k log k + k) for k denominations, but as the name warns, it is only correct for canonical denomination systems — you must verify (or be told) the coin system is canonical before trusting the result.
int greedyCoinChange(int[] coins, int amount) {
Arrays.sort(coins);
int count = 0;
for (int i = coins.length - 1; i >= 0 && amount > 0; i--) {
count += amount / coins[i];
amount %= coins[i];
}
return amount == 0 ? count : -1;
}Q58. Under what conditions does greedy coin selection actually produce the minimum number of coins?
A: Greedy is provably optimal for "canonical" coin systems — informally, ones where each denomination is a multiple of, or otherwise well-structured relative to, the smaller ones, such as standard currency systems like {1, 5, 10, 25} or any powers-of-a-base system like {1, 2, 4, 8, ...}. Formally, a coin system is canonical if, for every amount, the greedy solution's coin count equals the true DP-optimal minimum; this must be verified per denomination set rather than assumed, since it is not guaranteed for arbitrary sets.
Q59. What is a concrete denomination set where greedy coin change gives a suboptimal answer?
A: With coins {1, 3, 4} and a target amount of 6, greedy takes the largest coin ≤ remaining amount first: one 4-coin (remaining 2), then two 1-coins, totaling 3 coins. The true optimum is two 3-coins, totaling only 2 coins. This is the standard textbook counterexample demonstrating that greedy coin selection is not universally correct.
// coins = {1, 3, 4}, amount = 6
// Greedy: takes 4, then 1, then 1 -> 3 coins total (suboptimal)
// Optimal: takes 3, then 3 -> 2 coins total
// greedyCoinChange(new int[]{1, 3, 4}, 6) incorrectly returns 3, not 2Q60. How do you solve minimum-coins coin change correctly using dynamic programming?
A: Build a DP array where dp[a] is the minimum coins needed to make amount a, with dp[0] = 0. For each amount from 1 up to the target, try every denomination ≤ that amount and take 1 + dp[amount - coin], keeping the minimum across all choices. This explores every combination implicitly (unlike greedy's single fixed path) and runs in O(amount × numCoins) time, always correct regardless of whether the coin system is canonical.
int coinChangeDP(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i && dp[i - coin] != Integer.MAX_VALUE) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}Q61. What does it mean for a coin system to be "canonical," and how would you verify one?
A: A canonical coin system is one where the greedy algorithm always matches the DP-optimal minimum coin count for every possible amount. One practical (though not fully general) verification approach, sometimes called Pearson's algorithm, checks all amounts up to a bound related to twice the second-largest denomination, comparing greedy's answer to DP's answer for each; if they never disagree in that range, the system is canonical. For an interview, the safe default is: never assume canonicity — either prove it for the given denominations or use DP.
Q62. How does the coin change "counting the number of ways" problem differ from the minimum-coins problem?
A: Minimum-coins asks for the fewest coins that sum to the target; counting-ways asks how many distinct combinations of coins (regardless of count) sum to the target. Counting-ways is solved with an unbounded-knapsack-style DP: dp[a] += dp[a - coin] processed one coin denomination at a time across all amounts (denomination in the outer loop matters here, to avoid counting permutations as distinct combinations). Neither variant is greedy-solvable in general, since both require considering many combinations, not a single locally-best path.
Q63. What is the job sequencing with deadlines problem?
A: Given a set of jobs, each with a deadline and a profit, and the constraint that every job takes exactly one unit of time and only one job can run per time unit, the problem asks for the subset and schedule of jobs that maximizes total profit while respecting every scheduled job's deadline. Unlike weighted interval scheduling, jobs here have no fixed start time — only a deadline by which they must complete, and each takes the same unit duration.
Q64. What is the greedy strategy for job sequencing with deadlines, and how do you implement it?
A: Sort jobs by profit descending, then for each job (highest profit first), try to schedule it in the latest available time slot ≤ its deadline (scanning slots from the deadline down to 1); if a free slot is found, occupy it and add the profit. This greedily reserves earlier slots for jobs that might need them, since scheduling as late as possible per job never blocks a lower-deadline job unnecessarily. It runs in O(n log n + n × maxDeadline) with a naive slot scan, improvable to O(n log n) with Union-Find over available slots.
class Job {
int id, deadline, profit;
Job(int id, int deadline, int profit) {
this.id = id; this.deadline = deadline; this.profit = profit;
}
}
int jobSequencing(Job[] jobs) {
Arrays.sort(jobs, (a, b) -> b.profit - a.profit);
int maxDeadline = 0;
for (Job j : jobs) maxDeadline = Math.max(maxDeadline, j.deadline);
boolean[] slot = new boolean[maxDeadline + 1];
int totalProfit = 0;
for (Job j : jobs) {
for (int t = j.deadline; t > 0; t--) {
if (!slot[t]) {
slot[t] = true;
totalProfit += j.profit;
break;
}
}
}
return totalProfit;
}Q65. Why does the greedy job sequencing strategy provably yield the maximum total profit?
A: The set of "feasible" job subsets (those schedulable without missing any deadline) forms a matroid: it's hereditary (any subset of a feasible set is feasible), and it satisfies the exchange property (a smaller feasible set can always absorb an element from a larger feasible set while staying feasible, by a slot-shifting argument). By the matroid greedy theorem, processing jobs by decreasing profit and adding each one if it keeps the current set feasible (equivalent to "can it still find a free slot ≤ its deadline") is guaranteed to produce the maximum-weight feasible set.
Q66. How can Union-Find speed up the job sequencing with deadlines greedy algorithm?
A: Instead of a boolean slot array with a linear backward scan per job (worst case O(maxDeadline) per job), model each time slot as a Union-Find element where find(slot) returns the latest still-available slot ≤ that slot. Finding a free slot for a job becomes a single find() call, and occupying it means union-ing that slot with slot-1 (redirecting future lookups past it), reducing the total slot-finding cost to O(n α(n)) amortized instead of O(n × maxDeadline), which matters when maxDeadline can be large relative to n.
Q67. Why does weighted job scheduling (jobs with start and end times, not just deadlines) require DP instead of greedy?
A: Once jobs occupy specific time ranges rather than a uniform single unit before a deadline, choosing a high-profit job can block multiple other jobs whose combined profit exceeds it, and no simple sort-and-greedily-place rule accounts for that interaction correctly (the same failure mode as weighted interval scheduling in general). The standard fix sorts by finish time and applies DP with binary search to find, for each job, the best achievable profit among jobs compatible with it, exploring the necessary include/exclude trade-off that greedy cannot resolve with a single pass.
Q68. What is the key structural difference between "job sequencing with deadlines" and "weighted interval scheduling"?
A: In job sequencing with deadlines, every job takes exactly one unit of time and has no fixed start time, only a deadline — this uniform-duration structure is what makes the feasible-schedule family a matroid and lets greedy work. In weighted interval scheduling, jobs occupy arbitrary, specific start-to-end ranges, so feasibility interacts in a richer, non-matroid way (two jobs might overlap in one ordering but not another), which is precisely why it needs DP instead.
Q69. What is the gas station problem?
A: Given circular arrays of gas available at each station and the cost to travel from each station to the next, the problem asks for the starting station index from which a car (starting with an empty tank) can complete a full loop around all stations without ever running out of gas, or to determine that no such station exists. It's a classic example of a greedy algorithm that avoids an apparent O(n²) brute force (trying every starting point) by exploiting a subtle invariant.
Q70. How do you solve the gas station problem with a single greedy pass, and why does it work?
A: Track a running tank total as you scan stations left to right; whenever the tank goes negative at station i, it proves that no station from the current candidate start through i could possibly work either (each of them would have even less surplus reaching that failure point), so reset the candidate start to i+1 and reset the tank to zero. If the total gas across all stations is ≥ total cost, this single pass is guaranteed to find a valid start, running in O(n) time and O(1) space instead of the O(n²) brute force of testing every start independently.
int canCompleteCircuit(int[] gas, int[] cost) {
int totalTank = 0, currentTank = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
int diff = gas[i] - cost[i];
totalTank += diff;
currentTank += diff;
if (currentTank < 0) {
start = i + 1;
currentTank = 0;
}
}
return totalTank >= 0 ? start : -1;
}Q71. Why is it safe to skip re-testing intermediate starting points once a greedy attempt fails partway through?
A: If starting at station s and driving to station i causes the tank to go negative, then for any candidate start s' strictly between s and i, the tank upon reaching i starting from s' would be no larger than it was starting from s (since s' skips some of the earlier surplus that s enjoyed before failing). Therefore every one of those intermediate starts would fail at or before reaching i too, so they can all be safely skipped in a single pass without individually re-simulating them.
Q72. Prove informally why a valid starting station must exist whenever total gas is at least total cost.
A: If total gas across the whole circuit is ≥ total cost, then the sum of all (gas[i] - cost[i]) differences is ≥ 0. The greedy algorithm's single pass either never goes negative (station 0 already works) or resets its candidate start every time it does go negative; since the overall sum is non-negative, the very last reset point must be a station from which the tank never dips negative again all the way around the loop back to itself — that final candidate is a guaranteed valid start, which is exactly what the algorithm returns.
Q73. What is Jump Game I, and how do you solve it greedily?
A: Given an array where each element is the maximum jump length from that position, Jump Game I asks whether you can reach the last index starting from index 0. Greedily track the farthest index reachable so far as you scan left to right; if you ever reach an index beyond the current farthest reach, you're stuck and the answer is false, otherwise update the farthest reach to max(farthest, i + nums[i]) at each step. This runs in O(n) time and O(1) space, avoiding any need for backtracking or DP.
boolean canJump(int[] nums) {
int maxReach = 0;
for (int i = 0; i < nums.length; i++) {
if (i > maxReach) return false;
maxReach = Math.max(maxReach, i + nums[i]);
}
return true;
}Q74. What is Jump Game II (minimum jumps to reach the end), and how do you solve it greedily?
A: Jump Game II asks for the minimum number of jumps needed to reach the last index, assuming it's always reachable. Track the farthest reachable index within the current jump's range; whenever the scan index reaches the boundary of the current jump ("currentEnd"), that jump is exhausted, so increment the jump counter and extend currentEnd to the farthest reach found so far. This BFS-like greedy processes each "level" of reachability implicitly, achieving O(n) time versus a naive O(n²) DP over all jump choices.
int jump(int[] nums) {
int jumps = 0, currentEnd = 0, farthest = 0;
for (int i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i == currentEnd) {
jumps++;
currentEnd = farthest;
}
}
return jumps;
}Q75. Why is the greedy solution to Jump Game II preferred over an O(n²) DP solution?
A: A straightforward DP defines dp[i] as the minimum jumps to reach index i, computed by checking every earlier index j that can reach i, costing O(n) per index and O(n²) overall. The greedy "BFS-by-levels" approach recognizes that you never need to know the exact optimal predecessor — only the farthest boundary reachable within the current jump count — collapsing the same guarantee into a single O(n) pass with O(1) space, since each index is visited exactly once regardless of how many jump options it has.
Q76. Why do variants like Jump Game III (jumping forward or backward) require BFS/DFS instead of greedy?
A: Once jumps can go both forward and backward (or the goal is just reachability to any zero-valued index rather than the fixed last index), there's no monotonic "farthest reach so far" invariant to exploit greedily — a backward jump can revisit territory, and different jump choices lead to genuinely different, non-comparable reachable sets rather than one clearly dominating another. This makes it a graph-reachability problem, correctly solved with BFS or DFS over the implicit graph of index-to-index jumps, visiting each index once with a visited-set to avoid infinite loops.
Q77. How do you solve the candy distribution problem (ratings-based) using a two-pass greedy scan?
A: Give every child 1 candy initially. In a left-to-right pass, if a child's rating is higher than the child to their left, give them one more candy than that left neighbor. In a right-to-left pass, if a child's rating is higher than the child to their right, ensure they have at least one more candy than that right neighbor (taking the max with what the left pass already assigned). Summing the final array gives the minimum total candies satisfying both neighbor constraints, in O(n) time and O(n) space.
int candy(int[] ratings) {
int n = ratings.length;
int[] candies = new int[n];
Arrays.fill(candies, 1);
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
}
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
}
int total = 0;
for (int c : candies) total += c;
return total;
}Q78. How do you solve the "assign cookies" problem using a greedy strategy?
A: Sort both the children's greed factors and the cookie sizes ascending. Walk through both sorted arrays with two pointers: if the current cookie satisfies the current child's greed factor, count that child as content and advance both pointers; otherwise the cookie is too small for any remaining child (since children are sorted ascending too), so just advance the cookie pointer. This greedily uses the smallest sufficient cookie for the least-greedy unsatisfied child, maximizing satisfied children in O(n log n) time.
int findContentChildren(int[] greed, int[] cookies) {
Arrays.sort(greed);
Arrays.sort(cookies);
int child = 0, cookie = 0;
while (child < greed.length && cookie < cookies.length) {
if (cookies[cookie] >= greed[child]) child++;
cookie++;
}
return child;
}Q79. How do you solve "boats to save people" using two-pointer greedy?
A: Sort people by weight. Use two pointers at opposite ends: try pairing the heaviest remaining person with the lightest remaining person in one boat if their combined weight fits the limit; whether or not that pairing succeeds, the heaviest person must go on a boat this round (either alone or paired), so always advance the heavy-end pointer, and advance the light-end pointer only if pairing succeeded. Each boat launch increments the count, giving O(n log n) time for the sort plus O(n) for the two-pointer sweep.
int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);
int left = 0, right = people.length - 1, boats = 0;
while (left <= right) {
if (people[left] + people[right] <= limit) left++;
right--;
boats++;
}
return boats;
}Q80. How do you solve the "partition labels" problem greedily?
A: First record the last occurrence index of every character in the string. Then scan left to right, extending the current partition's end boundary to the maximum last-occurrence index of every character seen so far in this partition; once the scan index reaches that boundary, the partition is complete and cannot be shrunk further without splitting a character across two partitions. This greedily produces the maximum number of partitions (each character confined to exactly one partition) in O(n) time.
List<Integer> partitionLabels(String s) {
int[] lastIndex = new int[26];
for (int i = 0; i < s.length(); i++) lastIndex[s.charAt(i) - 'a'] = i;
List<Integer> result = new ArrayList<>();
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
end = Math.max(end, lastIndex[s.charAt(i) - 'a']);
if (i == end) {
result.add(end - start + 1);
start = i + 1;
}
}
return result;
}Q81. How do you solve the "lemonade change" problem greedily?
A: Track counts of $5 and $10 bills received so far (you never need to track $20 bills, since they're only ever given as change using a $15 or $10+$5 combination). For a $5 bill, just add it to the till; for a $10 bill, give back one $5 (fail if none available) and keep the $10; for a $20 bill, prefer giving a $10+$5 combination if available (it uses up a less flexible $10 bill), otherwise give three $5 bills, failing if neither combination is possible. This greedy preference order (spend less-flexible change first) runs in O(n) time and provably maximizes the chance of successfully making change throughout the sequence.
boolean lemonadeChange(int[] bills) {
int five = 0, ten = 0;
for (int bill : bills) {
if (bill == 5) five++;
else if (bill == 10) { five--; ten++; }
else if (ten > 0) { ten--; five--; }
else five -= 3;
if (five < 0) return false;
}
return true;
}Q82. How does the fractional knapsack problem differ from 0/1 knapsack, and why does greedy work for it?
A: In fractional knapsack, any fraction of an item can be taken, so there's no all-or-nothing coupling between the choice to include an item and the remaining capacity — you can always use up exactly the remaining capacity with a fraction of the current best-ratio item. Sorting items by value-to-weight ratio descending and greedily taking as much of each as capacity allows (a fraction of the last one, if needed) is provably optimal, since any solution not following this order could be improved by shifting weight toward higher-ratio items. This runs in O(n log n); 0/1 knapsack lacks this divisibility and needs DP instead.
double fractionalKnapsack(int[] weights, int[] values, int capacity) {
int n = weights.length;
Integer[] idx = new Integer[n];
for (int i = 0; i < n; i++) idx[i] = i;
Arrays.sort(idx, (a, b) -> Double.compare(
(double) values[b] / weights[b], (double) values[a] / weights[a]));
double totalValue = 0;
for (int i : idx) {
if (capacity <= 0) break;
int take = Math.min(capacity, weights[i]);
totalValue += take * ((double) values[i] / weights[i]);
capacity -= take;
}
return totalValue;
}Q83. What is the greedy strategy behind "minimum cost to connect ropes/sticks," and how does it relate to Huffman coding?
A: To minimize total connection cost (where connecting two ropes costs the sum of their lengths, added to a running total, repeated until one rope remains), repeatedly connect the two currently-shortest ropes using a min-heap, exactly mirroring Huffman's "merge two smallest frequencies" strategy. It's optimal for the same exchange-argument reason: connecting the two shortest ropes first minimizes how many times their length gets "re-paid" in subsequent merges, since shorter ropes end up deeper in the merge tree and are counted fewer times overall — structurally identical to Huffman tree construction.
int connectRopes(int[] ropes) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int r : ropes) minHeap.offer(r);
int totalCost = 0;
while (minHeap.size() > 1) {
int first = minHeap.poll();
int second = minHeap.poll();
int cost = first + second;
totalCost += cost;
minHeap.offer(cost);
}
return totalCost;
}Q84. How do you solve "remove K digits to form the smallest possible number" using a greedy monotonic stack?
A: Scan digits left to right maintaining a monotonic non-decreasing stack (implemented here as a StringBuilder): whenever the current digit is smaller than the stack's top and removals remain (k > 0), pop the top (a locally "too large" digit that a smaller digit later can beneficially replace higher up), decrementing k. After the scan, if removals remain, trim from the end. Finally strip any leading zeros. This greedily prioritizes making the most-significant digits as small as possible, running in O(n) time since the stack is populated and drained only once each.
String removeKdigits(String num, int k) {
StringBuilder stack = new StringBuilder();
for (char c : num.toCharArray()) {
while (k > 0 && stack.length() > 0 && stack.charAt(stack.length() - 1) > c) {
stack.deleteCharAt(stack.length() - 1);
k--;
}
stack.append(c);
}
while (k-- > 0 && stack.length() > 0) {
stack.deleteCharAt(stack.length() - 1);
}
int start = 0;
while (start < stack.length() - 1 && stack.charAt(start) == '0') start++;
String result = stack.substring(start);
return result.isEmpty() ? "0" : result;
}Q85. What is the greedy strategy for the "two-city scheduling" problem?
A: Given 2n people each with a cost to fly to city A and a cost to fly to city B, and exactly n must go to each city, sort people by the difference (costToA - costToB) ascending — people who "save the most" by going to A relative to B come first. Send the first n (by this sorted order) to city A and the remaining n to city B; this greedily maximizes total savings versus sending everyone to whichever city is individually cheapest, provably minimizing total cost. It runs in O(n log n).
int twoCitySchedCost(int[][] costs) {
Arrays.sort(costs, (a, b) -> (a[0] - a[1]) - (b[0] - b[1]));
int n = costs.length / 2;
int total = 0;
for (int i = 0; i < n; i++) total += costs[i][0];
for (int i = n; i < costs.length; i++) total += costs[i][1];
return total;
}Q86. How does greedy minimize maximum lateness in single-machine job scheduling?
A: When each job has a fixed processing time and a due date, and the goal is to minimize the maximum lateness (completion time minus due date, across all jobs) on a single machine, the earliest-due-date-first (EDD) greedy rule is provably optimal: an exchange argument shows that if two jobs are scheduled out of due-date order, swapping them cannot increase the maximum lateness. This is a different objective from job sequencing with deadlines (which maximizes total profit under hard deadlines) but shares the same greedy-by-sorted-key structure.
Q87. How does "shortest job first" scheduling minimize total/average waiting time?
A: When multiple jobs (with known burst/processing times but no deadlines) must run sequentially on one machine, running the shortest job first minimizes the sum (and thus average) of all jobs' waiting times, because every job "in front of" a given job in the queue adds directly to that job's wait — putting shorter jobs first means fewer total wait-minutes accumulate across all the jobs still behind them. This is provable via an exchange argument: swapping any two adjacent out-of-order jobs (a longer one before a shorter one) strictly reduces total waiting time, so a fully sorted (ascending burst time) order is optimal.
double averageWaitingTime(int[] burstTimes) {
int[] times = burstTimes.clone();
Arrays.sort(times);
long waitTime = 0, totalWait = 0;
for (int t : times) {
totalWait += waitTime;
waitTime += t;
}
return (double) totalWait / times.length;
}Q88. How do you solve "maximum units on a truck" using a greedy sort-by-ratio strategy?
A: Given boxes each with a count and units-per-box, and a truck capacity limited by total number of boxes, sort box types by units-per-box descending, then greedily load boxes from the highest-unit-density type first until either that type is exhausted or the truck's box capacity is reached, moving to the next-best type as needed. This maximizes total units per box loaded, which is optimal because every box costs the same "one slot" of capacity, so the highest-value boxes should always fill slots first — runs in O(n log n).
Q89. What is the greedy strategy for finding the minimum number of points to cover all given intervals?
A: Sort intervals by end coordinate ascending. Whenever the current interval isn't already covered by the most recently placed point, place a new point exactly at that interval's end coordinate (the latest possible position, maximizing the chance it also covers future overlapping intervals) and update the "last placed point" tracker. This is structurally identical to the minimum-arrows-to-burst-balloons problem and runs in O(n log n).
int minPointsToCoverIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
int points = 0;
int lastPoint = Integer.MIN_VALUE;
for (int[] iv : intervals) {
if (iv[0] > lastPoint) {
lastPoint = iv[1];
points++;
}
}
return points;
}Q90. How do you use a greedy first-fit strategy to solve a simplified bin-packing problem?
A: For each item in arrival order, scan existing bins and place the item into the first bin with enough remaining capacity; if none fits, open a new bin. This "first-fit" greedy heuristic doesn't guarantee the true minimum number of bins (bin packing is NP-hard), but it's simple, runs in O(n × numBins) naively (or O(n log n) with better data structures), and is provably within a small constant factor (roughly 1.7×) of optimal in the worst case.
int firstFitBinPacking(int[] items, int capacity) {
List<Integer> bins = new ArrayList<>();
for (int item : items) {
boolean placed = false;
for (int i = 0; i < bins.size(); i++) {
if (bins.get(i) + item <= capacity) {
bins.set(i, bins.get(i) + item);
placed = true;
break;
}
}
if (!placed) bins.add(item);
}
return bins.size();
}Q91. What is the difference between first-fit and first-fit-decreasing bin packing, and why does ordering matter?
A: Plain first-fit processes items in whatever order they arrive, which can lead to poor packing if large items show up after bins are already partially filled with small ones. First-fit-decreasing sorts items by size descending before applying the same first-fit placement rule, which tends to pack large items early (when bins are emptiest) and lets small items fill in remaining gaps later — this simple reordering measurably improves the worst-case approximation ratio (to about 11/9 of optimal) despite being the same underlying greedy placement rule.
Q92. Why does the "minimum cost to merge stones" problem generally require DP rather than a pure greedy Huffman-style merge?
A: Huffman-style greedy merging of the two smallest piles works when any two piles can be merged at any time, but "merge k adjacent stones" problems (a common LeetCode variant) restrict merges to exactly k adjacent piles at once and only where merging is allowed contiguously, breaking the free-choice assumption that makes Huffman's exchange argument valid. That adjacency and fixed-group-size constraint reintroduces the kind of choice-interaction that greedy can't resolve locally, requiring interval DP over subranges instead.
Q93. What is the set cover problem, and why does greedy only give an approximate (not exact) solution?
A: Set cover asks for the minimum number of given subsets whose union covers an entire target universe of elements. The greedy heuristic — repeatedly pick the subset covering the most currently-uncovered elements — is simple and runs in polynomial time, but set cover is NP-hard, so no polynomial algorithm (greedy included) is known to find the exact minimum in general. Greedy is provably within a factor of ln(n) of optimal, which is actually the best approximation ratio achievable in polynomial time unless P = NP.
Q94. Why are greedy algorithms popular for NP-hard problems even though they don't guarantee optimality?
A: For NP-hard problems, no known polynomial-time algorithm guarantees the exact optimum, so practitioners settle for fast heuristics with provable approximation bounds instead. Greedy heuristics are especially popular because they're simple to implement, run quickly (often near-linear), and for many NP-hard problems (set cover, vertex cover, scheduling) their worst-case approximation ratio is both provable and reasonably tight, making them a practical default before reaching for slower techniques like branch-and-bound or metaheuristics.
Q95. How does a greedy algorithm give a 2-approximation for the vertex cover problem?
A: A simple greedy 2-approximation repeatedly picks any remaining uncovered edge and adds both of its endpoints to the cover, removing every edge incident to either endpoint before repeating; because each pick "pays for" covering at least one edge with two vertices, and any valid vertex cover must have included at least one endpoint of that edge, the resulting cover is at most twice the size of the true minimum vertex cover. This runs in O(E) time and, while not exact, gives a simple, easily-provable worst-case guarantee for an NP-hard problem.
Q96. How do you distribute chocolates to minimize maximum difference between distributed and remaining piles (chocolate distribution problem)?
A: Given an array of packet sizes and a number of students m, sort the packet sizes ascending, then slide a window of size m across the sorted array, computing (window's max - window's min) for each position and keeping the minimum such difference. Sorting first ensures that any contiguous window represents the tightest possible grouping of m values, since spreading the selection across non-adjacent sorted positions could only increase the max-min gap. This runs in O(n log n).
Q97. How do you find the least number of unique integers remaining after removing k elements, using a greedy frequency-based approach?
A: Count the frequency of every distinct value, then sort those frequencies ascending. Greedily remove entire groups starting from the least-frequent value (since removing a whole low-frequency group eliminates one unique value "cheaply," using the fewest removals per eliminated unique count), continuing while k allows a full group removal. The number of remaining unique values after this greedy elimination is the answer, computed in O(n log n).
Q98. Why do problems needing "look-ahead" or "undo" naturally break the greedy paradigm?
A: Greedy makes a single irrevocable choice per step based only on information available up to that point, with no mechanism to reconsider it later. Any problem where the correctness of an early choice fundamentally depends on information that only becomes available much later (or where a choice sometimes needs to be partially undone once a downstream conflict is discovered) cannot be captured by that "commit once, never revisit" model — such problems inherently need either DP (to consider all relevant possibilities in a structured way) or backtracking (to explicitly undo and retry).
Q99. What is a formal template for writing an exchange-argument proof during an interview?
A: State the greedy rule precisely; assume for contradiction that some optimal solution O disagrees with greedy's first choice; show that swapping (exchanging) O's conflicting element for greedy's chosen element produces another valid solution O' that is no worse than O (often exactly as good, or strictly better); conclude O' is also optimal and now agrees with greedy on this first choice; then induct — apply the same argument to the remaining subproblem after removing the agreed-upon first choice from both O' and greedy's future work. Reaching full agreement after n such exchanges proves greedy achieves an optimal solution.
Q100. Summarize how the cut property, matroid exchange property, and "greedy stays ahead" all relate to the same underlying correctness principle.
A: All three are specialized instances of the general exchange-argument principle: they each show that swapping a piece of some hypothetical better solution for the greedy algorithm's actual choice cannot make that solution worse. The cut property is this principle applied to graph edges crossing a partition (for MST); the matroid exchange property is the same idea abstracted to arbitrary independence systems (covering MST, job sequencing, and more); "greedy stays ahead" restates it as an inductive invariant on partial-solution quality rather than a one-time swap. Recognizing a new problem as an instance of any of these is usually the fastest route to a rigorous greedy correctness proof.
Q101. What signals in a problem statement suggest a greedy algorithm might work?
A: Look for a single, natural sorting key (finish time, ratio, deadline, frequency) after which a simple local rule seems to "obviously" work; a matroid-like independence constraint (adding one more choice either keeps a property valid or doesn't, with no complex interaction between choices); or a problem framed as "maximize count of compatible items" rather than "maximize a value under a shared resource budget." These are recurring shapes behind interval scheduling, MST, and Huffman-style problems.
Q102. What signals suggest dynamic programming is required instead of greedy?
A: Watch for problems where each item carries an independent weight/profit/value that interacts with a shared, limited resource (a budget, capacity, or count) — the presence of "maximize total value subject to a capacity constraint" is the classic knapsack-family signal. Also watch for problems where a small hand-worked example breaks every greedy rule you try, or where the problem explicitly asks for a count of ways or an optimal value defined recursively over overlapping subproblems (like LCS, edit distance, or subset sum).
Q103. What signals suggest backtracking or exhaustive search is required instead of greedy?
A: Backtracking is typically needed when the problem asks to enumerate all valid configurations (permutations, combinations, valid boards) rather than optimize a single numeric objective, when constraints can only be verified once a full or partial assignment exists (like N-Queens or Sudoku), or when the input size is explicitly small (n ≤ 20 or so), hinting that exponential-but-pruned search is the intended approach rather than a polynomial greedy or DP solution.
Q104. What is the most common mistake candidates make when assuming a greedy strategy is correct?
A: The most common mistake is testing a greedy rule against one or two "nice" examples that happen to work, then presenting it as correct without either a proof sketch or a deliberate attempt to break it with an adversarial example. Interviewers specifically probe for this by asking "why does this work?" or "can you think of a case where this fails?" — a strong answer references an exchange argument, a matroid structure, or an explicit counterexample search, not just "it seemed right when I traced through the example."
Q105. How can you quickly stress-test and disprove a greedy hypothesis during a live interview?
A: Construct small adversarial inputs by hand (3-5 elements) specifically designed to create a conflict between the greedy criterion and the true optimum — for coin change, try denominations that skip a "natural" value like {1, 3, 4}; for knapsack-like problems, try two items where one has a slightly better ratio but a much worse absolute fit. If you can't find a counterexample after a couple of honest attempts and the structure resembles a known matroid/exchange pattern, that's reasonable (though not airtight) evidence to proceed with a greedy solution while stating your confidence level honestly.
Q106. How do greedy, DP, and backtracking compare in typical time complexity for the same class of problem?
A: For problems where all three could conceivably apply, greedy is typically the fastest, often O(n log n) (dominated by a sort) or O(n) with O(1) or O(n) extra space. DP is typically polynomial but higher-order, like O(n²) or O(n × capacity), trading time/space for guaranteed correctness on problems greedy can't handle. Backtracking is typically exponential in the worst case, like O(2ⁿ) or O(n!), used only when the problem structure genuinely requires exploring a combinatorial search space, usually with pruning to keep it practical for the given input size.
Q107. What are real-world production systems that rely on greedy algorithms?
A: Operating system CPU schedulers use greedy-flavored heuristics like shortest-job-first and earliest-deadline-first for real-time task scheduling; network routing protocols use Dijkstra's greedy shortest-path computation to determine forwarding tables; compression tools (ZIP, JPEG, PNG) use Huffman coding for their entropy-coding stage; and cloud infrastructure schedulers (like Kubernetes' bin-packing-style pod placement) use greedy first-fit-style heuristics to pack workloads onto available nodes efficiently.
Q108. Where specifically are Huffman coding and Dijkstra's algorithm used in real infrastructure?
A: Huffman coding (or a close variant) underlies the entropy-coding stage of DEFLATE (used by ZIP, gzip, and PNG) and is a core component of JPEG's final compression step, both chosen for their speed and provably optimal prefix-code compression given a symbol frequency distribution. Dijkstra's algorithm (or link-state variants built on the same greedy relaxation idea) powers OSPF and IS-IS, the interior gateway routing protocols that compute shortest paths through enterprise and ISP networks, as well as many mapping and turn-by-turn navigation systems' core pathfinding layer (often extended with A*).
Q109. How does greedy algorithm design relate formally to matroid theory and the "independence system" concept?
A: An independence system is any family of subsets closed under taking subsets (hereditary property) without necessarily satisfying the stronger matroid exchange property. Greedy is guaranteed optimal on weighted matroids (by the matroid greedy theorem), but on a general independence system that isn't a matroid, greedy can fail — which is exactly the theoretical reason 0/1 knapsack (an independence system defined by a single capacity constraint, not a matroid) resists greedy while spanning forests and job-deadline feasibility (both genuine matroids) do not. Recognizing whether a constraint structure is a true matroid is the deepest-level justification for why some greedy strategies are provably correct and others are not.
Q110. What is a practical checklist for approaching any greedy-flavored interview question?
A: First, identify a plausible sorting key or local rule from the problem's structure. Second, hand-test it against 2-3 small examples, actively trying to break it with adversarial inputs (skewed ratios, non-canonical denominations, ties). Third, sketch a correctness argument — exchange argument, "greedy stays ahead," or matroid recognition — even informally, rather than assuming correctness from examples alone. Fourth, if you can't find either a counterexample or a convincing proof sketch within a reasonable time, default to DP or backtracking and state clearly why you're making that call; interviewers reward that judgment more than a shaky, unproven greedy answer.
Post a Comment
Add