Table of Contents

## 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:

- Longest mountain subarray
- Find all triplets with zero-sum
- Container with most water
- Sum of two elements equals the third
- Triplets with a given sum
- Shortest substring with all characters
- Valid string
- Remove consecutive duplicates from a string
- Minimum operations needed to convert to the given string
- Is subsequence

**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:

- Smallest subarray with K distinct elements
- Three pointer
- Longest switching subarray
- Equilibrium indices of a sequence
- Count distinct elements in every k size window
- Check duplicate
- Maximum of all subarrays of size K
- Longest substring without repeating characters
- Fruits and baskets
- Anagram substring search

**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:

- Add first and second half
- Delete middle node
- Add first and second reversed half
- Delete kth node from end in the list
- Detect and remove cycle

**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)

- Sudoku
- Reach the destination
- Paths in a maze
- The N Queens puzzle
- Letter combinations of a phone number
- Tug of war
- K subsets with equal sum
- Binary strings with no consecutive 1s
- Reverse stack using recursion
- Minimum distance points
- Print permutations – string
- Print parentheses
- IP address
- Subsequences of string
- Combination sum

**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:

- Maximum sum of two non overlapping subarrays of a given size
- Minimum jumps
- Minimum removals
- Minimum steps to reach target by a knight
- Minimum cost of reducing array by merging any adjacent elements repetitively
- Wildcard pattern matching
- Scramble string
- Regular expression match
- LCS of 3 strings
- Distinct subsequences
- Choose students
- Best time to buy and sell stock
- Matrix chain multiplication
- Buy and sell stock – III
- Coin game
- Optimal BST
- Number of balanced binary trees
- Goku and dragon balls
- Partition to k equal sum subsets
- Partition equal subset sum
- Palindrome partitioning II
- Maximum length of chain
- King and his golden rod
- Ways to make coin change
- Ways to arrange balls
- Count number of ways to cover a distance
- Count ways to reach the nth stairs
- Count palindromic subsequences
- Longest palindromic substring
- Edit distance
- Rod cutting problem
- Longest increasing subsequence
- 0-1 Knapsack
- Loot houses
- Colorful knapsack
- Word wrap
- Optimal strategy for a game
- Cut logs
- Interleaving two strings
- Common digit longest subsequence
- Tiling problem
- Gold mine problem
- Maze with N doors and 1 key

**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:

- Placement of students
- Is it a tree?
- Colour the graph
- Largest island
- Fire in the cells
- Count nodes within k-distance

## 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.

**By Pooja Gera**

## Leave a Reply