Top 7 Greedy Algorithm Problems

 
A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.

 
Below are commonly asked greedy algorithm problems in technical interviews –
 

Activity Selection Problem

Given a set S of activities with start time and finish time of each activity, find the maximum number of activities that can be performed by a single person assuming that a person can only work on a single activity at a time.

 

Greedy coloring of graph

Greedy coloring of graphThe graph coloring (also called as vertex coloring) is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color. In this post we will discuss a greedy algorithm for graph coloring and try to minimize the number of colors used.

 

Job Sequencing Problem with Deadlines

Given a set of tasks with deadlines and total profit earned on completion of a task, find maximum profit earned by executing the tasks within the specified deadlines. Assume any task will take one unit of time to execute and any task can’t execute beyond its deadline. Also, only one task can be executed at a time.

 

Shortest Superstring Problem

Given a list of strings where no string is substring of another, find a shortest string that contains each string in given list as a substring.

 

Find minimum number of platforms needed in the station so to avoid any delay in arrival of any train

Given a schedule containing arrival and departure time of trains in a station, find minimum number of platforms needed in the station so to avoid any delay in arrival of any train.

 

Huffman Coding

Huffman Coding is a algorithm for doing data compression and it forms the basic idea behind file compression. This post talks about fixed length and variable length encoding, uniquely decodable codes, prefix rules and construction of Huffman Tree.

 

Single-Source Shortest Paths – Dijkstra’s Algorithm

Given a source vertex s from set of vertices V in a weighted graph where all its edge weights w(u, v) are non-negative, find the shortest-path weights d(s, v) from given source s for all vertices v present in the graph.

 

Kruskal’s Algorithm for finding Minimum Spanning Tree

Given a undirected, connected and weighted graph, construct a minimum spanning tree out of it.

 

Thank you all being with us. 🙂

 




Like us? Please spread the word and help us grow. Happy coding 🙂