Home » Interview coding problems/challenges

Greedy Strategy to solve major algorithm problems

In this article, we are going to see what greedy algorithm is and how it can be used to solve major interview problems based on algorithms? Submitted by Radib Kar, on December 03, 2018

Introduction:

Let's start the discussion with an example that will help to understand the greedy technique. If we think about playing chess, when we make a move we think about the consequences of the move in future states, but in case of playing cricket or tennis, we consider immediate states rather considering any future consequences. This means in some cases we make decisions which seems to be correct at that moment and in some cases we make a decision based on the following consequences or future cases.

The idea of local and global can take place here. Local means the immediate case where global means considering the future situation.

The greedy technique is all about making a local decision, based n that immediate case, on based on future consequences and that's why the strategy is known as greedy.

Greedy strategy

Greedy strategy means to make a decision at each step without taking account its consequence at future steps. We find out the best local move at each step to reach the goal. The greedy strategy assumes that a bunch of local best decisions can lead to global optimization.

What greedy algorithm consists of?

The basic properties of the greedy strategy can be divided into two part:

1. Greedy choice property
2. Optimal substructure

Greedy choice property is about making local optimization (greedy). The choices made by greedy may depend on the past moves but never on the future steps. Iteratively, we make each greedy move to reduce the problem to a smaller problem and finally to achieve global optimization.

Optimal substructure means if we can divide the problem to further sub-problems and have optimal solutions for that, which will combine to a solution to solve the entire large problem.

Does greedy work always?

Needless to say, making a local best choice can't lead to global best choice always. Just think of a hill and think while climbing you are to find the maximum peak. You took a greedy strategy and found a local peak which is not at all global.

Thus greedy strategy doesn't work for all to give the best solutions.

Greedy algorithm at a glance

Why to use greedy algorithm?

• It's straightforward, easy to examine and easy to code.
• Since we are making local moves, no need to store any computation to re-examine.

But greedy has pitfalls

• It doesn't have a solution to all problems
• In many cases greedy fails to lead optimal solution
• In some cases, it misleads to a wrong solution

Still due to the simple structure and strategic nature greedy has a lot of applications. In interview coding problems we also use greedy strategy to the well-known greedy problems. Following is a list of applications where greedy can be used:

• Sorting: Topological sort, heap sort
• Priority Queue
• Huffman coding compression
• Prim's and Kruskal's algorithm
• Dijkstra's algorithm to find the shortest path in a weighted graph
• Coin change problem
• Fractional knapsack problem
• Job scheduling problem

There is also a special use of the greedy technique. When we need to find an approximate solution to a complex problem, greedy can be a superb choice.