Ace the top 15 Java algorithm questions for coding interviews
Tags: java, algorithms, career, programming
Published: 2022-11-18 22:51:57

Algorithm-based questions are a staple of any modern coding interview, as they demonstrate your problem-solving and critical thinking skills. To make sure you don’t get caught off guard in your next Java interview, we’ve put together **15 of the most common algorithm coding questions** used by most tech companies and recruiters across the industry.

These algorithm coding questions vary in difficulty, so if you can’t figure out one, don’t be ashamed to move on to the next and return later. With enough practice, you’ll shortly be able to crack any interview question thrown at you. Each question is followed by a detailed explanation to help you get prepped for the big interviews ahead. 

**Today, we'll be covering questions on:**

* [Measuring Complexity: Big O Notation](#mc)
* [Sorting and Searching: Quicksort, Binary Search, and more](#ss)
* [Dynamic Programing: Memoization and Tabulation](#dp)
* [Greedy Algorithms: Maximization](#ga)
* [Divide and Conquer](#dc)
* [Graph Algorithms](#ga2)

<a name="mc"></a>

## Measuring Complexity: Big O Notation

Using [Big O notation](https://www.educative.io/blog/a-big-o-primer-for-beginning-devs?eid=5082902844932096) is a foundational skill that will be checked by Java interviewers. Before we jump into some more intensive examples, we'll first go through some questions that test your knowledge and understanding of Big O notation.

As a refresher, Big O is used to classify algorithms based on how their run-time and space requirements grow with input size.

### 1: Big O of a Nested Loop with Addition

**Problem Statement:**

Compute the Big O complexity of the code snippet given below.

```Java
class NestedLoop {
  public static void main(String[] args) {
    int n = 10;
    int sum = 0;
    double pie = 3.14;
    
    for (int var = 1; var < n; var = var + 3) {
      System.out.println("Pie: " + pie);
      for (int j = 1; j < n; j = j + 2) {
        sum++;
      }
      System.out.println("Sum = " + sum);
    }
  }
}
```
Solution: O(n<sup>2</sup>)

**Solution Breakdown:**

The first for loop on line 7 can be broken down into 3 parts:

* Initialization
* Comparison
* Incrementation


Since the initialization `(int var = 0)` only happens once in the entire program, it takes one unit of time. The comparison (`var < n`) gets executed *(n/3+ 1)* times and the increment runs *n/3* ​times.

Similarly, (`int j = 0`) runs *n/3* times, the comparison (`j < n`) runs *n/3* * *(n/2 + 1)*, and the increment (`j = j + 2`) gets executed *n/2* times for each iteration of the outer loop, so it runs:

![Big O](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/njv1r64j0tet6l7z2fnt.png)

Below is the line-by-line calculation of time complexity:

![Big O](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/10df0ihk69x0f09r2xa5.png)

Finally, we add all lines' time complexity, drop the leading constants and lower order terms, and find our Big O Complexity.

<a name="ss"></a>

## Sorting and Searching: Quicksort, Binary Search, and more

Almost every interviewer will ask a question that calls for at least one type of searching or sorting, if not more. To help you prepare for these questions, we've included the following overview section to build foundational search/sort algorithm proficiency.


> **Note:** It's unlikely you'll be prompted to use a certain algorithm in an interview. Instead, you must learn to recognize which algorithm to use based on keywords in the problem statement.
>
> As you practice, try to pinpoint which part of the problem statement would lead you to use the indicated algorithm.

### 2: Quicksort

**Problem Statement:**

Given an unsorted array of numbers, find `K`th smallest number in it.

Please note that it is the `K`th smallest number in the sorted order, not the `K`th distinct element.

```java
import java.util.*;

class KthSmallestNumber {

  public static int findKthSmallestNumber(int[] nums, int k) {
    // TODO: Write your code here
    return -1;
  }

  public static void main(String[] args) {
    int result = KthSmallestNumber.findKthSmallestNumber(new int[] { 1, 5, 12, 2, 11, 5 }, 3);
    System.out.println("Kth smallest number is: " + result);

    // since there are two 5s in the input array, our 3rd and 4th smallest numbers should be a '5'
    result = KthSmallestNumber.findKthSmallestNumber(new int[] { 1, 5, 12, 2, 11, 5 }, 4);
    System.out.println("Kth smallest number is: " + result);

    result = KthSmallestNumber.findKthSmallestNumber(new int[] { 5, 12, 11, -1, 12 }, 3);
    System.out.println("Kth smallest number is: " + result);
  }
}
```

**Solution:**

```java
import java.util.*;

class KthSmallestNumber {

  public static int findKthSmallestNumber(int[] nums, int k) {
    return findKthSmallestNumberRec(nums, k, 0, nums.length - 1);
  }

  public static int findKthSmallestNumberRec(int[] nums, int k, int start, int end) {
    int p = partition(nums, start, end);

    if (p == k - 1)
      return nums[p];

    if (p > k - 1) // search lower part
      return findKthSmallestNumberRec(nums, k, start, p - 1);

    // search higher part
    return findKthSmallestNumberRec(nums, k, p + 1, end);
  }

  private static int partition(int[] nums, int low, int high) {
    if (low == high)
      return low;

    int pivot = nums[high];
    for (int i = low; i < high; i++) {
      // all elements less than 'pivot' will be before the index 'low'
      if (nums[i] < pivot)
        swap(nums, low++, i);
    }
    // put the pivot in its correct place
    swap(nums, low, high);
    return low;
  }

  private static void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }

  public static void main(String[] args) {
    int result = KthSmallestNumber.findKthSmallestNumber(new int[] { 1, 5, 12, 2, 11, 5 }, 3);
    System.out.println("Kth smallest number is: " + result);

    // since there are two 5s in the input array, our 3rd and 4th smallest numbers should be a '5'
    result = KthSmallestNumber.findKthSmallestNumber(new int[] { 1, 5, 12, 2, 11, 5 }, 4);
    System.out.println("Kth smallest number is: " + result);

    result = KthSmallestNumber.findKthSmallestNumber(new int[] { 5, 12, 11, -1, 12 }, 3);
    System.out.println("Kth smallest number is: " + result);
  }
} 

```

**Solution Breakdown:**

*Time Complexity:* average *O(N)* or worst case O(n<sup>2</sup>)

We use Quicksort's partitioning scheme to find the Kth smallest number. We recursively partition the input array, and if, after partitioning, our pivot is at the `K-1` index, we have found our required number. If not, we choose one of the following options:

* If the pivot’s position is larger than K-1, we recursively partition the array on numbers lower than the pivot.
* If the pivot’s position is smaller than K-1, we recursively partition the array on numbers greater than the pivot.

### 3: Binary Search

**Problem Statement:**

We are given a 2D array where all elements in any individual row or column are sorted. In such a matrix, we have to search or find the position of a given key.

```java
class searchMatrix{
  public static IntPair
  search_in_matrix(int matrix[][], int value) {
    //TODO: Write - Your - Code
    return new IntPair(-1, -1);
  }
}  
```

**Solution:**

```java
class searchMatrix{
  public static IntPair
  search_in_matrix(int matrix[][], int value) {
    int M = matrix.length; //rows
    int N = matrix[0].length; // columns

    // Let's start searching from top right.
    // Alternatively, searching from bottom left
    // i.e. matrix[M-1][0] can also work.

    int i = 0, j = N-1;

    while (i < M && j >= 0) {
      if (matrix[i][j] == value) {
        return new IntPair(i, j);
      }
      else if (value < matrix[i][j]) {
        // search left
        --j;
      }
      else {
        // search down.
        ++i;
      }
    }  

    return new IntPair(-1, -1);
  }
  public static void verify_search(int [][] matrix) {
    for (int i = 0; i < matrix.length; ++i) {
      for (int j = 0; j < matrix[0].length; ++j) {
        System.out.println("Verifying at " + i + ", " + j);
        IntPair val_loc = search_in_matrix(matrix, matrix[i][j]);
        assert(val_loc.first == i);
        assert(val_loc.second == j);
      }
    }
  }

  public static void main(String[] args) {
    int [] [] matrix = new int [] [] {
      {1, 5, 45, 80, 81},
      {6, 7, 48, 82, 83},
      {20, 22, 49, 85, 86},
      {21, 23, 50, 90, 92}
    };

    verify_search(matrix);
  }
}  


```

**Solution Breakdown:**

*Time Complexity:* *O(m + n)*

We start from the upper right corner of the matrix and compare its value with the key. If they are equal, we have found the position of the key. 

If the key is smaller than the current element, we move to the left one position. If the key is larger than the current element, we move right one position.

As the matrix is sorted, moving left always results in lower values than the current while moving down always results in higher values.

We continue this process until either we find the element or go out of the boundary of the matrix (which indicates that the key does not exist). 

### 4. Merge Sort

**Problem Statement:**

Given the head pointer of a linked sort, sort the linked list in ascending order using merge sort and return the new head pointer of the sorted linked list.

```java
class MergeSort{
  public static LinkedListNode mergeSort(LinkedListNode head) {
    //TODO: Write - Your - Code
    return head;
  }
}
```

**Solution:**

```java
class MergeSort{
  // this method splits linked list in half by iterating over whole list
  // then returns head pointers of first and second halves of linked lists in firstSecond
  // The head of 1st half is just the head node of the linked list
  public static void splitInHalf(LinkedListNode head,
      Pair<LinkedListNode,LinkedListNode> firstSecond) {

    if (head == null) {
      return;
    }

    // Edge case: only one elements
    if (head.next == null) {
    
      firstSecond.first = head;
      firstSecond.second = null;
    }
    else {

      // We'll use the technique of moving two pointers:
      // 'fast' and 'slow'. 'fast' will move two steps in each 
      // iteration where 'slow' will be pointing to middle element
      // at the end of loop.

      LinkedListNode slow, fast;
      slow = head;
      fast = head.next;

      while (fast != null) {

        fast = fast.next;
  
        if (fast != null) {

          fast = fast.next;
          slow = slow.next;
        }
      }

      firstSecond.first = head;
      firstSecond.second = slow.next;

      // Terminate first linked list.
      slow.next = null;
    }
  }

  public static LinkedListNode mergreSortedLists(LinkedListNode first,
  LinkedListNode second) {
  
    if (first == null) {
      return second;
    }
    else if (second == null) {
      return first;
    }
  
    LinkedListNode newHead;
    if (first.data <= second.data) {
      newHead = first;
      first = first.next;
    }
    else {
      newHead = second;
      second = second.next;
    }

   LinkedListNode newCurrent = newHead;
   while (first != null && second != null) {
     LinkedListNode temp = null;
     if (first.data <= second.data) {
       temp = first;
       first = first.next;
     } else {
       temp = second;
       second = second.next;
     }

     newCurrent.next = temp;
     newCurrent = temp;
   }

   if (first != null) {
     newCurrent.next = first;
   } else if (second != null) {
     newCurrent.next = second;
   }

    return newHead;
  }

  public static LinkedListNode mergeSort(LinkedListNode head) {

    // No need to sort a single element.
    if (head == null || head.next == null) {
      return head;
    }

    Pair<LinkedListNode,LinkedListNode> firstSecond = 
      new Pair<LinkedListNode,LinkedListNode>(null,null);
  
    // Splits the list in half, sorts the sublists
    // and then merge the sorted lists for printing.
    splitInHalf(head, firstSecond);

    firstSecond.first = mergeSort(firstSecond.first);
    firstSecond.second = mergeSort(firstSecond.second);

    return mergreSortedLists(firstSecond.first, firstSecond.second);
  }

  public static void main(String[] args) {

    int[] v1 = {29, 23, 82, 11, 4, 3, 21};
    LinkedListNode listHead1 = LinkedList.createLinkedList(v1);
  
    System.out.print("Unsorted list: ");
    LinkedList.display(listHead1);
        
    listHead1 = mergeSort(listHead1);
    System.out.print("Sorted list: ");
    LinkedList.display(listHead1);
  }
}

```

**Solution Breakdown:**

*Time Complexity:*  *O(nlogn)*

In the dividing step, we split our input linked list into two halves and keep doing so until there is a linked list of size 1 or 0. Linked lists of sizes 1 and 0 are always sorted. In the combining step, we merge sorted lists and keep doing so until we have a completely sorted list.

At each step, we divide our problem into two sub-problems. The size of each sub-problem is *n/2*, and the total cost of combining steps (merging sorted lists) is *n*.

### 5. Insertion Sort

**Problem Statement:**

Given the head pointer of a linked list, sort the linked list in ascending order using insertion sort. Return the new head pointer of the sorted linked list.

```java
class InsertionSort{
   public static LinkedListNode insertionSort(LinkedListNode head) {
      //TODO: Write - Your - Code
      return head;
    }
}  
```

**Solution:**

```java
class InsertionSort{
  public static LinkedListNode sortedInsert(LinkedListNode head, LinkedListNode node) {

    if (node == null) {
      return head;
    }

    if (head == null || node.data <= head.data) {
      node.next = head;
      return node;
    }

    LinkedListNode curr = head;

    while (curr.next != null && (curr.next.data < node.data)) {

      curr = curr.next;
    }

    node.next = curr.next;
    curr.next = node;

    return head;
  }

  public static LinkedListNode insertionSort(LinkedListNode head) {

    LinkedListNode sorted = null;
    LinkedListNode curr = head;

    while (curr != null) {

      LinkedListNode temp = curr.next;

      sorted = sortedInsert(sorted, curr);

      curr = temp;
    }

    return sorted;
  }

  public static void main(String[] args) {

    int[] list = {29, 23, 82, 11};
    int[] listExpected = {11, 23, 29, 82};
    LinkedListNode listHead = LinkedList.createLinkedList(list);
    LinkedListNode listHeadExpected = LinkedList.createLinkedList(listExpected);
    
    System.out.print("Original: ");
    LinkedList.display(listHead);
    
    listHead = insertionSort(listHead);
    System.out.print("After sorting: ");
    LinkedList.display(listHead);
  }
}  

```

**Solution Breakdown:**

*Time Complexity:* O(n<sup>2</sup>)

While the original list is not empty:

* Remove an element (say 'X') from the original list.

* Insert 'X' at the correct sorted position in the sorted list.

To insert a node into the sorted linked list, we may need to scan the entire sorted list depending on the node being inserted.


### 6. HashMap

**Problem Statement:**

Using a HashMap, implement a function that takes an array `arr`, a number `value`, and the size of the array as an input and returns two numbers that add up to `value`.

```java
class CheckSum {
 public static int[] findSum(int[] arr, int n) {
  int[] result = new int[2];
  // write your code here
  return result; // return the elements in the array whose sum is equal to the value passed as parameter 
 }
}
```

**Solution:**

```java
class CheckSum {
 public static int[] findSum(int[] arr, int n) {
  int[] result = new int[2];
  HashMap < Integer, Boolean > hmap = new HashMap < Integer, Boolean > (); // Create a hashmap

  for (int i = 0; i < arr.length; i++) {
   hmap.put(n - arr[i], true); // Store value - arr[i] for all elements in arr
  }
  for (int i = 0; i < arr.length; i++) {
   if (hmap.containsKey(arr[i])) // If a value from arr is present in hmap
   {
    result[0] = arr[i];
    result[1] = n - arr[i];
    return result;
   }
  }
  return result;
 }

 public static void main(String args[]) {

  int n = 9;
  int[] arr1 = {2, 4, 5, 7, 8};
   int[] arr2 = findSum(arr1, n);
  int num1 = arr2[0];
  int num2 = arr2[1];

  if ((num1 + num2) != n)
   System.out.println("Results not found!");
  else
   System.out.println("Sum of " + n + " found: " + num1 + " and " + num2);
 }
}

```

**Solution Breakdown:**

*Time Complexity:* *O(n)*

For all the elements in the `arr` array, we store the difference `n - arr[i]` in `hmap`.

Then with another iteration over `arr`, we check if any element of `arr` exists in the `hmap` , which means the difference of `n` and the number found (`n - arr[i]`) are also present.

Therefore, an array of size 2 called `result` is created to store the pair that sums up to `n`. If `hmap` contains an array element, `result[]` is updated, or else it is returned containing the default value.

### 7. HashSet

**Problem Statement:**

Implement an `isSubset()` function to take two arrays as input and check whether an array is a subset of another given array.

```java
class CheckSubset {
  public static boolean isSubset(int[] arr1, int[] arr2) {
    // write your code here	
    return false;
  }
}
```

**Solution:**

```java
class CheckSubset {
  static boolean isSubset(int arr1[], int arr2[]) {
    HashSet<Integer> hset= new HashSet<>(); 
    // hset stores all the values of arr1 
    for(int i = 0; i < arr1.length; i++) { 
      if(!hset.contains(arr1[i])) 
        hset.add(arr1[i]); 
    } 

    // loop to check if all elements of arr2 also 
    // lies in arr1 
    for(int i = 0; i < arr2.length; i++) { 
      if(!hset.contains(arr2[i])) 
        return false; 
    } 
    return true; 
  }
  
  public static void main(String args[]) {
    
    int[] arr1 = {9, 4, 7, 1, -2, 6, 5};
    int[] arr2 = {7, 1, -2};
    int[] arr3 = {10, 12};

    System.out.println(isSubset(arr1, arr2));
    System.out.println(isSubset(arr1, arr3));
  }
}

```

**Solution Breakdown:**

*Time Complexity:* *O(m+n)*

First, we iterate over `arr2` and `arr3` to see whether their elements can be found in `arr1`.

At the back end, the values are checked against their hashed indices in `arr1`.

<a name="dp"></a>

## Dynamic Programming: Memoization and Tabulation

Dynamic Programming is a central algorithm technique for the modern developer, as it focuses on breaking a problem into simpler sub-problems to achieve optimization. The more optimal the solution to sub-problems, the more optimal the overall solution is.

This is the foundation of [recursive](https://www.educative.io/blog/recursion?eid=5082902844932096) problem-solving and, therefore, will be asked by any good interviewer.

Dynamic Programming questions can either be solved from a Top-Down approach or a Bottom-Up approach, using either **Memoization** or **Tabulation**, respectively. Interviewers may ask for one or may leave it to your decision. 

Below we'll see an example of each, so you're prepared for any alternative.

### 8. The Knapsack Problem: 

**Problem Statement:**

Imagine that you’re an adventurer with a knapsack looking over a dragon's hoard.

Given two integer arrays that represent the weights and profits of `N` items, implement a function `knapSack()` that finds a subset of these items that will give us the maximum profit without their cumulative weight exceeding a given number `capacity`. Each item may only be selected once, which means when we get to it we can either skip it or put it in the knapsack.

Use the top-down approach with memoization.

```java
class KnapsackProblem
{ 
    static int Knapsack(int profits[], int profitsLength, int weights[], int weightsLength, int capacity) 
    {
        // write your code here
        return -1;
    }
};
```

**Solution:**

```java
class KnapsackProblem
{ 
  public static int knapsackRecursive(int [][] lookupTable, int profits[], int profitsLength, int weights[], int weightsLength, int capacity, int currentIndex) {

    // base checks  
    if (capacity <= 0 || currentIndex >= profitsLength || currentIndex < 0 || weightsLength != profitsLength)
      return 0;

    // if we have already solved the problem, return the result from the table  
    if (lookupTable[currentIndex][capacity] != 0)
      return lookupTable[currentIndex][capacity];

    // recursive call after choosing the element at the currentIndex
    // if the weight of the element at currentIndex exceeds the capacity, we shouldn't process this
    int profit1 = 0;
    if (weights[currentIndex] <= capacity)
      profit1 = profits[currentIndex] + knapsackRecursive(lookupTable, profits, profitsLength, weights, weightsLength,
        capacity - weights[currentIndex], currentIndex + 1);

    // recursive call after excluding the element at the currentIndex
    int profit2 = knapsackRecursive(lookupTable, profits, profitsLength, weights, weightsLength, capacity, currentIndex + 1);

    lookupTable[currentIndex][capacity] = Math.max(profit1, profit2);
    return lookupTable[currentIndex][capacity];
  }

  public static int knapSack(int profits[], int profitsLength, int weights[], int weightsLength, int capacity) 
  {
    int lookupTable[][] = new int [profitsLength][];

    for (int i = 0; i < profitsLength; i++) {
      lookupTable[i] = new int[capacity + 1];
      for (int j = 0; j < capacity + 1; j++)
        lookupTable[i][j] = 0;
    }
    return knapsackRecursive(lookupTable, profits, profitsLength, weights, weightsLength, capacity, 0);
  }

  public static void main(String args[]) 
  {
    int profits[] = {1, 6, 10, 16}; // The values of the jewelry
    int weights[] = {1, 2, 3, 5}; // The weight of each
    System.out.println("Total knapsack profit ---> " + knapSack(profits, 4, weights, 4,  7));
    System.out.println("Total knapsack profit ---> " + knapSack(profits, 4, weights, 4, 6));
  }
};

```

**Solution Breakdown:**

*Time Complexity:* *O(N*C)*

The function `knapSack` makes a `lookupTable` within the function that stores the maximum value that can be attained with maximum capacity (lines 29-35). This function calls the helper function `knapsackRecursive` (line 36). It returns the maximum value that can be attained using only the first `i` items, i.e., items at the `currentIndex` while keeping their total weight no more than weights. 

We have two varying values (`capacity` and `currentIndex`), so we can use a two-dimensional array to store the results of all the solved subproblems in our recursive function `knapsackRecursive`.

We need to store results for every subarray, i.e., for every possible index and for every possible capacity. If the `lookupTable[currentIndex][capacity]` is already computed before (line 10), this value is immediately returned (line 11).

Otherwise, we call the function recursively:

* With the item, saving the result in `profit1` (line 17).

* Without the item, saving the result in the variable, `profit2` (line 21).

Out of the two, we return the result that is greater (as done on lines 23-24).

### 9. Staircase Problem

**Problem Statement:**

A child is running up a staircase with `n` steps and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a function to count the number of possible ways that the child can run up the stairs.

Try to solve this one using a Bottom-Up approach with Tabulation.

```java
class StairCaseProblem
{
    public static int countWays(int n) 
    {
        // write your code here
        return -1;
    }
};
```

**Solution:**

```java
class StairCaseProblem
{ 
  public static int countWays(int n) 
  { 
    int[] lookupTable = new int[n+1]; // Initialize lookup table
    lookupTable[0] = 1; // Setting the first three values
    lookupTable[1] = 1;
    lookupTable[2] = 2;
    
    for (int i = 3; i <= n; i++) 
        lookupTable[i] = lookupTable[i-1] + lookupTable[i-2] + lookupTable[i-3]; // Fill up the table by summing up previous two values
    
    return lookupTable[n]; 
  } 
  public static void main(String args[]) 
  {
    System.out.println(countWays(3));
  }
};

```

**Solution Breakdown:**

*Time Complexity:* *O(n)*

We know that:

* The total number of ways to reach the zero-step is 1 (line 6).

* The total number of ways to reach the first step is 1 (line 7).

* The total number of ways to reach the second step is 2 (line 8).

Hence, we fill up the `lookupTable` with these three values (lines 6-8).

We know that the total number of ways to reach any `n`th stair is by taking 1, 2, or 3 steps. Hence, the total number of ways to reach an `n`th stair would be equal to the sum of the total number of ways to reach `[n-1]`th step, number of ways to reach `[n-2]`th step, and the number of ways to reach the `[n-3]`th step.

So, the rest of the values of the `lookupTable` are filled by calculating the total number of ways to reach an nth step by summing the ways to reach the previous three steps (line 11).

The required value is then returned from the `lookupTable` (line 13).

<a name="ga"></a>

## Greedy Algorithms: Local Maximization

Greedy is an algorithmic technique where the solution is built one piece at a time, prioritizing immediate, obvious benefits at each choice. In other words, it seeks to maximize profit (the positive) and minimizes the cost (the negative).

This technique works on the idea that the locally optimal choice will contribute to the globally optimal solution. Below we'll see a few interview questions to help you use this technique when required.

### 10: Change Machine Problem

**Problem Statement:**

You have to make such a change machine that only returns the change in the form of coins.

You are supplied with an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (1 cent). The user will enter any amount. For each amount, you have to return the minimum number of coins possible!

```java
class ChangeMachine 
{
  // a public collection of available coins
  public static int [] coins = {25, 10, 5, 1}; 

  public static  ArrayList<Integer> getMinCoins(int amount)  // function to recieve change in the form of coins
  {
    ArrayList<Integer> change = new ArrayList<Integer>();
    // your awesome code goes here
    return change;
  }
}
```

**Solution:**

```java
class ChangeMachine {
 
 public static int[] coins = {25, 10, 5, 1}; // a public collection of available coins

 // function to recieve change in the form of coins
 public static ArrayList < Integer > getMinCoins(int amount) {
  
  // an array list to store all the coins
  ArrayList < Integer > change = new ArrayList < Integer > ();
  for (int i = 0; i < coins.length; i++) // traverse through all available coins
  {
   while (amount >= coins[i]) // keep checking if the amount is greater than the max coin
   {
    amount -= coins[i]; // subtract the maximum coin selected from the total amount in every iteration
    change.add(coins[i]); // add the coin to the list of 'change'
   }
  }
  return change; // return the list containing all the change
 }

    public static void main(String args[]) 
    {
        // Play around with this amount to see how many coins you get!
        int amount = 1;
        System.out.println(amount + " --> " + getMinCoins(amount)); 

        amount = 17;
        System.out.println(amount + " --> " + getMinCoins(amount));   
        
        amount = 33;
        System.out.println(amount + " --> " + getMinCoins(amount)); 

        amount = 99;
        System.out.println(amount + " --> " + getMinCoins(amount));          
    }
}

```

**Solution Breakdown:**

*Time Complexity:* O(n<sup>2</sup>)

* Line 3: A public array is given containing the set of coins available.

* Line 6: The function `getMinCoins()` is defined; it has ArrayList as its return type and int amount as its parameter.

* Line 9: The ArrayList of type Integer is allocated to store the change.

* Lines 10-17: A for loop traverses the `int[]coins` array from beginning to end (given in descending order).

* Line 12: Since the first index of coins has the maximum element, compare in the while condition whether this amount is greater than the max coin.

* Line 14: If yes, subtract the max value coin from the amount given.

* Line 15: Add this coin to the change list.

* Line 17: When the largest coin becomes greater than the remaining amount, the while loop breaks and the value of `i` is incremented to move to the next (lesser value) coin.

* Keep iterating this for loop, until the remaining amount can no longer be subdivided by the available coins.

### 11: Find the Egyptian Fraction

**Problem Statement:**

Every positive fraction can be represented as the sum of its unique unit fractions. A fraction is a unit fraction if the numerator is 1 and the denominator is a positive integer. For example, *1/3* is a unit fraction. Such a representation is called Egyptian fraction.

```java
class Fraction {
 public static void printEgyptianFraction(int numerator, int denominator) {
  //write your code here
  int n = -1; //calculate the correct value 
  System.out.print("1/" + n + " , "); //printing out your solution
 }
}
```

**Solution:**

```java
class Fraction
{
    public static void printEgyptianFraction(int numerator, int denominator) 
    {
      //if either numerator or denominator is zero
      if (denominator == 0 || numerator == 0){
        return;
      }
      //numerator divides denominator -> fraction in 1/n form
      if (denominator % numerator == 0) {
        System.out.print("1/" + denominator / numerator);
        return;
      }
      //denominator can divide numerator -> number not a fraction 
      if (numerator % denominator == 0) {
        System.out.println(numerator / denominator);
        return;
      }
      //if numerator greater than denominator 
      if (numerator > denominator) {
        System.out.println(numerator / denominator + " , ");
        printEgyptianFraction(numerator % denominator, denominator);
        return;
      }
      //denominator  greater than numerator here
      int n = denominator / numerator + 1;
      System.out.print("1/" + n + " , ");
      //call function recursively for remaining part  
      printEgyptianFraction(numerator * n - denominator, denominator * n);
}
}

class Main{
  public static void main(String[] args){

  //Example 1
  int numerator = 6, denominator = 14;
  System.out.print("Egyptian Fraction Representation of " + numerator + "/" + denominator + " is\n ");
  Fraction.printEgyptianFraction(numerator, denominator);
  System.out.println();
  
  //Example 2
  numerator = 2;
  denominator = 3;
  System.out.print("Egyptian Fraction Representation of " + numerator + "/" + denominator + " is\n ");
  Fraction.printEgyptianFraction(numerator, denominator);

  }
}

```

**Solution Breakdown:**

*Time Complexity:* *O(log_3)*

For a given number of the form *n/d*, where d > n, first find the greatest possible unit fraction and then perform recursion for the remaining part.

For example, consider *6/14*. We first find the ceiling of *14/6*, i.e., 3, so the first unit fraction becomes *1/3*. Now subtract *1/3* out of *6/14* and recur for *6/14* – *1/3*.

We use the greedy algorithm because we want to reduce the fraction to a form where the denominator is greater than the numerator, and the numerator doesn’t divide the denominator.

The method is to find the biggest unit fraction we can and subtract it from the remaining fraction. Doing subtractions always decreases this group of unit fractions, but it never repeats a fraction and eventually will stop, which is why we call this approach greedy.

<a name="dc"></a>

## Divide and Conquer: 

Similar to Dynamic Programming, Divide and Conquer algorithms work by breaking down a problem into sub-problems. Where they differ is that Divide and Conquer algorithms solve each sub-problem and then combine the results to form the ultimate solution, whereas the sub-problems in Dynamic Programming are fully separate.

This is another staple type of algorithm that will be tested in your coding interview.

### 12: Euclidean Algorithm Problem

**Problem Statement:**

Given two integers `a` and `b`, calculate the largest number (GCD) that divides both of them without leaving a remainder.

```java
class EuclideanAlgorithm
{ 
    public static int GCD(int a, int b) 
    {
        // your awesome code goes here!
        return -1;
    }
} 
```

**Solution:**

```java
class EuclideanAlgorithm
{ 
    public static int GCD(int a, int b) 
    {
        if (a == 0)
            return b;
        return GCD(b % a, a);
    }

    // Driver Program 
    public static void main(String[] args) 
    { 
        Random rand = new Random(); // built-in funtion provided by the library java.util.Random in Java for Random Number Generation
        int a = rand.nextInt(50);   // use random inputs 
        int b = a * rand.nextInt(10) + rand.nextInt(35);  
        System.out.println("GCD(" + a +  " , " + b+ ") = " + GCD(a, b)); 

        a = (rand.nextInt(150)%50); b = (rand.nextInt(200)%5);   // you can play around with the range of random numbers to see different outputs
        System.out.println("GCD(" + a +  " , " + b+ ") = " + GCD(a, b)); 

        a = rand.nextInt(10); b = rand.nextInt(10); 
        System.out.println("GCD(" + a +  " , " + b+ ") = " + GCD(a, b)); 

    }
} 

```

**Solution Breakdown:**

*Time Complexity:* *O(log min(a,b))*

* Line 5: The algorithm starts by checking if the first number (`a` , which was obtained by `b \%ab%a` in recursive calls) is 0.
* Line 6: If that is the case, then return `b`.
* Line 7: Otherwise, we make the next recursive call `GCD(b % a, a)`.

<br>


### 13: Missing number in Sorted Array

**Problem Statement:**

Given an array of contiguous integers starting from `x`, with one missing integer in between, and the size of the array, find the missing number!

```java
class MissingNumber 
{
    public static int missingNumber(int arr[], int size) 
    {  
        // your awesome code here
        return Integer.MIN_VALUE;
    }
}
```

**Solution:**

```java
class MissingNumber {
 
 // Performing a binary search like technique to find the missing number in the array 
 public static int missingNumber(int arr[], int size) {
  
  int leftLimit = 0, rightLimit = size - 1; // initialize limits

  // Keeping in check the Boundary Cases! 
  if (arr[leftLimit] != 1) // if '1' is not present at 0th index
   return 1;

  while (leftLimit <= rightLimit) // binary search
  {
   int middle = (leftLimit + rightLimit) / 2;

   // Element at index `i` should be `i+1` (e.g. 1 at index 0). If this is the first element  which is not `i`+ 1, then  missing element is middle+1 
   if (arr[middle] != middle + 1 && arr[middle - 1] == middle)
    return middle + 1;

   // If this is not the first missing element search in left subarray 
   if (arr[middle] != middle + 1)
    rightLimit = middle - 1; // update rightLimit to search only left

   // if it follows index+1 property then search in right side 
   else
    leftLimit = middle + 1; // update leftLimit to search only right
  }
  return -1; // if no element missing 
 }

 public static void main(String args[]) {
  int[] input1 = {1,2,4};
  int[] input2 = {1,2,3,4,6};
  int[] input3 = {2,3,4,5,6};
  int[] input4 = {1,2,3,4,5,6,7,8,9,10};

  System.out.println("Find the Missing Number!");
  System.out.println(Arrays.toString(input1) + " --> " + missingNumber(input1, input1.length));
  System.out.println(Arrays.toString(input2) + " --> " + missingNumber(input2, input2.length));
  System.out.println(Arrays.toString(input3) + " --> " + missingNumber(input3, input3.length) + "\t\t\t\t\t\t Corner Case I - Handeled");
  System.out.println(Arrays.toString(input4) + " --> " + missingNumber(input4, input4.length) + "\t\t\t Corner Case II - Handeled");
 }
}

```

**Solution Breakdown:**

*Time Complexity:* *O(log_n)*

* Line 38: The driver program calls the function `missingNumber()` with `int [] arr` and `int size` as its parameters.

* Line 6: Initialize the right and left limits.

* Lines 9-10: Handles corner case 1. Return `1` if array’s 1st element is not equal to 1.

* Line 12-18: Begin by finding the middle index of the array, if the element at `middle` is not equal to `middle + 1`, and this is the first missing element, `middle + 1` is the missing element.

* Lines 21-26: If this is not the first missing element and `arr[middle]` is not equal to `middle+1`, search in the right half. Otherwise, search in the left half of the array.

* Line 28: Handles corner case 2. Return `-1` if you end up traversing the whole array and no element is missing.

<a name="ga2"></a>

## Graphs Algorithms:

For our final section we'll look at problems to build proficiency with common graph-related questions. These questions are becoming increasingly popular in interviews due to their prevalence in social-media mapping, meaning now more than ever it's key to come prepared with this practice.

### 14: Calculate the Number of Nodes in a Given Graph Level

**Problem Statement:**

Implement a function that returns the number of nodes at a given level of an undirected graph.

**Graph.java:**

```java
import java.io.*;
import java.util.*;

class Graph {
 private int vertices; //number of vertices 
 private LinkedList < Integer > adjacencyList[]; //Adjacency Lists 
 @SuppressWarnings("unchecked")
 // Constructor 
 Graph(int vert) {
  this.vertices = vert;
  this.adjacencyList = new LinkedList[vertices];
  for (int i = 0; i < this.vertices; ++i)
   this.adjacencyList[i] = new LinkedList();
 }

 // Function to add an edge into the graph 
 void addEdge(int source, int destination) {
  this.adjacencyList[source].add(destination);
 }

 public int getVertices() {
  return this.vertices;
 }

 public LinkedList < Integer > [] getAdj() {
  return this.adjacencyList;
 }
};
```

**main.java**:

```java
class CountNodes {
 public static int numberOfNodesInGivenLevel(Graph g, int source, int level) {
  int count = 0; //count initialized to zero
  int num_of_vertices = g.getVertices(); //getVertices given in Graph.java file

  // Write - Your - Code

  return count;
 }
}
```

**Solution:**

```java
  class CountNodes {
   public static int numberOfNodesInGivenLevel(Graph g, int source, int level) {
    int count = 0;
    int num_of_vertices = g.getVertices();
    //Integer Array to hold the history of visited nodes (by default-false)
    //Make a node visited whenever you add it into queue
    int visited[] = new int[num_of_vertices];
    //Create a linkedlist array called Queue
    LinkedList < Integer > queue = new LinkedList < Integer > ();
    //mark the visited nodes as true by setting value to 1 and add them to the queue
    visited[source] = 1;
    queue.add(source);
    //Traverse while queue is not empty
    while (queue.size() != 0) {
     //add the vertex/node from queue to result
     source = queue.poll();
     //Get adjacent vertices to the current node from the list
     LinkedList < Integer > Llist[];
     Llist = g.getAdj();
     Iterator < Integer > i = Llist[source].listIterator();

     while (i.hasNext()) {
      int temp = i.next();
      //if not already visited then add to the Queue
      if (visited[temp] != 1) {
       visited[temp] = visited[source] + 1;
       if (visited[temp] < level)
       queue.add(temp);
      }
     }
    }
    //calculating the count for the level
    for (int i = 0; i < num_of_vertices; i++)
     if (visited[i] == level)
      count++;
    return count;
   }
  }

  class Main {
   public static void main(String args[]) {
    Graph g = new Graph(6);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    g.addEdge(3, 5);
    g.addEdge(2, 4);

    int answer;

    answer = CountNodes.numberOfNodesInGivenLevel(g, 0, 1);
    System.out.println(answer);
    answer = CountNodes.numberOfNodesInGivenLevel(g, 0, 2);
    System.out.println(answer);
    answer = CountNodes.numberOfNodesInGivenLevel(g, 0, 3);
    System.out.println(answer);
    answer = CountNodes.numberOfNodesInGivenLevel(g, 0, 4);
    System.out.println(answer);
   }
  }

```

**Solution Breakdown:**

*Time Complexity:* *O(V + E)*

The solution above modifies the visited array to store the level of each node. Later, it counts the nodes with the same level (lines 32-35).

In this code, while visiting each node, the level of the visited node is set with an increment in the level of its parent node, i.e.,

```java
visited[child] = visited[parent] + 1 
```

This is how the level of each node is determined (line 26).

### 15: Transpose a Graph

**Problem Statement:**

Implement a function that takes a directed graph as input and prints its transpose.

**Graph.java:**

```java
import java.io.*;
import java.util.*;

class Graph {
 private int vertices; //number of vertices 
 private LinkedList < Integer > adjacencyList[]; //Adjacency Lists 
 @SuppressWarnings("unchecked")
 // Constructor 
 Graph(int vert) {
  this.vertices = vert;
  this.adjacencyList = new LinkedList[vertices];
  for (int i = 0; i < this.vertices; ++i)
   this.adjacencyList[i] = new LinkedList();
 }

 // Function to add an edge into the graph 
 void addEdge(int source, int destination) {
  this.adjacencyList[source].add(destination);
 }

 public int getVertices() {
  return this.vertices;
 }

 public LinkedList < Integer > [] getAdj() {
  return this.adjacencyList;
 }

 void printGraph() {

  for (int v = 0; v < this.vertices; v++) {
   System.out.print(v);
   for (Integer pCrawl: this.adjacencyList[v]) {
    System.out.print("->" + pCrawl);
   }
   System.out.print("\n");
  }
 }
};
```

**main.java:**

```java
class Transpose {
 public static void getTranspose(Graph g) {
  int num_of_vertices = g.getVertices(); //getVertices defined in Graph.java file

  Graph transposedGraph = new Graph(num_of_vertices); //new graph to store the transpose

  //Write your code here

  transposedGraph.printGraph(); //calling print function on the final transposed graph
 }
}
```

**Solution:**

```java
  class CountNodes {
   public static int numberOfNodesInGivenLevel(Graph g, int source, int level) {
    int count = 0;
    int num_of_vertices = g.getVertices();
    //Integer Array to hold the history of visited nodes (by default-false)
    //Make a node visited whenever you add it into queue
    int visited[] = new int[num_of_vertices];
    //Create a linkedlist array called Queue
    LinkedList < Integer > queue = new LinkedList < Integer > ();
    //mark the visited nodes as true by setting value to 1 and add them to the queue
    visited[source] = 1;
    queue.add(source);
    //Traverse while queue is not empty
    while (queue.size() != 0) {
     //add the vertex/node from queue to result
     source = queue.poll();
     //Get adjacent vertices to the current node from the list
     LinkedList < Integer > Llist[];
     Llist = g.getAdj();
     Iterator < Integer > i = Llist[source].listIterator();

     while (i.hasNext()) {
      int temp = i.next();
      //if not already visited then add to the Queue
      if (visited[temp] != 1) {
       visited[temp] = visited[source] + 1;
       if (visited[temp] < level)
       queue.add(temp);
      }
     }
    }
    //calculating the count for the level
    for (int i = 0; i < num_of_vertices; i++)
     if (visited[i] == level)
      count++;
    return count;
   }
  }

  class Main {
   public static void main(String args[]) {
    Graph g = new Graph(6);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    g.addEdge(3, 5);
    g.addEdge(2, 4);

    int answer;

    answer = CountNodes.numberOfNodesInGivenLevel(g, 0, 1);
    System.out.println(answer);
    answer = CountNodes.numberOfNodesInGivenLevel(g, 0, 2);
    System.out.println(answer);
    answer = CountNodes.numberOfNodesInGivenLevel(g, 0, 3);
    System.out.println(answer);
    answer = CountNodes.numberOfNodesInGivenLevel(g, 0, 4);
    System.out.println(answer);
   }
  }

```

**Solution Breakdown:**

*Time Complexity:* *O(V + E)*

First, you make another graph and start reversing it. Traverse the adjacency list of the given graph. When the program finds a vertex `v` in the adjacency list of vertex `u` (i.e., an edge from `u` to `v` in the given graph), add an edge from `v` to `u` in the `transposedGraph`, adding `u` in the adjacency list of vertex `v` of the new graph) (lines 9-13).

 In line 19, the `printGraph()` function prints the graph to console. You can find its implementation in `Graph.java` file (lines 29-36).


## More coding interview questions to ace algorithms:

16. Search in a rotated array
17. Find the median of two sorted arrays
18. Find duplicates in an array
19. The Dutch National Flag Problem
20. Find the longest common substring in a string
21. The Egg Drop Problem
22. Find the longest palindromic subsequence of a string
23. The Edit Distance Problem
24. Connect `n` pipes with the minimum cost
25. The Train Station Platform Problem
26. The Fractional Knapsack Problem
27. Find Kruskal’s minimum spanning tree
28. Find the peak element in an array
29. Shuffle the integers of an array
30. Search a graph breadth-first
31. Search a graph depth-first
32. Count the paths between two nodes
33. Print all connected components in a graph
34. Remove an edge of a graph
35. Implement topological sorting of a graph
36. Check if a graph is strongly connected
37. Check if a graph is Bipartite
38. Find the floor and ceiling of a number
39. Find the closest number in an array
40. Collect coins in the least steps
41. Find the maximum sum of two subarrays
42. The Coin Change Problem
43. The Partition Problem
44. Count element occurrence
45. The Sparse Search Problem

<a name="where"></a>

## Where to go from here

Great work! Hopefully, you can already feel that pre-interview anxiety starting to melt away. 

While this was a deep dive into 15 of the most common algorithm questions, there are many more possibilities that may come up in your interview. Varied practice is essential to success in a coding interview. 

To master the underlying patterns behind coding interview problems, check out our course, <a href="https://www.educative.io/courses/grokking-coding-interview-patterns-java?utm_campaign=coding-interview&utm_source=medium&utm_medium=&utm_content=&utm_term=&eid=5082902844932096">**Grokking Coding Interview Patterns in Java**</a>.

### Interview roadmap

If you’re unsure where the road to your dream front-end dev job leads next, take a look at our free [interview roadmap](https://www.codinginterview.com/interview-roadmap?eid=5082902844932096) to help you get quickly.

### Keep reading about interview prep on Educative
* [5 tried and true techniques to prepare for a coding interview](https://www.educative.io/blog/5-tried-and-true-techniques-to-prepare-for-a-coding-interview?eid=5082902844932096)
* [Cracking the top Amazon coding interview questions](https://www.educative.io/blog/crack-amazon-coding-interview-questions?eid=5082902844932096)

### Start a discussion
Which programming language do you think is most relevant for coding interviews? Was this article helpful? Let us know in the comments below!