Algorithm 2: Dutch National Flag Algorithm
The Dutch National Flag Algorithm is an algorithm that is used to solve the popular sort 0 1 2 problems with ease and in O(N) time. The approach is fairly simple, you have to create three variables, low, mid and high were low and midpoint to the start of the array and high points to the end of the array.
After the sorting has been performed the elements between low and mid will be 0, between mid and high will be 1 and after high will be 2. When you encounter a 0 at the index where mid is pointing, swap mid and low and increment the mid pointer by 1.
When you encounter a 1 at the index where mid is pointing, increment the mid pointer by 1. And finally, when you encounter a 2 at the index where mid is pointing, swap mid and high, increment mid by 1 and decrement high by 1.
Algorithm:
Begin DutchNationalFlagAlgo(arr, size):
low = 0
mid = 0
high = size-1
while mid<=high:
if arr[mid] == 0
swap(arr[mid],arr[low])
low++
mid++
End if
if arr[mid] == 1
mid++
End if
if arr[mid] == 2
swap(arr[mid],arr[high])
mid++
high--
End if
End while
End
The time complexity of the dutch national flag algorithm is O(N) as we are traversing the array only once and the space complexity is O(1) as there is no extra storage used.
Problems for Practice:
Algorithm 3: Two Pointers Technique
The two-pointers technique is a technique where two-pointers are used to keep track of different indices. The pointers can start together from the same index or they can start from opposite directions in the array. This technique is useful for comparisons and traversing the array quickly while keeping a check on two elements simultaneously.
Problems for Practice:
Algorithm 4: Sliding Window Algorithm
The sliding window algorithm proves to be extremely vital while solving questions on strings and arrays. This technique helps in lowering down the time complexity from O(N^2) to O(N).
The sliding window can either be of a fixed size or the size may vary according to the condition given in the question. The state of the window also has to be maintained. This approach can be used on linear data structures such as an array of integers or higher data structures such as linked lists, queues and deques.
Problems for Practice:
Algorithm 5: Slow and Fast Pointers Technique in Linked List
The slow and fast pointer technique in linked lists proves to be quite beneficial for a number of questions based on linked lists. It basically involves two pointers whereas one pointer takes n steps (slow pointer) and the other pointer takes 2*n steps (fast pointer).
Problems for Practice:
Algorithm 6: Recursion
Recursion is the algorithm by the virtue of which a given problem can be divided into smaller problems that can be solved with ease. To identify if a function is recursive, you can see if that function is calling itself and if that is the case, we say that the given function is a recursive function.
Every recursive function consists of three parts – base case. recursive call and function computations. The base case indicates the condition where the recursion needs to stop, in the absence of a base case, the function will call itself infinitely and cause a TLE in your program.
The recursive call is made to handle a smaller problem of the problem assigned to us. The function computations are done before or after the recursive call depending upon the question.
Given below is the recursive algorithm for finding the factorial of a number:
Begin factorial(n):
if n==0
return 1
smallFact = factorial (n-1)
fact = n*smallFact
return fact
End
Problems for Practice:
Algorithm 7: Divide and Conquer
The divide and conquer algorithm is an extension of the recursive algorithm where a given problem is divided into subproblems and then each subproblem is solved separately and recursively (the conquer step) after which the answers to these subproblems are combined to make a final answer.
The divide and conquer approach is advantageous as many problems can be solved parallelly which is an efficient usage of the memory. The divide and conquer approach can also prove to be beneficial for complex problems like the Tower of Hanoi.
Algorithm:
Begin divideAndConquer(A)
if(small(A)) return solution;
return
combine{
divideAndConquer(A1)
divideAndConquer(A2)
.
.
.
divideAndConqier(Ak)
}
End
Algorithm 8: Backtracking
Backtracking is an algorithmic technique which uses the recursive paradigm to explore and find out all possible ways and directions for a particular problem. Backtracking is used for problems where a decision has to be made, a feasible solution has to be found, the most feasible solution has to be found or even all feasible solutions have to be found.
Popular problems like N-Queens, Rat Maze, Sudoku, Maze Path etc. can be solved using backtracking. It is also used in popular knapsack problems. Backtracking is extremely easy to understand and using this, one can come up with a solution very quickly.
Mixed Problems for Practice (Recursion, Divide and Conquer, and Backtracking)
Algorithm 9: Dynamic Programming
During recursion, the same calls and computations are made repeatedly. When dealing with large data, this could cause overflows and generate a time limit exceeded error. To cope up with this issue, dynamic programming comes into the picture which stores the already computed values and makes them available so that the program does not have to re-compute the values.
For example, if we are calculating the fibonacci numbers, we are making two calls in every recursive call – fib(n-1) and fib(n-2) then we can infer that when we are calling fib(5) it will call fib(4) and fib(3) and when we call fib(4) it will call fib(3) and fib(2), fib(3) is being called twice which causes re-computations. Now if we store the value of fib(3) somewhere the first time we are calling it, our work will reduce significantly.
Algorithm:
Begin fib(n,dp)
if(n==0 or n==1) return n
if(dp[n] != -1) return dp[n]
ans = fib(n-1) + fib(n-2)
dp[n] = ans
return ans
End
Problems for Practice:
Algorithm 10: Graph Algorithms (BFS and DFS)
There are two ways to traverse graphs – breadth first and depth first.
Algorithm:
Begin DFS(graph, cur)
visited[cur] = true
for all neighbors of v of cur in graph:
if visited[v] == false
DFS(graph,v)
return
End
Algorithm:
Begin BFS(graph, source)
Q.enqueue(source)
visited[source] - true
while Q
cur = Q.front()
Q.dequeue()
for all neighbors v of cur in graph:
if visited[v] is false
Q.enqueue(v)
visited[v] = true
End
Problems for Practice:
Frequently Asked Questions
What algorithms are you able to implement during the interview using any programming language?
All the algorithms can be implemented by using any programming language.
How do you ace the coding interview?
To ace a coding interview, you are supposed to be well versed with data structures, algorithms and computer fundamentals.
Which sorting algorithms are asked in interviews?
For coding interviews, different sorting algorithms can be asked. Heap sort, merge sort, quick sort are few examples of sorting algorithms that can be asked in the interviews.
What is the fastest sorting algorithm?
Quicksort is the fastest sorting algorithm.
Key Takeaways
The above mentioned 10 algorithms are standard algorithms that everyone should be well versed with before appearing for a coding interview. These algorithms will help you in impressing your interviewer in a coding interview as you will be able to optimise your code more efficiently than the students who are only able to tell the brute force approaches to a particular problem.