Algorithms, the step-by-step process to solving problems, is the root if one wants to pursue a career in software developing. It is one of the crucial aspects of Computer Science which helps a student or software developer to find the solution of problems in an intuitive way. In this article, we list down seven important algorithms that one must one while appearing for a technical interview.
1| Sorting Algorithm
In this algorithm, an ordered series is given as an input is rearranged in a certain order and gives a product or result of the sorted array. Some of the important algorithms are mentioned below.
- Quick Sort: This is a comparison-based algorithm which follows the procedure of the Divide and Conquer rule. It basically chooses an element as pivot and partitions the given array around the chosen pivot.
- Merge Sort: Merge Sort is mostly similar to Quick Sort as it also follows the Divide and Conquer algorithm. In this algorithm, the input array is divided into two halves, after calling itself for the two halves, it again merges the two sorted halves.
- Bubble Sort: Bubble sort is one of the simplest sorting algorithms. This algorithm works by comparing each item in the list with the item next to it, and swapping them if required.
- Bucket Sort: Bucket sort or bin sort is a sorting algorithm which performs sorting by distributing the elements of an array or list into a number of buckets. Therefore, each bucket is sorted individually with the help of a separate sorting algorithm.
2| Dynamic Programming Algorithm
A dynamic algorithm programming is much like the “divide-and-conquer” problem except that unlike divide-and-conquer, the subproblems will typically overlap. It is an optimization approach that transforms a complex problem into a sequence of simpler problems.
Some of the important dynamic programming algorithms are mentioned below.
- Fibonacci Sequence
- 0-1 Knapsack Problem
3| Recursive Algorithm
A recursive algorithm is an algorithm which solves a problem by calling itself with the input values of the sub-problem which is a smaller instance of the actual problem. More generally if a problem can be solved utilizing solutions to smaller versions of the same problem, and the smaller versions reduce to easily solvable cases, then one can use a recursive algorithm to solve that problem.
4| Backtracking Algorithm
A backtracking algorithm is a recursive approach where the algorithm tries to construct a solution to a computational problem incrementally, one small piece at a time. It is also known as a depth-first search or branch and bound. Backtracking algorithms are commonly used to make a sequence of decisions, with the goal of building a recursively defined structure satisfying certain constraints. The prototypical backtracking problem is the classical n Queens Problem, first proposed by German chess enthusiast Max Bezzel in 1848.
5| Searching Algorithm
Searching Algorithms are used to retrieve data which is stored within some data structure. This algorithm is classified into two categories i.e. linear search and binary search algorithms. Linear search algorithms check every record for the one associated with a target key in a linear manner. Binary or half interval searches, repeatedly target the center of the search structure and divide the search space in half. Some of the specific applications of this algorithm are 0-1 knapsack problem, nurse scheduling problem, map colouring problem, etc.
6| Greedy Algorithm
A greedy algorithm is a simple algorithm which is used in optimisation problems. This algorithm always takes the best immediate, or local, solution while finding an answer. Greedy algorithms are similar to dynamic programming algorithms in the manner where the solutions are both efficient and optimal if the problem exhibits some particular sort of substructure. Greedy algorithms are quite successful in some problems mentioned below.
- Dijkstra’s Algorithm: Dijkstra’s Algorithm is used to find the shortest paths from a single source vertex to all other vertices in a weighted, directed graph. All weights must be nonnegative.
- Kruskal Algorithm: Kruskal Algorithm is used for computing a minimum spanning tree. It maintains a set of partial minimum spanning trees and repeatedly adds the shortest edge in the graph whose vertices are in the different partial minimum spanning trees.
7| Brute Force Algorithm
This algorithm solves a particular problem in a simple and intuitive way. It consists of inspecting, at all locations in the text between 0 and n-m, whether an event of the pattern starts there or not. Then, after each attempt, it moves the pattern by exactly one position to the right.