Top Standard Algorithms for a Coding Interview

Top Standard Algorithms for a Coding Interview
Top Standard Algorithms for a Coding Interview

Introduction 

A coding interview is a rigorous test of your data structures and algorithms abilities. Numerous programmers and mathematicians have made our lives easier by creating algorithms that can be used directly for approaching and optimizing a particular problem.

In this article, we will be looking at five standard algorithms that you should be well prepared with for acing your coding interview. After the explanation of every algorithm, a set of problems that you can practice has also been provided. 

The best way to learn is to make notes as you go. Therefore it is highly recommended to make notes from little details that are mentioned in the article on coding interview. In addition to this, you can also utilise peer to peer learning by gathering your friend group and solving the problems given in this article together. 


Algorithm 1: Kadane’s Algorithm 

Kadane’s Algorithm is used to solve the famous problem of finding the maximum sum subarray in a given array. 

Example:
Given array = [-1,2,-2,5,7,-3,1] and the maximum sum subarray for this will be 12 [2,-2,5,7].
The current sum gets updated as the array is traversed, if the current sum is less than zero then it is set to 0. The maxsum is updated by comparing the previous maxsum and the current sum after every iteration.

Algorithm:

Begin KadaneAlgo(arr, size)
	currentSum = 0 
	maxSum = INT_MIN
	for i=0 to size-1
		currentSum = currentSum + arr[i]
		maxSum = max(maxSum, currentSum)
		if currentSum < 0 
			currentSum - 0 
		End if
	End for
	return maxSum 
End

The time complexity for this algorithm is O(N) as the array is being traversed only once and the space complexity for this algorithm is O(1) as there is no extra space that has been used. 

Problems for Practice: 

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. 

Read more about Types Of Algorithm and Their Uses

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.

Image Source: CodeStudio

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

Image Source: CodeStudio

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. 

Programming is all about ensuring that your resources of time and space are utilised efficiently and algorithms help in the same. Learn algorithms in depth along with understanding their time complexities.

Happy Learning

By Pooja Gera

Exit mobile version