PRACTICE • LEARN • GROW
Greedy Algo MCQs
Solve topic-wise placement questions and improve your skills.
Greedy Algo Progress
0 of 34 completed
0%
Topic Track
You are viewing MCQs in preview mode. Log in to select options, submit answers, and track your progress.
Log In to Answer
1
What is the core principle of a Greedy Algorithm?
A.
Explore all possible solution permutations exhaustively
B.
Make the locally optimal choice at each step with the hope of finding a global optimum
C.
Divide the problem into overlapping subproblems and memoize
D.
Randomly choose decisions until a valid answer is found
Explanation & Key
Correct Answer:
2
Which two properties must a problem exhibit for a greedy algorithm to guarantee an optimal solution?
A.
Greedy-choice property and Optimal substructure
B.
Overlapping subproblems and Independent variables
C.
Associativity and Commutativity
D.
NP-Hardness and Completeness
Explanation & Key
Correct Answer:
3
In the Activity Selection / Interval Scheduling problem, by which attribute should activities be sorted to maximize the number of non-overlapping activities?
A.
Start time in ascending order
B.
Finish (end) time in ascending order
C.
Total duration (finish - start) in descending order
D.
Activity ID
Explanation & Key
Correct Answer:
4
Which variant of the Knapsack Problem can be solved optimally using a Greedy approach?
A.
0/1 Knapsack Problem
B.
Fractional Knapsack Problem
C.
Bounded Knapsack Problem
D.
Quadratic Knapsack Problem
Explanation & Key
Correct Answer:
5
What is the time complexity of Huffman Coding on an alphabet of N characters with given frequencies?
A.
O(N log N)
B.
O(N^2)
C.
O(2^N)
D.
O(N)
Explanation & Key
Correct Answer:
6
What type of code does Huffman Coding generate to ensure that no encoded symbol is a prefix of another?
A.
Prefix Code (Prefix-free code)
B.
Hamming Code
C.
Cyclic redundancy code
D.
Fixed-length code
Explanation & Key
Correct Answer:
7
Which Minimum Spanning Tree (MST) algorithm repeatedly adds the lowest-weight edge that does not form a cycle?
A.
Prim's Algorithm
B.
Kruskal's Algorithm
C.
Dijkstra's Algorithm
D.
Bellman-Ford Algorithm
Explanation & Key
Correct Answer:
8
Which Minimum Spanning Tree (MST) algorithm grows a single tree by greedily adding the cheapest edge connecting an unvisited vertex to the current tree?
A.
Prim's Algorithm
B.
Kruskal's Algorithm
C.
Floyd-Warshall Algorithm
D.
Ford-Fulkerson Algorithm
Explanation & Key
Correct Answer:
9
Why does Dijkstra's greedy algorithm fail on graphs with negative edge weights?
A.
It cannot detect undirected cycles
B.
It assumes that once a vertex is marked visited with minimum distance, its shortest distance is finalized and can never decrease
C.
It overflows 32-bit integers
D.
It requires adjacency matrices only
Explanation & Key
Correct Answer:
10
In the Job Sequencing Problem with deadlines where each job takes 1 unit of time and has a profit, what is the greedy choice?
A.
Sort jobs by profit in descending order and schedule each job as late as possible before its deadline
B.
Sort jobs by deadline in ascending order and schedule immediately
C.
Schedule jobs with smallest profits first
D.
Run jobs in alphabetical order
Explanation & Key
Correct Answer:
11
In the Gas Station (Circular Tour) problem, when the running balance of fuel drops below 0 at station `i`, where should the candidate starting station be reset to?
A.
Station 0
B.
Station i + 1
C.
Station i - 1
D.
The station with max gas
Explanation & Key
Correct Answer:
12
What is the time complexity of the Jump Game I problem (can you reach the last index) using the greedy furthest-reach technique?
A.
O(N^2)
B.
O(N)
C.
O(2^N)
D.
O(log N)
Explanation & Key
Correct Answer:
13
In the Coin Change problem for canonical currency denominations (e.g. US coins: 1, 5, 10, 25), the greedy approach works. For arbitrary denominations like {1, 3, 4}, does greedy always find the minimum coins for amount 6?
A.
Yes, greedy always works for any coin denominations
B.
No, greedy gives 4 + 1 + 1 (3 coins), whereas the optimal solution is 3 + 3 (2 coins)
C.
Greedy finds 2 coins always
D.
No coins can make 6
Explanation & Key
Correct Answer:
14
What is the time complexity of Kruskal's Algorithm on a graph with V vertices and E edges using Union-Find with path compression?
A.
O(E log E) or O(E log V)
B.
O(V^2)
C.
O(V * E)
D.
O(V + E)
Explanation & Key
Correct Answer:
15
In the Assign Cookies problem (distributing cookies to satisfy children's greed), how do we maximize the number of satisfied children greedily?
A.
Sort both children's greed factors and cookie sizes; assign the smallest cookie that satisfies each child
B.
Give the largest cookie to the child with smallest greed
C.
Assign cookies randomly
D.
Sort in reverse order only
Explanation & Key
Correct Answer:
16
What greedy strategy solves the "Minimum Number of Platforms Required for a Railway Station"?
A.
Sort arrival and departure times separately; use two pointers to count overlapping trains
B.
Sort by train ID
C.
Keep all trains on one platform
D.
Run BFS on schedules
Explanation & Key
Correct Answer:
17
In the Candy problem (children with ratings in a row must have more candies than their neighbors if their rating is higher), how is it solved greedily in O(N)?
A.
Two passes: left-to-right pass satisfying left neighbors, then right-to-left pass satisfying right neighbors taking the max
B.
Sort children by rating
C.
Give everyone 10 candies
D.
Use a priority queue of size N
Explanation & Key
Correct Answer:
18
Can a greedy algorithm backtrack if a choice made earlier turns out to be suboptimal?
A.
Yes, that is the definition of greedy
B.
No, greedy algorithms never reconsider or reverse decisions once made
C.
Only if running in debug mode
D.
Yes, using recursion stack
Explanation & Key
Correct Answer:
19
In Task Scheduler (LeetCode 621), the minimum intervals needed to execute tasks with cooldown `n` depends greedily on:
A.
The frequency of the most frequent task
B.
The alphabetical ordering of task names
C.
The total number of unique task types only
D.
The execution time of CPU cache
Explanation & Key
Correct Answer:
20
Which of the following problems is guaranteed to be solved to exact optimality by a greedy algorithm?
A.
Travelling Salesperson Problem (TSP)
B.
Fractional Knapsack Problem
C.
0/1 Knapsack Problem
D.
Longest Common Subsequence
Explanation & Key
Correct Answer:
21
Why does the greedy choice of selecting the highest Value/Weight ratio fail for the 0/1 Knapsack problem?
A.
Because items cannot be divided, and picking a high-ratio item may leave unused capacity that could have held combinations of higher total value
B.
Because weights can be negative
C.
Because ratio calculation causes floating point rounding errors
D.
Because 0/1 knapsack is NP-complete and no algorithm can solve it
Explanation & Key
Correct Answer:
22
In the Minimum Platforms required for a railway station problem, how can the problem be solved greedily in O(n log n) time?
A.
Sort arrivals and departures separately; traverse with two pointers incrementing platforms on arrival and decrementing on departure
B.
Check all combinations of train pairs
C.
Use a 2D dynamic programming grid
D.
Sort trains by platform number
Explanation & Key
Correct Answer:
23
What greedy strategy is used in Prim's Algorithm to construct a Minimum Spanning Tree (MST)?
A.
Always pick the global minimum edge in the graph, regardless of connectivity
B.
Always add the minimum weight edge that connects an unvisited vertex to the currently growing tree
C.
Traverse the graph using DFS
D.
Delete the maximum weight edge from each cycle
Explanation & Key
Correct Answer:
24
In Kruskal's Algorithm for MST, which data structure is essential to prevent cycle formation in O(alpha(V)) time?
A.
Disjoint Set Union (DSU / Union-Find) with path compression and union by rank
B.
Binary Search Tree
C.
Stack
D.
Circular Queue
Explanation & Key
Correct Answer:
25
In the Jump Game problem (can you reach index n - 1 from index 0), what greedy invariant is maintained?
A.
The maximum reachable index so far (`maxReach = max(maxReach, i + nums[i])`)
B.
The sum of all jump values
C.
The number of zeroes encountered
D.
The index of the largest number in the array
Explanation & Key
Correct Answer:
26
What is the greedy strategy for the Gas Station circuit problem (LeetCode 134)?
A.
If total_gas >= total_cost, a unique valid starting station is guaranteed to exist; reset start to i + 1 whenever running tank drops below 0
B.
Try starting at every gas station using nested loops
C.
Always pick the gas station with the highest individual gas value
D.
Sort gas stations descending by cost
Explanation & Key
Correct Answer:
27
What is the time complexity of building a Huffman Tree for n distinct characters with given frequencies?
A.
O(n log n) using a Min-Heap of character frequencies
B.
O(n^2)
C.
O(2^n)
D.
O(n!)
Explanation & Key
Correct Answer:
28
In the Task Scheduler problem (with cooldown period n between identical tasks), what determines the theoretical minimum execution time?
A.
The frequency of the most frequent task and how many other tasks share that peak frequency
B.
The total number of tasks divided by n
C.
The order in which tasks are submitted
D.
The number of unique characters in the task list
Explanation & Key
Correct Answer:
29
Which of the following problem statements CANNOT be solved using a greedy approach?
A.
Fractional Knapsack
B.
0/1 Knapsack
C.
Huffman Coding
D.
Dijkstra's Shortest Path on non-negative graphs
Explanation & Key
Correct Answer:
30
In Interval Scheduling, why does sorting by Start Time instead of Finish Time fail to maximize the count of non-overlapping intervals?
A.
An interval starting very early could have a massive duration (e.g. [0, 100]), blocking many shorter subsequent intervals
B.
Start times cannot be compared with integer math
C.
Start times can be negative
D.
Sorting by start time requires O(n^2) space
Explanation & Key
Correct Answer:
31
In Job Sequencing with Deadlines, what is the greedy criterion for selecting jobs to maximize total profit?
A.
Sort jobs descending by profit, and schedule each job in the latest available slot before its deadline
B.
Sort jobs ascending by deadline
C.
Sort jobs ascending by profit
D.
Schedule jobs with shortest duration first
Explanation & Key
Correct Answer:
32
What is the Matroid Theory in discrete mathematics commonly used for?
A.
Proving mathematically whether a greedy algorithm is guaranteed to produce an optimal solution for an optimization problem
B.
Solving matrix multiplication in O(n^2)
C.
Parsing programming language grammars
D.
Generating pseudo-random numbers
Explanation & Key
Correct Answer:
33
In the Candy Distribution problem (LeetCode 135), how is the optimal distribution computed in linear O(n) time and O(n) space?
A.
Two passes: left-to-right pass satisfying right neighbor condition, followed by right-to-left pass taking the maximum
B.
Sort children by ratings
C.
Assign random candies and balance
D.
Binary search on total candies
Explanation & Key
Correct Answer:
34
Why does Dijkstra's greedy algorithm fail when negative edge weights are present in a directed graph?
A.
Once a node is popped from the priority queue and marked finalized, Dijkstra never revisits it; a negative edge discovered later could have yielded a shorter path
B.
Priority queues cannot store negative numbers
C.
Negative edges cause compiler errors in C++
D.
Negative edges create infinite trees
Explanation & Key
Correct Answer:
Question Palette
Answered
Current
Not Attempted
Wrong
