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:

- Greedy choice property
- 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.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions