Algorithms - Interview Questions

Big O notation is used to describe the complexity, i.e. performance, of an algorithm in Computer Science. Big O notation describes the worst-case scenario of an algorithm. Analysis of algorithms includes time complexity (i.e. how long will the algorithm take to execute) as well as space complexity (i.e. how much disk space or memory will the algorithm take to execute). Big O notation can be used to describe both time complexity as well as space complexity of algorithms.

Big O notation is depicted as O(g(N)) where g(N) is the order of growth for N data elements. Common order of growth scenarios encountered frequently are - constant (1), linear (N), logarithmic (log N), linearithmic (N log N), quadratic (N^2), cubic (N^3) and exponential (2^N). These are depicted in Big O notation as O(1), O(N), O(log N), O(N log N), O(N^2), O(N^3), O(2^N) respectively

Algorithms that take contact time O(1) are those algorithms that will take the same time (or space) to execute regardless of the size of the input data set.

Example: Algorithm to find the first element of an array - will always take the same time to execute regardless of the size of the size of the input dataset.

return myArray[0];

Algorithms that take linear time O(N) are Algorithms whose time to execute will grow linearly in proportion to the size of the input dataset. These are algorithms that will loop through the input dataset once.

Example - Algorithm to find the max value in an array of integers.

int maxValue = intArray[0],

for(int i=1; i < intArray.length; i++){

if (a[i] > max) max = intArray[i];

}

Algorithms that take logarithmic time O(log N) to complete are Algorithms that will grow logarithmically to the size of the input dataset. These are usually divide in half algorithms that will iteratively split the input dataset into two.

Example - Binary Search.

// A recursive binary search function.

// returns location of x in an array if present, else returns -1

int binarySearch(int myArray[], int l, int r, int x) {

if (r >= l) {

int mid = l + (r - l)/2;

//element present at the middle

if (myArray[mid] == x) return mid;

//element smaller than mid

if (myArray[mid] > x) return binarySearch(myArray, l, mid-1, x);

//element larger tham mid

if (myArray[mid] < x) return binarySearch(myArray, mid+1, r, x);

}

//element not present in array

return -1;

}

Algorithms that take linearithmic time O(N log N) time to complete are Algorithms that are usually divide and conquer algorithms which will iteratively split the input dataset into two.

Example - Sorting Algorithm - Mergesort.

Algorithms that take quadratic time O(N^2) to complete are Algorithms that require double loops, i.e. loop within a loop.

Example: Algorithm to get all pairs of an array's elements.

for (int i=0; i < myArray.length; i++) {

for (int j=i+1; j < myArray.length; j++) {

System.out.println(myArray[i]+myArray[j]);

}

}

Algorithms that take cubic time O(N^3) to complete are Algorithms that require triple loops, i.e. loop -within a loop -within a loop.

Example: Algorithm to get all triples of an array's elements.

for (int i=0; i < myArray.length; i++) {

for (int j=i+1; j < myArray.length; j++) {

for (int k=j+1; k < myArray.length; k++) {

System.out.println(myArray[i]+myArray[j]+myArray[k]);

}

}

}

Recursion is an approach to solving algorithms by using a function that calls itself. This process in which a function calls itself is called recursion, and the function that calls itself is called a recursive function.

Factorial of a number n, written as 'n!', is the product of all positive numbers less than n.

Formula: n! = n*(n-1)*(n-2)*(n-3)*(n-4)...*1

Example of sequence: 4! = 4*3*2*1=24

Below function calculates the factorial for a number n using recursion.

public int factorial(int n) {

//base condition

if (n==0) {

return 1;

} else {

//recursion

return n*factorial(n-1);

}

}

Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones.

Formula: Fn = Fn-1 + Fn-2

Example of sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

function fibonacci(int n) {

//base condition

if (n <= 2) {

return 1;

}

//recursion

return fibonacci(n — 1) + fibonacci(n — 2);

}

In a Breadth First Search (BFS) traversal of a graph, you traverse all vertices at one level before moving on to the next level.

You start by traversing from any vertex say currentVertex. If adjacent vertices to the currentVertex are not yet visited then print their value. Then repeat the same for children of the currentVertex.

In a Depth First Search (DFS) traversal of a graph, you traverse the vertices depth wise rather than breadth wise. You start by traversing from any vertex say currentVertex - pick any one of it's adjacent vertex and keep traversing adjacent vertices until the farthest vertex is reached. Then you move back to the starting vertex and repeat the same for another adjecent vertex. You repeat this process until all the vertices are traversed.

Subscribe to our Newsletter

Offered By - **Andrei Neagoie**

Platform - **Udemy**

Rating - *** * * * ***

Students Enrolled - **100,000 +**