Top Searching and Sorting Algorithms For The Coding Interview

Top Searching and Sorting Algorithms For The Coding Interview
Top Searching and Sorting Algorithms For The Coding Interview

Introduction 

The coding interview process is a tedious process and without the right guidance, it is a hard road. 

But worry not! 

Searching and sorting are the most basic algorithms that one should be aware of before appearing for a coding interview. The article is structured in a manner where you understand the intuition behind the algorithm, study the algorithm, and understand its time and space complexities.


Finally, for your practice, plenty of questions are provided in the end which you can practice on the best platform for interview preparation – CodeStudio

Let’s go!

Searching and Sorting Algorithms: Binary Search 

1. Introduction

Binary Search is an algorithm used to perform the search operation on a given sorted array in an optimized manner. It utilizes three-pointers – lower, middle, and higher which are moved around the array based on certain conditions.

If the item to be searched in the array is less than the middle, then higher is updated to take the middle’s place and the middle is updated to be the middle of lower and higher. Similarly, if the item to be searched in the array is greater than the middle, then the lower is updated to take the middle’s place, and the middle is updated to be the middle of the lower and higher. 

The binary search algorithm is a crucial algorithm for your next coding interview as it offers a more systematic and optimised approach towards finding an element in a given list of elements.

Image Source: CodeStudio 

blog banner 1

2. Algorithm

binarySearch(arr, target)
lower = 0
higher = size(arr) - 1
while (lower <= higher) do
middle = (lower + higher)/2
if (target==arr[middle]) then
return true
else if (target < arr[middle]) then 
high = middle - 1
else low = middle + 1
end while
return false
end 

3. Problems for Practice

Codestudio is an interesting and vast platform to prepare for your next coding interview. Given below are 21 problems based on the binary search algorithm that you can practice. Codestudio also offers the average time that should be taken to solve a particular problem. Make sure you are able to complete each problem within time. 

P.S. Don’t forget to make notes – it will help you tremendously in your next coding interview.

Search in a rotated sorted arraySearch in a 2D matrixSearch in a 2D matrix IIFirst and last position of an element in a sorted arrayOccurence of x in a sorted array
Allocate booksRecycling pensSquare root of an integerAggressive cowsPainter’s partition problem
Chess tournamentNinja and candiesMinimum time to solve the problemsSquare submatrix with sum less than or equal to kSmart intervals
Distribute n candies among k peopleSearch in infinite sorted array of 0 and 1Find pair sum in rotated sorted arrayFind peak elementFind missing number in AP
Find best insertion position in array 

Searching and Sorting Algorithms: Selection Sort

1. Introduction

As the name suggests, the selection sorting algorithm helps in sorting the array with the intuition of selecting the elements and placing them at their right position. The selection sorting algorithm involves traversing through the entire array and picking the smallest element first.

This is then swapped with the element on the 0th index of the array. The array is traversed once again to find the second smallest element which is then swapped with the element on the 1st index of the array. This goes on till the entire array is sorted.  

Example array to be sorted -> [14,33,27,10,35,19,42,44]

Image Source: CodeStudio

2. Algorithm 

Begin selectionSort(arr, size_of_arr)
for i=0 to i = size_of_arr-1:
smallest_idx = i 
for j = i+1 to j = size_of_arr-1:
if(arr[j]<arr[smallest_idx]) smallest_idx = j
end for
smallest_ele = arr[smallest_idx]
arr[smallest_idx] = arr[i]
arr[i] = smallest_ele
end for 
End

Time Complexity - O(N^2)
Space Complexity - O(1)

Searching and Sorting Algorithms: Bubble Sort

1. Introduction

Bubble Sort is another sorting algorithm that involves swapping adjacent elements after comparing them. It is like forming a bubble around a pair of elements, comparing them, and then arranging them in ascending order. This is the easiest algorithm to learn and apply. 

Example array to sort -> [50,25,5,20,10]

Image Source: CodeStudio

2. Algorithm 

Begin bubbleSort(arr, size_of_arr)
i := size_of_arr - 1
while (i>=1) do:
j:=0
while(j<i) do:
if(arr[j] <arr[j+1])
temp_ele:=arr[j]
arr[j]:=arr[j+1]
arr[j+1]:=temp
end if
j++
end while
i++
end while
end 
Time Complexity - O(n^2)
Space Complexity - O(1)

Searching and Sorting Algorithms: Insertion Sort

1. Introduction

The insertion sort as the name suggests is a sorting technique which is used to insert the elements at the right position. You pick an element and find its correct place in the array then you move on to the next element and do the same till there are no elements left. 

Example of array to be sorted = [9,4,5,1,3]

Image Source: CodeStudio

2. Algorithm

Begin insertionSort( arr)
for j = 2 to arr.size
key_ele = arr[j]
i:=j-1
while (i>0 and arr[i] >key_ele) 
arr[i+1] = arr[i]
i:i-1
end while
arr[i+1] = key_ele
end for
End
Time Complexity - O(N^2)
Space Complexity - O(1) 

Searching and Sorting Algorithms: Counting Sort

1. Introduction

Counting sort as the name suggests is a sorting technique that counts the frequency of every unique element in the array and this frequency is used in mapping to an index of a temporary array taken for sorting.

2. Algorithm 

Begin countingSort(arr, k)
n = arr.size()
create array B[n] and C[k+1]
for i=0 to i=k
C[i]=0
end For
for i=1 to i = n 
C[A[i]] ++
end for
for i =1 to i = k 
C[i] = C[i] + C[i-1]
end for
for i=n to i = 1 
B[C[A[i]]] = A[i]
C[A[i]}--
end for
End

Time Complexity = O(N+K)
Space Complexity = O(N+K)

Searching and Sorting Algorithms: Heap Sort 

1. Introduction

Heapsort is another simple, easy, and effective sorting algorithm that uses heaps and priority queues. This is an algorithm that can be performed in-place. Example array to be sorted -> [12,6,10,5,1,9]

Image Source: CodeStudio

2. Algorithm 

Begin sort(arr)
buildHeap(arr)
for i = n-1 to i = 1:
swap(arr[0],arr[i])
heapify(arr,0,i)
end for
End

Begin buildHeap(arrr)
for i = |_ n/2 _| to i = 0: 
heapify(arr,i,n)
end for
End

Begin heapify(arr, index, max)
left = 2*index + 1
right = 2*index + 2
if( left<max and arr[left] > arr[index) then 
largest_idx = left 
else largest_idx = index
if(right<max and arr[right]>arr[largest_idx]) then 
largest_idx = right 
if(largest_idx != index) then 
swap(A[i], A[largest_idx])
heapify(arr, largest_idx, max)
End

Time Complexity = O(nlogn) 
Space Complexity = O(1) 

Practice Problems on Sorting Algorithms

Given below are practice problems specially prepared by team Coding Ninjas for you to ace in your coding interviews. All problems are available in 

Sort by kth bitSort an array in wave formSort an array according to the count of set bits Relative sorting Sort a half-sorted array
Binary array sortingMinimum number of swaps required to sort an arrayQuicksort on linked listCount inversionInsertion sort in linked list 
Sort linked list Sort linked list of 0’s, 1’s and 2’s Build heapConvert min-heap to max-heapConvert BST to min-heap
Kth largest element in the unsorted arrayKth largest numberKth largest sum contiguous subarrayMinimum k productKth smallest element
K most frequent wordsMinimum and maximum cost to buy N candiesGary and multiplicationMax gameLast stone weight
Fourth largest element in the arrayString transformationRunning medianMinimum character deletionSorted matrix
Connect n ropes with minimum cost 

Frequently Asked Questions

What algorithms are you able to implement during the interview using any programming language?

Every algorithm can be implemented during the coding interview using any programming language. Algorithms are not language-specific.

How do you ace the coding interview?

To ace the coding interview, you need to ensure you are well versed with the basic concepts and have practiced enough. You can take up the newly launched guided paths course on CodeStudio which will be a triumph card for you to ace your next coding interview.

Which sorting algorithms are asked in interviews?

Sorting algorithms like the bubble sort, selection sort, insertion sort, counting sort, merge sort and heap sort can be asked in your coding and technical interview.

What are the three types of sorting?

The three types of sorting can include bubble sort, insertion sort and selection sort.

What is the fastest sorting algorithm?

Quicksort is the fastest sorting algorithm.

Key Takeaways

Now that you have read the entire blog, you are aware that you can use this blog as your revision notes or a practice handbook during the Coding Interviews.

Make sure you have understood the intuition behind the algorithm and you know how the algorithm works. After that practice, this can’t be stressed enough, practice as much as you can and there will be nothing that can stop you from acing your next coding interview!

Stay tuned for more algorithms for Coding interviews and happy learning! 

By Pooja Gera