50 Greedy Algorithm Interview Questions in C

Basic Greedy Concepts – Short Answer Interview Questions

  1. What is a greedy algorithm?
    An algorithm that makes the locally optimal choice at each step, hoping to reach a global optimum. It never revisits past decisions.
  2. How is greedy different from dynamic programming?
    Greedy picks one best local choice per step without storing subproblem results. DP explores overlapping subproblems and uses memoization or tabulation to guarantee optimality.
  3. When does a greedy approach work?
    When the problem has greedy-choice property and optimal substructure—each local best choice leads to a globally optimal solution.
  4. What is the greedy-choice property?
    A global optimum can be reached by making a locally optimal choice first, without needing to reconsider earlier choices.
  5. What is optimal substructure in greedy problems?
    An optimal solution to the problem contains optimal solutions to its subproblems after the greedy choice is made.
  6. Give a classic example where greedy works.
    Activity selection: sort by finish time and pick non-overlapping activities greedily to maximize count.
  7. Give a classic example where greedy fails.
    0/1 knapsack: taking highest value/weight ratio first does not always maximize total value when items cannot be split.
  8. Why does fractional knapsack allow greedy but 0/1 knapsack does not?
    Fractional knapsack lets you take partial items, so value/weight ratio sorting is optimal. 0/1 knapsack requires considering combinations, which greedy cannot guarantee.
  9. What is the typical time complexity of a greedy solution?
    Often O(n log n) due to sorting, plus O(n) for the greedy pass—e.g., activity selection and job sequencing.
  10. What proof techniques are used for greedy algorithms?
    Exchange argument, staying ahead, and cut property (for MST) are common ways to prove correctness.
  11. Explain activity selection in one line.
    Sort activities by finish time; always pick the next compatible activity with the earliest finish.
  12. How does job sequencing with deadlines work?
    Sort jobs by profit descending; schedule each job in the latest available slot before its deadline using a slot array or disjoint set.
  13. Why sort by finish time in interval problems?
    Choosing the activity that finishes earliest leaves maximum room for subsequent activities, maximizing the count of non-overlapping intervals.
  14. What is Huffman coding?
    A lossless compression scheme that assigns shorter bit codes to more frequent characters using a min-heap–built binary tree.
  15. Why is a min-heap used in Huffman coding?
    Repeatedly merging the two smallest-frequency nodes builds a tree with minimum weighted path length (optimal prefix code).
  16. When does the coin-change greedy algorithm work?
    For canonical coin systems (e.g., standard US coins) where the greedy choice at each step is always part of some optimal solution.
  17. Give coin denominations where greedy coin change fails.
    Coins {1, 3, 4} for amount 6: greedy gives 4+1+1 (3 coins) but optimal is 3+3 (2 coins).
  18. How does Prim's algorithm use greedy choice?
    It grows the MST by always adding the minimum-weight edge connecting the current tree to a vertex outside it.
  19. How does Kruskal's algorithm use greedy choice?
    It sorts all edges by weight and adds the smallest edge that does not form a cycle, using union-find.
  20. Is Dijkstra's shortest path algorithm greedy?
    Yes. It repeatedly selects the unvisited vertex with the smallest known distance and relaxes its neighbors (with non-negative weights).
  21. Why does Dijkstra fail with negative edge weights?
    A later negative edge could reduce a distance already finalized by the greedy step, breaking the assumption that the current minimum is final.
  22. What is the minimum platforms problem?
    Given arrival and departure times, find the maximum number of trains at the platform at any moment—sort events and sweep a counter.
  23. How do you solve "minimum number of arrows to burst balloons"?
    Sort balloons by end coordinate; shoot an arrow at the end of the first balloon and skip all overlapping ones, then repeat.
  24. What is the Egyptian fraction greedy method?
    Repeatedly subtract the largest unit fraction 1/ceil(d/n) from the remainder until the fraction is fully represented.
  25. What data structure helps in "connect n ropes with minimum cost"?
    A min-heap: always merge the two shortest ropes first, similar to Huffman construction.
  26. How is fractional knapsack implemented in C?
    Sort items by value/weight ratio descending; take full items while capacity allows, then take a fraction of the next item.
  27. What is the exchange argument proof idea?
    Show any optimal solution can be transformed into the greedy solution by swapping choices without worsening the result.
  28. What is the "staying ahead" proof idea?
    Prove that after each greedy step, the greedy solution is at least as good as any other solution's partial result at the same stage.
  29. Can greedy be used for finding longest path in a graph?
    No. Longest path is NP-hard in general graphs; greedy local choices do not guarantee a global longest route.
  30. What is a common interview tip when choosing greedy?
    Try to identify a sorting key (ratio, deadline, end time), prove or argue greedy-choice property, and mention a counterexample if greedy might fail.

Advanced Greedy Concepts – Short Answer Interview Questions

  1. How do you solve "gas station" (circular tour) greedily?
    Track total fuel and current tank; if tank goes negative, restart from the next station. If total fuel ≥ total cost, a solution exists.
  2. Explain "assign mice to holes" greedy approach.
    Sort mice positions and hole positions; pair the i-th mouse with the i-th hole to minimize maximum distance.
  3. How does "remove k digits to form smallest number" work?
    Use a monotonic stack: pop digits while the top is greater than the current digit and removals remain; trim leading zeros.
  4. What is the greedy idea in "jump game" (can reach last index)?
    Track the farthest reachable index while scanning; if current index exceeds farthest, return false; else update farthest with i + nums[i].
  5. How do you minimize cash flow among friends?
    Compute net balance for each person; repeatedly settle the largest creditor with the largest debtor (greedy on magnitudes).
  6. Why is "rearrange string so no two adjacent are same" sometimes greedy with max-heap?
    Always place the most frequent remaining character if possible; if not, the arrangement is impossible (freq max > (n+1)/2).
  7. What is the greedy approach for "maximize stock profit with unlimited transactions"?
    Sum all positive day-to-day price differences (buy at every valley, sell at every peak in one pass).
  8. How does "minimum refueling stops" use greedy + heap?
    At each reachable station, push available fuel into a max-heap; when you cannot reach the next stop, use the largest fuel can seen so far.
  9. What is the interval covering greedy pattern?
    Sort by start (or end); extend coverage by choosing the interval that reaches farthest from the current point.
  10. How is chocolate distribution problem solved greedily?
    Sort packets; slide a window of size m students and minimize (max − min) in that window.
  11. What is the greedy coloring algorithm for graphs?
    Order vertices; assign each the smallest color not used by already colored neighbors. Not optimal but simple.
  12. When is greedy coloring optimal?
    For interval graphs and some special classes; in general it can use more colors than chromatic number.
  13. How do you prove Prim's algorithm is correct?
    Use the cut property: the minimum edge crossing any cut belongs to some MST; Prim always adds such an edge.
  14. How do you prove Kruskal's algorithm is correct?
    Same cut property—adding the smallest safe (non-cycle-forming) edge at each step builds an MST.
  15. What is the difference between greedy and brute force?
    Brute force tries all combinations (often exponential). Greedy makes one decisive choice per step (usually polynomial).
  16. Can backtracking and greedy be combined?
    Yes—use greedy to prune or order choices (e.g., try most promising branch first), but backtrack when greedy leads to dead ends.
  17. What is the time complexity of Huffman coding?
    O(n log n) for n distinct characters using a min-heap to merge nodes repeatedly.
  18. How do you detect if greedy fails for a new problem?
    Look for counterexamples where local optimum blocks a better global arrangement; try small cases and compare with DP/brute force.
  19. What greedy pattern fits "minimum cost to hire k workers"?
    Sort by wage/quality ratio; maintain a max-heap of qualities for the k workers and minimize wage × max quality in the window.
  20. What are real-world uses of greedy algorithms?
    Compression (Huffman), routing (Dijkstra), network design (MST), scheduling, caching, and load balancing heuristics.
Related Greedy Algorithm Resources
Simple Programs
MCQs
Problem Solving Tricks
Topic-wise Problems
Tech Hub