Introduction To Algorithms
Before we dive into the interview algorithms, it is essential to understand what algorithms are. An Algorithm is a “set of rules to obtain the expected output from an input”. Algorithms play an important role in problem-solving in general, which is one of the reasons coding interviews are mostly wrapped around algorithms regardless of the position you are applying for, role front-end not excluded!
Top Coding Interview Algorithms
So, now you know about algorithms and probably have started to figure out why they make a big part of the coding interviews, which is to see how you can design an effective solution to an existing problem. However, you are not going to write an algorithm for an alien problem, but rather be asked to explain existing algorithms to test how well you understand them, Hence, here are the top coding algorithms that are likely to be part of your next interview questions.
1. Quick sort.
2. Backtracking.
3. Insertion Sort.
4. Bubble Sort.
5. Linear Search.
6. Greedy Algorithm.
7.Binary Search.
Binary search algorithm
The binary search algorithm is used on a sorted array to search for the position of a specific item by repeatedly dividing the array in half. The idea is that we create an interval(which is the entire array on the starting point), if the item is less than the array’s midpoint, we reduce the array to the lower half. Otherwise, we make use of the upper half. We repeat until the value is found or the array becomes empty.
-Steps in implementing Binary Search
1. Start by comparing the search item to the middle element.
2. If the search item is equal to the middle element, return the index(position) of the middle element.
3. Or, if the search item is greater than the middle element, cut off the lower part of the array.
4. Otherwise, reduce the array to the lower half
5. Repeat until it is found or the array becomes empty.
The Greedy Algorithm.
What is the Greedy Algorithm?
A greedy algorithm is a method whose only goal is to choose the best optimal decision at every step in the solution of the problem, which eventually leads to a globally optimal solution. In other words, it chooses the best solution available at that time.
When to use a Greedy Algorithm?
You can use a Greedy algorithm if the following properties are true in the problem.
-Greedy choice property.
This is a problem whereby a global solution can be obtained by making a locally optimal solution at each iteration. The choice is affected by previous choices but does not depend on future choices.
-Optimal substructure.
This means that when the solution to an entire problem and sub-problems are optimal.
Examples of the Greedy Algorithm
1. Knapsack problem
2. Kruskal’s Minimal spanning Tree Algorithm
3. Traveling salesman problem
4. Huffman coding
5. Selection sort
6. Coin change problem.
Linear Search
In a linear search algorithm, the position of a variable is searched by iterating over the entire array comparing the variable to the element at each iteration. If the variable is not found, we claim the variable is not in the array. The algorithm is sometimes called sequential search.
-Steps in writing a Linear Search Algorithm.
1. Start by comparing the variable to the first element in the array.
2. If the variable is found in the first element return the index of the first element and terminate the search.
3. Otherwise, move to the next element.
4. Repeat until the variable is found.
5. If the variable is not in the array, terminate the search.
Bubble Sort
In the bubble sort algorithm, two adjacent elements are compared, if these elements are in the desired order (either ascending or descending order), we move on (this means comparing your last element to the next element). Otherwise, we swap their position.
-Steps in writing a Bubble sort.
1. Start by comparing the first two-element in the array.
2. if they are in the desired order, move on by comparing the last element with the next.
3. Otherwise, swap the value of the elements at both positions.
4. Repeat steps (2, 3) until the end of the array.
5. Repeat the entire procedure for the number of elements in the array.
Insertion Sort
The idea of insertion sort is to virtually split the array into two parts (sorted and unsorted), then loop over the position in the array, starting from the beginning. At each iteration, you pick an element from the unsorted part of the array, check if it is the minimum or maximum (depending on sorting in ascending or descending order) value in the unsorted part and place it in the sorted part of the array. This algorithm is only very suitable for a small number of elements.
-Steps in writing an Insertion Sort Algorithm.
1. Assume the first element is the minimum value on the list.
2. Iterate over the rest of the element and compare it to your current minimum value to find the overall minimum value on the list.
3. If a new minimum value is found, swap its position with the current minimum value.
4. Move on to the next element on the list and repeat steps 2 and 3 until the array is sorted.
Backtracking.
Backtracking searches for the solution of a problem in all available options. The idea is very simple, we try to solve the problem with the currently selected approach. If the problem is solved, we output the solution otherwise we select other options to solve the problem. If none of the options reached a solution, we claim no solution to the problem.
Example Algorithms of Backtracking.
1. Binary Strings: generating all binary strings
2. N-Queens Problem
3. Generalized Strings
4. Hamiltonian Cycles
Quicksort
This sorting algorithm uses the divide-and-conquer method. It works by selecting an element as a pivot from the array and splitting the array into two sub-arrays, which contain elements that are greater than the pivot and elements less than the pivot. This process is done recursively until the array can no more be partitioned. The Quicksort algorithm can also be referred to as a partition-exchange sort.
-Steps in writing a Quicksort Algorithm.
1. Consider the first element as a pivot element.
2. partition the array into two parts, elements greater than the pivot and those less than the pivot.
3. Repeat the same process for the two arrays that are obtained until you can no more divide the array.
Conclusion
It is important to understand how this algorithm works rather than trying to master the code, in an interview you will not be asked to write the code for an algorithms, instead you will be asked to explain how the algorithm works and how you can apply them to a real world problem.
Good luck!
