Algorithms - Interview Questions

Basics of Algorithms

### What is Big O notation?

FAQ

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

### Give example of an algorithm that takes constant time O(1) to complete.

FAQ

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];`

### Give example of an algorithm that takes linear time O(N) to complete.

FAQ

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];}`

### Give an example of an algorithm that takes logarithmic time O(log N) to complete.

FAQ

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 -1int 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;}`

### Give an example of an algorithm that takes linearithmic time O(N log N) to complete.

FAQ

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.

### Give an example of an algorithm that takes quadratic time O(N^2) to complete.

FAQ

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]); }}`

### Give an example of an algorithm that takes cubic time O(N^3) to complete.

FAQ

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]);  } }}`

### Give an example of an algorithm that takes exponential time O(2^N) to complete.

FAQ

Recursion Algorithms

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.

### Write a function in Java that returns the factorial of a number n?

FAQ

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); }}`

### Write a function in Java that returns the factorial of a number n?

FAQ

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);}`

Graph Algorithms

### How do you traverse a graph using Breadth First Search (BFS)?

FAQ

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.

### How do you traverse a graph using Depth First Search (DFS)?

FAQ

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

TOP COURSES
Master the Coding Interview: Data Structures + Algorithms

Offered By - Andrei Neagoie
Platform - Udemy
Rating - * * * * *
Students Enrolled - 100,000 +

Algorithms

Offered By - Princeton University
Platform - Coursera
Rating - * * * * *
Students Enrolled - 850,000 +

RECOMMENDED RESOURCES
Behaviorial Interview
Top resource to prepare for behaviorial and situational interview questions.