Greedy Algorithm Questions for Placement 2026 (with Solutions)

Last Updated: March 2026

---

Overview

Greedy algorithms make locally optimal choices at each step with the hope of finding a global optimum. While not always optimal, greedy algorithms provide efficient solutions for many problems and are frequently tested in technical interviews. Understanding when to apply greedy vs dynamic programming is crucial.

Companies Focused on Greedy Algorithms

• Google: Interval scheduling, Huffman coding, meeting rooms
• Amazon: Activity selection, jump game, task scheduling
• Microsoft: Fractional knapsack, gas station, candy distribution
• Meta: Reconstruct queue, remove k digits
• Apple: Job sequencing, minimum platforms
• Uber: Route optimization with greedy heuristics

---

Core Concepts

Greedy Algorithm Properties

A problem can be solved using greedy approach if it has:

1. Greedy Choice Property: A global optimum can be reached by choosing local optimum at each step
2. Optimal Substructure: An optimal solution contains optimal solutions to subproblems

Common Greedy Strategies

1. Sorting-based Greedy
   - Sort by finish time (activity selection)
   - Sort by value/weight ratio (fractional knapsack)
   - Sort by deadline (job sequencing)

2. Selection-based Greedy
   - Always pick the best available option
   - Discard options that don't satisfy constraints

3. Exchange Argument
   - Prove greedy choice doesn't worsen optimal solution
   - Show we can exchange elements to get greedy solution

Greedy vs Dynamic Programming

Aspect	Greedy	Dynamic Programming
Decision	One shot, never reconsider	Multiple choices, may reconsider
Optimal	Not always optimal	Always optimal
Speed	Faster	Slower
Examples	Dijkstra, Kruskal	Floyd-Warshall, 0/1 Knapsack

---

20 Frequently Asked Coding Questions

---

Question 1: Activity Selection Problem

Problem: Select maximum number of activities that don't overlap.

class Solution:
    def activitySelection(self, start, end):
        """
        start: list of start times
        end: list of end times
        """
        n = len(start)
        
        # Create activities and sort by end time
        activities = [(start[i], end[i]) for i in range(n)]
        activities.sort(key=lambda x: x[1])  # Sort by end time
        
        selected = [activities[0]]
        last_end = activities[0][1]
        
        for i in range(1, n):
            if activities[i][0] >= last_end:
                selected.append(activities[i])
                last_end = activities[i][1]
        
        return selected
    
    # Count only
    def maxActivities(self, start, end):
        activities = sorted(zip(start, end), key=lambda x: x[1])
        count = 1
        last_end = activities[0][1]
        
        for i in range(1, len(activities)):
            if activities[i][0] >= last_end:
                count += 1
                last_end = activities[i][1]
        
        return count

# Driver Code
start = [1, 3, 0, 5, 8, 5]
end = [2, 4, 6, 7, 9, 9]
sol = Solution()
print(sol.maxActivities(start, end))  # Output: 4
print(sol.activitySelection(start, end))
# Output: [(1, 2), (3, 4), (5, 7), (8, 9)]

Time Complexity: O(n log n) for sorting
Space Complexity: O(n)

---

Question 2: Fractional Knapsack

Problem: Maximize value in knapsack with fractional items allowed.

class Solution:
    def fractionalKnapsack(self, values, weights, capacity):
        """
        values: list of item values
        weights: list of item weights
        capacity: knapsack capacity
        """
        n = len(values)
        
        # Calculate value/weight ratio for each item
        items = [(values[i] / weights[i], values[i], weights[i]) 
                 for i in range(n)]
        
        # Sort by ratio in descending order
        items.sort(reverse=True, key=lambda x: x[0])
        
        total_value = 0.0
        remaining_capacity = capacity
        
        for ratio, value, weight in items:
            if remaining_capacity >= weight:
                # Take whole item
                total_value += value
                remaining_capacity -= weight
            else:
                # Take fraction of item
                fraction = remaining_capacity / weight
                total_value += value * fraction
                break  # Knapsack is full
        
        return total_value

# Driver Code
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
sol = Solution()
print(sol.fractionalKnapsack(values, weights, capacity))  # Output: 240.0

Time Complexity: O(n log n)
Space Complexity: O(n)

---

Question 3: N Meetings in One Room

Problem: Find maximum meetings that can be held in one room.

class Solution:
    def maxMeetings(self, start, end):
        n = len(start)
        
        # Create meeting objects with original indices
        meetings = [(start[i], end[i], i + 1) for i in range(n)]
        
        # Sort by end time
        meetings.sort(key=lambda x: x[1])
        
        selected = [meetings[0][2]]  # Store meeting numbers
        last_end = meetings[0][1]
        
        for i in range(1, n):
            if meetings[i][0] > last_end:
                selected.append(meetings[i][2])
                last_end = meetings[i][1]
        
        return selected

# Driver Code
start = [1, 3, 0, 5, 8, 5]
end = [2, 4, 6, 7, 9, 9]
sol = Solution()
print(sol.maxMeetings(start, end))  # Output: [1, 2, 4, 5]

Time Complexity: O(n log n)
Space Complexity: O(n)

---

Question 4: Job Sequencing with Deadlines

Problem: Schedule jobs to maximize profit, each job takes unit time.

class Solution:
    def jobSequencing(self, jobs):
        """
        jobs: list of (job_id, deadline, profit)
        """
        # Sort by profit in descending order
        jobs.sort(key=lambda x: x[2], reverse=True)
        
        # Find maximum deadline
        max_deadline = max(job[1] for job in jobs)
        
        # Result array: slot -> job_id
        result = [-1] * (max_deadline + 1)
        total_profit = 0
        job_count = 0
        
        for job_id, deadline, profit in jobs:
            # Find available slot from deadline backwards
            for slot in range(min(deadline, max_deadline), 0, -1):
                if result[slot] == -1:
                    result[slot] = job_id
                    total_profit += profit
                    job_count += 1
                    break
        
        return job_count, total_profit, [x for x in result if x != -1]

# Optimized version using Union-Find
class JobSequencingOptimized:
    def __init__(self, n):
        self.parent = list(range(n + 1))
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def jobSequencing(self, jobs):
        jobs.sort(key=lambda x: x[2], reverse=True)
        max_deadline = max(job[1] for job in jobs)
        
        uf = JobSequencingOptimized(max_deadline)
        total_profit = 0
        job_count = 0
        
        for job_id, deadline, profit in jobs:
            available_slot = uf.find(deadline)
            if available_slot > 0:
                total_profit += profit
                job_count += 1
                uf.parent[available_slot] = uf.find(available_slot - 1)
        
        return job_count, total_profit

# Driver Code
jobs = [('a', 4, 20), ('b', 1, 10), ('c', 1, 40), 
        ('d', 1, 30)]
sol = Solution()
print(sol.jobSequencing(jobs))  # Output: (2, 60, ['c', 'a'])

Time Complexity: O(n²) or O(n log n) with Union-Find
Space Complexity: O(max_deadline)

---

Question 5: Minimum Number of Coins

Problem: Find minimum coins needed to make a given amount (Indian currency).

class Solution:
    def minCoins(self, coins, amount):
        """
        coins: available denominations (should include 1)
        amount: target amount
        """
        # Sort in descending order
        coins.sort(reverse=True)
        
        coin_count = 0
        remaining = amount
        used_coins = []
        
        for coin in coins:
            if remaining >= coin:
                count = remaining // coin
                coin_count += count
                remaining -= coin * count
                used_coins.extend([coin] * count)
            
            if remaining == 0:
                break
        
        return coin_count, used_coins

# Driver Code
coins = [1, 2, 5, 10, 20, 50, 100, 500, 1000]
amount = 93
sol = Solution()
print(sol.minCoins(coins, amount))  # Output: (5, [50, 20, 20, 2, 1])

Time Complexity: O(n log n) for sorting, O(amount) in worst case
Space Complexity: O(1)

---

Question 6: Huffman Coding

Problem: Generate optimal prefix codes for characters based on frequency.

import heapq
from collections import defaultdict

class HuffmanNode:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None
    
    def __lt__(self, other):
        return self.freq < other.freq

class Solution:
    def huffmanCoding(self, chars, freqs):
        """
        chars: list of characters
        freqs: list of frequencies
        """
        # Create min heap
        min_heap = [HuffmanNode(chars[i], freqs[i]) for i in range(len(chars))]
        heapq.heapify(min_heap)
        
        # Build Huffman tree
        while len(min_heap) > 1:
            left = heapq.heappop(min_heap)
            right = heapq.heappop(min_heap)
            
            # Create internal node
            merged = HuffmanNode(None, left.freq + right.freq)
            merged.left = left
            merged.right = right
            
            heapq.heappush(min_heap, merged)
        
        # Generate codes
        root = min_heap[0]
        codes = {}
        self._generateCodes(root, "", codes)
        
        return codes
    
    def _generateCodes(self, node, current_code, codes):
        if node is None:
            return
        
        if node.char is not None:
            codes[node.char] = current_code or "0"
            return
        
        self._generateCodes(node.left, current_code + "0", codes)
        self._generateCodes(node.right, current_code + "1", codes)

# Driver Code
chars = ['a', 'b', 'c', 'd', 'e', 'f']
freqs = [5, 9, 12, 13, 16, 45]
sol = Solution()
codes = sol.huffmanCoding(chars, freqs)
print(codes)
# Output: {'f': '0', 'c': '100', 'd': '101', 'a': '1100', 'b': '1101', 'e': '111'}

Time Complexity: O(n log n)
Space Complexity: O(n)

---

Question 7: Minimum Platforms Required

Problem: Find minimum number of platforms needed for trains.

class Solution:
    def findPlatform(self, arr, dep):
        """
        arr: arrival times
        dep: departure times
        """
        # Sort both arrays
        arr.sort()
        dep.sort()
        
        n = len(arr)
        platforms_needed = 0
        max_platforms = 0
        
        i = j = 0
        
        while i < n and j < n:
            if arr[i] <= dep[j]:
                # Train arrives, need platform
                platforms_needed += 1
                max_platforms = max(max_platforms, platforms_needed)
                i += 1
            else:
                # Train departs, free platform
                platforms_needed -= 1
                j += 1
        
        return max_platforms

# Driver Code
arr = [900, 940, 950, 1100, 1500, 1800]
dep = [910, 1200, 1120, 1130, 1900, 2000]
sol = Solution()
print(sol.findPlatform(arr, dep))  # Output: 3

Time Complexity: O(n log n)
Space Complexity: O(1)

---

Question 8: Jump Game

Problem: Determine if you can reach the last index.

class Solution:
    def canJump(self, nums):
        max_reach = 0
        n = len(nums)
        
        for i in range(n):
            if i > max_reach:
                return False
            
            max_reach = max(max_reach, i + nums[i])
            
            if max_reach >= n - 1:
                return True
        
        return True
    
    # Find minimum jumps
    def jump(self, nums):
        n = len(nums)
        if n <= 1:
            return 0
        
        jumps = 0
        current_end = 0
        farthest = 0
        
        for i in range(n - 1):
            farthest = max(farthest, i + nums[i])
            
            if i == current_end:
                jumps += 1
                current_end = farthest
                
                if current_end >= n - 1:
                    break
        
        return jumps

# Driver Code
nums = [2, 3, 1, 1, 4]
sol = Solution()
print(sol.canJump(nums))  # Output: True
print(sol.jump(nums))     # Output: 2

Time Complexity: O(n)
Space Complexity: O(1)

---

Question 9: Gas Station

Problem: Find starting gas station to complete circuit.

class Solution:
    def canCompleteCircuit(self, gas, cost):
        n = len(gas)
        total_gas = 0
        total_cost = 0
        current_tank = 0
        start_station = 0
        
        for i in range(n):
            total_gas += gas[i]
            total_cost += cost[i]
            current_tank += gas[i] - cost[i]
            
            # If tank is negative, can't start from current station
            if current_tank < 0:
                start_station = i + 1
                current_tank = 0
        
        return start_station if total_gas >= total_cost else -1

# Driver Code
gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
sol = Solution()
print(sol.canCompleteCircuit(gas, cost))  # Output: 3

Time Complexity: O(n)
Space Complexity: O(1)

---

Question 10: Candy Distribution

Problem: Distribute candies so each child gets at least 1 and higher-rated children get more.

class Solution:
    def candy(self, ratings):
        n = len(ratings)
        candies = [1] * n
        
        # Left to right pass
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1
        
        # Right to left pass
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candies[i] = max(candies[i], candies[i + 1] + 1)
        
        return sum(candies)

# Driver Code
ratings = [1, 0, 2]
sol = Solution()
print(sol.candy(ratings))  # Output: 5

Time Complexity: O(n)
Space Complexity: O(n), can be optimized to O(1)

---

Question 11: Remove K Digits

Problem: Remove k digits to form the smallest possible number.

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []
        
        for digit in num:
            # Remove larger digits from stack
            while k > 0 and stack and stack[-1] > digit:
                stack.pop()
                k -= 1
            stack.append(digit)
        
        # Remove remaining digits from end
        while k > 0:
            stack.pop()
            k -= 1
        
        # Remove leading zeros
        result = ''.join(stack).lstrip('0')
        
        return result if result else "0"

# Driver Code
num = "1432219"
k = 3
sol = Solution()
print(sol.removeKdigits(num, k))  # Output: "1219"

Time Complexity: O(n)
Space Complexity: O(n)

---

Question 12: Queue Reconstruction by Height

Problem: Reconstruct queue from (height, k) pairs.

class Solution:
    def reconstructQueue(self, people):
        """
        people: list of [height, k] where k is number of people in front
        who are taller or same height
        """
        # Sort by height descending, then k ascending
        people.sort(key=lambda x: (-x[0], x[1]))
        
        result = []
        for person in people:
            # Insert at position k
            result.insert(person[1], person)
        
        return result

# Driver Code
people = [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]
sol = Solution()
print(sol.reconstructQueue(people))
# Output: [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]

Time Complexity: O(n²) due to insert, can be O(n log n) with advanced DS
Space Complexity: O(n)

---

Question 13: Assign Cookies

Problem: Maximize number of children satisfied with cookies.

class Solution:
    def findContentChildren(self, g, s):
        """
        g: greed factors of children
        s: sizes of cookies
        """
        g.sort()
        s.sort()
        
        child_i = cookie_j = 0
        content_children = 0
        
        while child_i < len(g) and cookie_j < len(s):
            if s[cookie_j] >= g[child_i]:
                # Cookie satisfies child
                content_children += 1
                child_i += 1
            cookie_j += 1
        
        return content_children

# Driver Code
g = [1, 2, 3]  # Greed factors
s = [1, 1]     # Cookie sizes
sol = Solution()
print(sol.findContentChildren(g, s))  # Output: 1

Time Complexity: O(n log n + m log m)
Space Complexity: O(1)

---

Question 14: Non-overlapping Intervals

Problem: Find minimum intervals to remove for no overlaps.

class Solution:
    def eraseOverlapIntervals(self, intervals):
        if not intervals:
            return 0
        
        # Sort by end time
        intervals.sort(key=lambda x: x[1])
        
        count = 0
        last_end = intervals[0][1]
        
        for i in range(1, len(intervals)):
            if intervals[i][0] < last_end:
                # Overlapping, remove this interval
                count += 1
            else:
                # Non-overlapping, keep this
                last_end = intervals[i][1]
        
        return count
    
    # Alternative: Find maximum non-overlapping
    def maxNonOverlapping(self, intervals):
        if not intervals:
            return 0
        
        intervals.sort(key=lambda x: x[1])
        
        count = 1
        last_end = intervals[0][1]
        
        for i in range(1, len(intervals)):
            if intervals[i][0] >= last_end:
                count += 1
                last_end = intervals[i][1]
        
        return count

# Driver Code
intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
sol = Solution()
print(sol.eraseOverlapIntervals(intervals))  # Output: 1

Time Complexity: O(n log n)
Space Complexity: O(1)

---

Question 15: Boats to Save People

Problem: Minimum boats to carry people with weight limit.

class Solution:
    def numRescueBoats(self, people, limit):
        people.sort()
        
        left, right = 0, len(people) - 1
        boats = 0
        
        while left <= right:
            if people[left] + people[right] <= limit:
                # Both can fit
                left += 1
            # Heaviest always goes
            right -= 1
            boats += 1
        
        return boats

# Driver Code
people = [3, 2, 2, 1]
limit = 3
sol = Solution()
print(sol.numRescueBoats(people, limit))  # Output: 3

Time Complexity: O(n log n)
Space Complexity: O(1)

---

Question 16: Partition Labels

Problem: Partition string so each letter appears in at most one part.

class Solution:
    def partitionLabels(self, s: str):
        # Find last occurrence of each character
        last_occurrence = {char: i for i, char in enumerate(s)}
        
        partitions = []
        start = end = 0
        
        for i, char in enumerate(s):
            end = max(end, last_occurrence[char])
            
            if i == end:
                # Current partition ends here
                partitions.append(end - start + 1)
                start = i + 1
        
        return partitions

# Driver Code
s = "ababcbacadefegdehijhklij"
sol = Solution()
print(sol.partitionLabels(s))  # Output: [9, 7, 8]

Time Complexity: O(n)
Space Complexity: O(1) - Fixed 26 characters

---

Question 17: Hand of Straights

Problem: Check if hand can be grouped into straights of size W.

from collections import Counter

class Solution:
    def isNStraightHand(self, hand, W):
        if len(hand) % W != 0:
            return False
        
        count = Counter(hand)
        
        for card in sorted(count):
            if count[card] > 0:
                needed = count[card]
                # Try to form straights starting from this card
                for i in range(W):
                    if count[card + i] < needed:
                        return False
                    count[card + i] -= needed
        
        return True

# Driver Code
hand = [1, 2, 3, 6, 2, 3, 4, 7, 8]
W = 3
sol = Solution()
print(sol.isNStraightHand(hand, W))  # Output: True

Time Complexity: O(n log n)
Space Complexity: O(n)

---

Question 18: Minimum Cost to Hire K Workers

Problem: Hire exactly K workers minimizing cost (quality + wage ratio).

import heapq

class Solution:
    def mincostToHireWorkers(self, quality, wage, K):
        n = len(quality)
        
        # Calculate ratio for each worker
        workers = [(wage[i] / quality[i], quality[i]) for i in range(n)]
        
        # Sort by ratio
        workers.sort()
        
        # Max heap for qualities (using negative for max heap)
        max_heap = []
        sum_quality = 0
        min_cost = float('inf')
        
        for ratio, q in workers:
            heapq.heappush(max_heap, -q)
            sum_quality += q
            
            if len(max_heap) > K:
                sum_quality += heapq.heappop(max_heap)
            
            if len(max_heap) == K:
                min_cost = min(min_cost, sum_quality * ratio)
        
        return min_cost

# Driver Code
quality = [10, 20, 5]
wage = [70, 50, 30]
K = 2
sol = Solution()
print(sol.mincostToHireWorkers(quality, wage, K))  # Output: 105.0

Time Complexity: O(n log n)
Space Complexity: O(K)

---

Question 19: Two City Scheduling

Problem: Minimize cost to send exactly n people to each city.

class Solution:
    def twoCitySchedCost(self, costs):
        """
        costs: [[costA, costB], ...]
        """
        n = len(costs) // 2
        
        # Sort by difference (costA - costB)
        # Negative difference = cheaper to send to A
        # Positive difference = cheaper to send to B
        costs.sort(key=lambda x: x[0] - x[1])
        
        total_cost = 0
        
        # First n go to city A
        for i in range(n):
            total_cost += costs[i][0]
        
        # Last n go to city B
        for i in range(n, 2 * n):
            total_cost += costs[i][1]
        
        return total_cost

# Driver Code
costs = [[10, 20], [30, 200], [400, 50], [30, 20]]
sol = Solution()
print(sol.twoCitySchedCost(costs))  # Output: 110

Time Complexity: O(n log n)
Space Complexity: O(1)

---

Question 20: Create Maximum Number

Problem: Create maximum number of length k from two arrays.

class Solution:
    def maxNumber(self, nums1, nums2, k):
        def pick_max(nums, k):
            """Pick k digits to form maximum number"""
            drop = len(nums) - k
            stack = []
            for num in nums:
                while drop and stack and stack[-1] < num:
                    stack.pop()
                    drop -= 1
                stack.append(num)
            return stack[:k]
        
        def merge(a, b):
            """Merge two arrays to form maximum"""
            result = []
            while a or b:
                if a > b:
                    result.append(a.pop(0))
                else:
                    result.append(b.pop(0))
            return result
        
        max_result = [0] * k
        
        for i in range(max(0, k - len(nums2)), min(k, len(nums1)) + 1):
            part1 = pick_max(nums1, i)
            part2 = pick_max(nums2, k - i)
            merged = merge(part1[:], part2[:])
            max_result = max(max_result, merged)
        
        return max_result

# Driver Code
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
sol = Solution()
print(sol.maxNumber(nums1, nums2, k))  # Output: [9, 8, 6, 5, 3]

Time Complexity: O(k × (m + n))
Space Complexity: O(k)

---

MCQ Questions

Question 1

Which property must a problem have for greedy algorithm to work optimally?

• A) Overlapping subproblems
• B) Greedy choice property
• C) Both A and B
• D) None of the above

---

Question 2

What is the time complexity of activity selection problem?

• A) O(n)
• B) O(n log n)
• C) O(n²)
• D) O(2^n)

---

Question 3

Fractional knapsack uses which approach?

• A) Dynamic Programming
• B) Greedy
• C) Backtracking
• D) Divide and Conquer

---

Question 4

Why doesn't greedy work for 0/1 knapsack?

• A) It requires sorting
• B) Items cannot be divided
• C) It's too slow
• D) Memory constraints

---

Question 5

In Huffman coding, what type of tree is built?

• A) Binary Search Tree
• B) Full Binary Tree
• C) Complete Binary Tree
• D) Balanced Binary Tree

---

Interview Tips for Greedy Algorithms

1. Identify greedy problems:

   • Optimization problems
   • Making locally optimal choices leads to global optimum
   • Problems involving sorting and selection

2. Prove correctness:

   • Use exchange argument
   • Show greedy choice doesn't worsen solution
   • Prove optimal substructure

3. Common greedy strategies:

   • Sort by some criteria (finish time, ratio, deadline)
   • Always pick the best available option
   • Two-pointer technique

4. When greedy fails:

   • Try dynamic programming instead
   • Problems requiring future information
   • Problems with complex constraints

5. Practice problems:

   • Interval scheduling variants
   • Resource allocation
   • String manipulation (remove k digits)
   • Array partitioning

---

Frequently Asked Questions

Q1: How do I know if a problem can be solved using greedy?

A: Check if making locally optimal choices leads to global optimum. Look for problems involving sorting, selection, or resource allocation. Try to prove using exchange argument.

Q2: What is the difference between greedy and dynamic programming?

A: Greedy makes one choice and never looks back. DP explores all choices and uses memoization. Greedy is faster but doesn't always give optimal solution.

Q3: Why does activity selection sort by finish time?

A: Sorting by finish time leaves maximum remaining time for other activities. This greedy choice allows accommodating maximum activities.

Q4: Can greedy be used for graph problems?

A: Yes! Dijkstra's shortest path, Prim's MST, and Kruskal's MST all use greedy approaches.

Q5: What is the exchange argument in greedy proofs?

A: Exchange argument shows that any optimal solution can be transformed into the greedy solution without worsening the result, proving greedy is also optimal.

---

Master these greedy problems to recognize patterns in interviews. Always try to prove why greedy works (or doesn't) for a given problem.