C Programming Greedy Algorithm MCQs
Basic Greedy Concepts (20 Questions)
1. What is the main idea of a greedy algorithm?
A) Try all combinations
B) Make the best local choice at each step
C) Always use recursion
D) Sort the output
Answer: B) Make the best local choice at each step
Greedy builds a solution step by step by picking the locally optimal option.
2. Which problem is a classic greedy example?
A) 0/1 Knapsack (always)
B) Activity selection
C) Longest common subsequence
D) Matrix chain multiplication
Answer: B) Activity selection
Activity selection uses finish-time sorting and greedy compatibility checks.
3. Fractional knapsack is solved greedily by sorting on:
A) Weight ascending
B) Value descending
C) Value/weight ratio descending
D) Random order
Answer: C) Value/weight ratio descending
Take items with highest value per unit weight first; split the last item if needed.
4. Activity selection sorts activities by:
A) Start time
B) Duration
C) Finish time
D) Profit
Answer: C) Finish time
Earliest finish time leaves room for more activities.
5. Huffman coding uses which data structure?
A) Stack
B) Queue
C) Min-heap
D) Hash map only
Answer: C) Min-heap
Repeatedly merge two lowest-frequency nodes.
6. Greedy coin change works for:
A) All coin systems
B) Canonical coin systems only
C) Only one coin type
D) Never
Answer: B) Canonical coin systems only
Non-canonical systems need DP (e.g., coins 1,3,4 for amount 6).
7. Prim's MST algorithm is an example of:
A) Dynamic programming
B) Greedy
C) Backtracking
D) Divide and conquer only
Answer: B) Greedy
Always adds the minimum edge crossing the cut.
8. Kruskal's MST algorithm sorts edges by:
A) Destination vertex
B) Weight ascending
C) Weight descending
D) Source vertex
Answer: B) Weight ascending
Add smallest safe edges using union-find.
9. Dijkstra's algorithm is greedy when edge weights are:
A) Negative
B) Non-negative
C) Zero only
D) Fractional only
Answer: B) Non-negative
Negative edges break the greedy finalize assumption.
10. Typical time complexity of greedy with sorting:
A) O(1)
B) O(n log n)
C) O(n²)
D) O(2^n)
Answer: B) O(n log n)
Sort dominates; greedy scan is usually O(n).
11. Greedy differs from DP because greedy:
A) Stores all subproblems
B) Does not reconsider past choices
C) Always slower
D) Requires exponential space
Answer: B) Does not reconsider past choices
DP may explore multiple subproblem states; greedy commits locally.
12. Job sequencing with deadlines maximizes:
A) Number of jobs
B) Total profit
C) Total duration
D) Minimum deadline
Answer: B) Total profit
Schedule high-profit jobs in latest available slots.
13. Minimum platforms problem uses:
A) Stack only
B) Event sweep after sorting times
C) Binary search tree
D) Graph coloring only
Answer: B) Event sweep after sorting times
Treat arrivals and departures as events; track concurrent trains.
14. 0/1 knapsack generally requires:
A) Greedy only
B) DP or brute force
C) BFS
D) Huffman coding
Answer: B) DP or brute force
Greedy ratio fails when whole items must be taken.
15. The greedy-choice property means:
A) Random choice works
B) A global optimum can be reached by local optima
C) All choices are equal
D) Sorting is unnecessary
Answer: B) A global optimum can be reached by local optima
Core requirement for greedy correctness.
16. Connect n ropes with minimum cost uses:
A) Max-heap
B) Min-heap merging smallest two
C) Stack
D) Queue only
Answer: B) Min-heap merging smallest two
Same pattern as Huffman tree construction.
17. Non-overlapping intervals: remove minimum intervals by sorting on:
A) Start time
B) End time
C) Interval length
D) Random
Answer: B) End time
Keep intervals that finish earliest; count removals.
18. Gas station circular tour greedy tracks:
A) Only total profit
B) Total fuel and current tank
C) Number of stations visited
D) Maximum distance
Answer: B) Total fuel and current tank
Reset start when tank goes negative; feasible if total fuel ≥ total cost.
19. Exchange argument is used to:
A) Swap variables in C
B) Prove greedy correctness
C) Sort arrays
D) Compress files
Answer: B) Prove greedy correctness
Show any optimal solution can be transformed into the greedy one.
20. Which is NOT typically greedy?
A) Fractional knapsack
B) Activity selection
C) 0/1 knapsack (general)
D) Huffman coding
Answer: C) 0/1 knapsack (general)
0/1 knapsack needs DP for guaranteed optimality.
Advanced Greedy Concepts (10 Questions)
21. Jump game (can reach last index) greedy tracks:
A) Minimum jump
B) Farthest reachable index
C) Array sum
D) Sorted order
Answer: B) Farthest reachable index
If i > farthest, fail; else farthest = max(farthest, i + nums[i]).
22. Remove k digits to form smallest number uses:
A) Queue
B) Monotonic stack
C) BST
D) Hash table
Answer: B) Monotonic stack
Pop larger digits while k removals remain; strip leading zeros.
23. Assign mice to holes minimizes time by:
A) Random pairing
B) Sorting both arrays and pairing
C) Using DFS
D) Using BST
Answer: B) Sorting both arrays and pairing
Pair i-th smallest mouse with i-th smallest hole.
24. Minimum refueling stops combines greedy with:
A) Stack
B) Max-heap of fuel
C) Queue only
D) Trie
Answer: B) Max-heap of fuel
When stuck, use largest fuel cans seen in reachable range.
25. Rearrange string (no adjacent same) fails when:
A) String is empty
B) Max frequency > (n+1)/2
C) All chars unique
D) String is palindrome
Answer: B) Max frequency > (n+1)/2
Most frequent char would need adjacent duplicate placement.
26. Stock profit unlimited transactions greedy sums:
A) All prices
B) Positive day-to-day differences
C) Maximum price only
D) Minimum price only
Answer: B) Positive day-to-day differences
Capture every upward move (valley to peak).
27. Chocolate distribution minimizes diff by:
A) Sorting + sliding window of size m
B) DFS
C) Huffman coding
D) Graph BFS
Answer: A) Sorting + sliding window of size m
Minimize max-min among m consecutive sorted packets.
28. Minimum cost to hire k workers sorts by:
A) Wage only
B) Wage/quality ratio
C) Quality only
D) Name
Answer: B) Wage/quality ratio
Maintain k workers in a window; cost = ratio × max quality in heap.
29. Greedy coloring assigns each vertex:
A) Random color
B) Smallest unused color among neighbors
C) Same color
D) Maximum color index
Answer: B) Smallest unused color among neighbors
Simple heuristic; not always optimal chromatic number.
30. When greedy fails, you should usually try:
A) More printf
B) DP or exhaustive search
C) Larger stack only
D) Remove sorting
Answer: B) DP or exhaustive search
If no proof/counterexample check fails, switch paradigm.
Related Greedy Resources
Related Greedy Algorithm Resources