Greedy Algorithms - DSA Interview Questions

Greedy algorithms make locally optimal choices at each step, aiming to find a global optimum. This approach is widely used in optimization problems, scheduling, and resource allocation. Understanding when and how to apply greedy strategies is key to solving problems efficiently.

Practice Greedy Algorithms DSA Coding Problems with Solutions

Learning Objectives:

Learn greedy strategies such as activity selection, Huffman encoding, interval scheduling, and coin change. Understand how greedy algorithms differ from dynamic programming and when greedy solutions guarantee optimal results.

Exercise Instructions:

Start with the first problem and attempt to solve it before checking the hint or solution.
Ensure you understand the logic behind each solution, as this will help you with more complex problems.
Use these exercises to reinforce your learning and identify areas that may require further study.

1. Fractional Knapsack Problem

Required Input:

items = [(60, 10), (100, 20), (120, 30)]
capacity = 50

Expected Output:

240.0

Code In Python

def fractional_knapsack(items, capacity): # Write your logic here pass # Prefilled input items = [(60, 10), (100, 20), (120, 30)] capacity = 50 print(fractional_knapsack(items, capacity))

Run Code?

Click Run Button to view compiled output

2. Activity Selection Problem

Required Input:

activities = [(1, 3), (2, 5), (4, 6), (6, 8), (5, 7)]

Expected Output:

Code In Python

def max_activities(activities): # Write your logic here pass # Prefilled input activities = [(1, 3), (2, 5), (4, 6), (6, 8), (5, 7)] print(max_activities(activities))

Run Code?

Click Run Button to view compiled output

3. Minimum Number of Coins

Required Input:

coins = [1, 2, 5, 10, 20, 50, 100, 500, 1000]
amount = 93

Expected Output:

[50, 20, 20, 2, 1]

Code In Python

def min_coins(coins, amount): # Write your logic here pass # Prefilled input coins = [1, 2, 5, 10, 20, 50, 100, 500, 1000] amount = 93 print(min_coins(coins, amount))

Run Code?

Click Run Button to view compiled output

4. Job Sequencing with Deadlines

Required Input:

jobs = [(100, 2), (27, 1), (15, 2), (10, 1), (5, 3)]

Expected Output:

[100, 27, 5]

Code In Python

def job_sequencing(jobs): # Write your logic here pass # Prefilled input jobs = [(100, 2), (27, 1), (15, 2), (10, 1), (5, 3)] print(job_sequencing(jobs))

Run Code?

Click Run Button to view compiled output

5. Maximize the Sum After K Negations

Required Input:

arr = [-4, -2, -3, 6]
k = 2

Expected Output:

Code In Python

def maximize_sum(arr, k): # Write your logic here pass # Prefilled input arr = [-4, -2, -3, 6] k = 2 print(maximize_sum(arr, k))

Run Code?

Click Run Button to view compiled output

6. Minimum Sum of Two Numbers Formed From Digits of an Array

Required Input:

digits = [1, 2, 3, 4, 5, 6]

Expected Output:

Code In Python

def min_sum_two_numbers(digits): # Write your logic here pass # Prefilled input digits = [1, 2, 3, 4, 5, 6] print(min_sum_two_numbers(digits))

Run Code?

Click Run Button to view compiled output

7. Gas Station Problem

Required Input:

gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]

Expected Output:

Code In Python

def can_complete_circuit(gas, cost): # Write your logic here pass # Prefilled input gas = [1, 2, 3, 4, 5] cost = [3, 4, 5, 1, 2] print(can_complete_circuit(gas, cost))

Run Code?

Click Run Button to view compiled output

8. Minimum Platforms Required for Trains

Required Input:

arrivals = [900, 940, 950, 1100, 1500, 1800]
departures = [910, 1200, 1120, 1130, 1900, 2000]

Expected Output:

Code In Python

def min_platforms(arrivals, departures): # Write your logic here pass # Prefilled input arrivals = [900, 940, 950, 1100, 1500, 1800] departures = [910, 1200, 1120, 1130, 1900, 2000] print(min_platforms(arrivals, departures))

Run Code?

Click Run Button to view compiled output

9. Assign Mice to Holes

Required Input:

mice = [4, -4, 2]
holes = [4, 0, 5]

Expected Output:

Code In Python

def assign_mice_to_holes(mice, holes): # Write your logic here pass # Prefilled input mice = [4, -4, 2] holes = [4, 0, 5] print(assign_mice_to_holes(mice, holes))

Run Code?

Click Run Button to view compiled output

10. Candy Distribution Problem

Required Input:

ratings = [1, 0, 2]

Expected Output:

Code In Python

def min_candies(ratings): # Write your logic here pass # Prefilled input ratings = [1, 0, 2] print(min_candies(ratings))

Run Code?

Click Run Button to view compiled output

1 of 3