Top Algorithms Interview Questions

ALGORITHM F[n]
//Computes n! recursively
//Input: A nonnegative integer n
//Output: The value of n!
if n = 0 return 1
else return F[n − 1] * n

The time Complexity of this algorithm is O(n).

Brute force is an straightforward approach, usually based directly on the problem's statement and definitions of the concepts involved.
Brute-force algorithms are the processes that reach the perfect solution to a problem by analysing all the possible candidate solutions. Usually, a brute-force approach is simple to implement, and it will always find a solution to the computational problem, by considering iteratively all the possible solutions one by one.

merge sort algorithm repeatedly divides the data in half, sorts each half, and combines the sorted halves into a sorted whole.
The algorithm:
> Divide the list into two roughly equal halves.
> Sort the left half.
> Sort the right half.
> Merge the two sorted halves into one sorted list.
> Often implemented recursively.
> An example of a "divide and conquer" algorithm.
> Time Complexity O(nlogn)

Inplace merge-sort algorithm: It will sort the array without using extra space.

ALGORITHM merge(arr, start, mid, end):
start2 = mid + 1;

# If the direct merge is already sorted
if (arr[mid] <= arr[start2]):
return;

# Two pointers to maintain start
# of both arrays to merge
while (start <= mid and start2 <= end):

# If element 1 is in right place
if (arr[start] <= arr[start2]):
start += 1;
else:
value = arr[start2];
index = start2;

# Shift all the elements between element 1
# element 2, right by 1.
while (index != start):
arr[index] = arr[index - 1];
index -= 1;

arr[start] = value;

# Update all the pointers
start += 1;
mid += 1;
start2 += 1;

'''
* l is for left index and r is right index of
the sub-array of arr to be sorted
'''
ALGORITHM mergeSort(arr, l, r):
if (l < r):

# Same as (l + r) / 2, but avoids overflow
# for large l and r
m = l + (r - l) // 2;

# Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

merge(arr, l, m, r);

ALGORITHM QS[A[l..r]]
//Input: Subarray of array A[0..n − 1], defined by its left and right
// indices l and r
//Output: Subarray A[l..r] sorted in nondecreasing order
if l < r
s ←Partition[A[l..r]] //s is a split position
QS[A[l..s − 1]]
QS[A[s + 1..r]]

Partition (arr[low....high])
{
// pivot - Element at right most position
pivot = arr[high];
i = (low - 1); // Index of smaller element
for (j = low; j <= high-1; j++)
{
// If current element is smaller than the pivot, swap the element with pivot
if (arr[j] < pivot)
{
i++; // increment index of smaller element
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}

The time complexity of quick sort algorithm is O(n^2)