Year-End Discount: 10% OFF 1-year and 20% OFF 2-year subscriptions!

Home/Blog/Crack the Top 50 Java Data Structure Interview Questions

Crack the Top 50 Java Data Structure Interview Questions

Nov 17, 2020 - 16 min read

Ryan Thelin

Java remains one of the most popular languages around the world, especially in financial fields. Companies like Goldman Sachs, eBay, Google, and Microsoft all hire Java developers.

Today, we’ll help you prepare for your next job interview at these and other popular companies by reviewing 50 of the most common Java data structure interview questions and answers.

By the end, you’ll have all the experience you need to answer the data structure questions that make up the bulk of most interviews.

Here’s what we’ll look at today:

Array Data Structure Questions
Linked List Data Structure Questions
String Data Structure Questions
Stack and Queue Data Structure Questions
Tree Data Structure Questions
What to learn next

Practice 100+ Java data structure questions in one place
Get hands-on experience with all the best Java questions from across our course library.

Ace the Java Coding Interview

Array Data Structure Questions

1. Array initialization

Which of the following statements will initialize an array?

// Option 1 int a[] = new int[5]; // 2 int a[5] = {1,2,3,4,5}; // 3 int a[] = {1,2,3,4,5};

2. Loops and Array size

What would you enter in the blank to run through all elements of the array?

int arr[] = {1,2,3,4}; for (int i = 0; i < _______ ; i++){ System.out.println(arr[i]); }

3. Linear or non-linear Data Structure

Is an array a linear data structure?

4. Default Values

What is the default value in boolean and integer arrays?

5. Common Error Message

What error message will the following code throw?

6. Merge Two Sorted Arrays

Problem Statement

Implement the method int[] mergeArrays(int[] arr1, int[] arr2) that takes two chronologically sorted arrays and returns a new sorted array including all elements from the input arrays.

Solution and Explanation:

class checkMergeArray { 
  // Merge arr1 and arr2 into resultantArray
  public static int[] mergeArrays(int[] arr1, int[] arr2) { 
    int s1 = arr1.length;
    int s2 = arr2.length;
    int[] resultantArray = new int[s1+s2];
    int i = 0, j = 0, k = 0;
    // Traverse both array 
    while (i < s1 && j < s2) { 
      // Check if current element of first 
      // array is smaller than current element 
      // of second array. If yes, store first 
      // array element and increment first array 
      // index. Otherwise do same with second array 
      if (arr1[i] < arr2[j]) 
        resultantArray[k++] = arr1[i++]; 
      else
        resultantArray[k++] = arr2[j++]; 
    } 
    // Store remaining elements of first array 
    while (i < s1) 
      resultantArray[k++] = arr1[i++]; 
    // Store remaining elements of second array 
    while (j < s2) 
      resultantArray[k++] = arr2[j++]; 
    return resultantArray;
  } 
  public static void main(String args[]) {
    int[] arr1 = {1,12,14,17,23}; // creating a sorted array called arr1
    int[] arr2 = {11,19,27};  // creating a sorted array called arr2
    int[] resultantArray = mergeArrays(arr1, arr2); // calling mergeArrays
    System.out.print("Arrays after merging: ");
    for(int i = 0; i < arr1.length + arr2.length; i++) {
      System.out.print(resultantArray[i] + " ");
    }
  }
}

Time Complexity: $O(n + m)$ where n and m are the sizes of arr1 and arr2.

In the solution above, we start by creating a new empty array of the size equal to the combined size of both input arrays.

Starting from the index 0 individually compare the elements at corresponding indexes of both arrays.

Place the element with a lower value in the resultant array, and increment the index of the array where you find the smallest element.

Keep repeating this until you hit the end of one array. Move the elements of the other array into the resultantArray as it is.

7. Find Two Numbers that Add up to n

Problem Statement

Create a method int[] findSum(int[] arr, int n) that takes an integer array arr and returns an array of the two integer elements that add up to integer n.

If there are multiple, return only one. If there is no such pair, return the original array.

Solution and Explanation:

class CheckSum{ 
  //Helper Function to sort given Array (Quick Sort)          
  public static int partition(int[] arr, int low, int high) { 
    int pivot = arr[high];  
    int i = (low - 1); // index of smaller element 
    for (int j = low; j < high; j++) { 
      // If current element is <= to pivot 
      if (arr[j] <= pivot) { 
        i++; 
        // swap arr[i] and arr[j] 
        int temp = arr[i]; 
        arr[i] = arr[j]; 
        arr[j] = temp; 
      } 
    } 
    // swap arr[i+1] and arr[high] (or pivot) 
    int temp = arr[i + 1]; 
    arr[i + 1] = arr[high]; 
    arr[high] = temp; 
    return i + 1; 
  } 
  public static void sort(int[] arr, int low, int high) { 
    if (low < high) { 
      int pi = partition(arr, low, high); 
      sort(arr, low, pi - 1); 
      sort(arr, pi + 1, high); 
    } 
  } 
  //Return 2 elements of arr that sum to the given value
  public static int[] findSum(int[] arr, int n) {
    //Helper sort function that uses the Quicksort Algorithm
    sort(arr, 0, arr.length - 1);   //Sort the array in Ascending Order
    int Pointer1 = 0;    //Pointer 1 -> At Start
    int Pointer2 = arr.length - 1;   //Pointer 2 -> At End
    int[] result = new int[2];
    int sum = 0;
    while (Pointer1 != Pointer2) {
      sum = arr[Pointer1] + arr[Pointer2];  //Calulate Sum of Pointer 1 and 2
      if (sum < n) 
        Pointer1++;  //if sum is less than given value => Move Pointer 1 to Right
      else if (sum > n) 
        Pointer2--; 
      else {
        result[0] = arr[Pointer1];
        result[1] = arr[Pointer2];
        return result; // containing 2 number 
      }
    }
    return arr; 
  } 
  public static void main(String args[]) {
    int n = 14;
    int[] arr1 = {1,2,3,4,5};
    if(arr1.length > 0){
      int[] arr2 = findSum(arr1, n);
      int num1 = arr2[0];
      int num2 = arr2[1];
      if((num1 + num2) != n)
        System.out.println("Not Found");
      else {
        System.out.println("Number 1 = " + num1);
        System.out.println("Number 2 = " + num2);
        System.out.println("Sum = " +  (n) );
      }
    } else {
      System.out.println("Input Array is Empty!");
    }
  }
}

Time Complexity: $O(nlogn)$

The best way to solve this is by first sorting the array.

Here, we use QuickSort to sort the array first. Then using two variables, one starting from the first index of the array and the second from size−1 index of the array.

If the sum of the elements on these indexes of the array is smaller than the given value n, then increment index from the start else decrement index from the end until the given value n is equal to the sum.

Store the elements on these indexes in the result array and return it.

8. Find Minimum Value in Array

Problem Statement

Create a method int findMinimum(int[] arr) that takes an array and returns the smallest element within the array.

Solution and Explanation:

class CheckMinimum
{
  //Returns minimum value from given Array 
  public static int findMinimum(int[] arr) {
 
    int minimum = arr[0];
 
    //At every Index compare its value with minimum and if its less 
    //then make that index value new minimum value
    for (int i = 1; i < arr.length; i++) {
 
      if (arr[i] < minimum) {
        minimum = arr[i];
      }
    }
    return minimum;
  } //end of findMinimum
 
  public static void main(String args[]) {
 
    int[] arr = { 9, 2, 3, 6};
 
    System.out.print("Array : ");
    for(int i = 0; i < arr.length; i++)
      System.out.print(arr[i] + " ");
    System.out.println();
 
    int min = findMinimum(arr);
    System.out.println("Minimum in the Array: " + min);
 
  }
 
}

Time Complexity: $O(n)$

Start with the first element, which is 9 in this example, and save it in minimum as the smallest value.

Then, iterate over the rest of the array and compare the minimum to each element.

If any element is smaller than the minimum, then set minimum to that element. By the end of the array, the number stored in the minimum will be the smallest integer in the whole array.

Enjoying the article? Scroll down to sign up for our free, bi-monthly newsletter.

9. Rearrange Positive & Negative Values

Problem Statement

Create the method void reArrange(int[] arr) that takes an integer array and returns the same array sorted with all negative integers to the left of the middle element and all positive integers to the right.

Solution and Explanation:

class CheckReArrange
{
  //Rearrange Positive and Negative Values of Given Array 
  public static void reArrange(int[] arr) 
  {
    int j = 0; 
    for (int i = 0; i < arr.length; i++) { 
      if (arr[i] < 0) {   // if negative number found
        if (i != j) { 
          int temp = arr[i];
          arr[i] = arr[j]; // swapping with leftmost positive
          arr[j] = temp;
        }
        j++; 
      } 
    } 
  } //end of reArrange()
  public static void main(String args[]) {
    int[] arr = {2, 4, -6, 8, -5, -10};
    System.out.print("Array before re-arranging: ");
    for(int i = 0; i < arr.length; i++)
      System.out.print(arr[i] + " ");
    System.out.println();
    reArrange(arr);
    System.out.print("Array after rearranging: ");
    for(int i = 0; i < arr.length; i++)
      System.out.print(arr[i] + " ");
  }
}

Time Complexity: $O(n)$

In this solution, we rearrange the elements within the array rather than create a new array. To do this, we keep two variables i and j. Both of them are 0 initially.

i iterates over the array while j keeps track of the position where the next encountered negative number will be placed.

When we come across a negative number, the values at i and j indexes are swapped, and j is incremented. This continues until the end of the array is reached.

10. Right Rotate the Array by One Index

Problem Statement

Create the method void rotateArray(int[] arr) which takes an array of integers and rotates the position of each element one to the right. The right-most element will rotate to become the left-most element.

Solution and Explanation:

class CheckRotateArray
{
  //Rotates given Array by 1 position
  public static void rotateArray(int[] arr) {
 
    //Store last element of Array.
    //Start from the Second last and Right Shift the Array by one.
    //Store the last element saved on the first index of the Array.
    int lastElement = arr[arr.length - 1];
 
    for (int i = arr.length - 1; i > 0; i--) {
 
      arr[i] = arr[i - 1];
    }
 
    arr[0] = lastElement;
  } //end of rotateArray
 
  public static void main(String args[]) {
 
    int[] arr = {3, 6, 1, 8, 4, 2};
 
    System.out.print("Array before rotation: ");
    for(int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
 
    rotateArray(arr);
 
    System.out.print("Array after rotation: ");
    for(int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
  }
 
}

Time Complexity: $O(n)$

To rotate the array towards the right, we have to move the array elements towards the right by one index.

This means every element stored at index i will be moved to i + 1 position.

However, if we start shifting elements from the first element of the array, then the element at last index arr[arr.length - 1] is overwritten.

We fix this by saving the last element of the array in the variable lastElement.

Then we start shifting elements from index i - 1 to i, where the initial value of i will be arr.length - 1, and we will keep shifting the elements until i is greater than 0.

When the loop ends, we store the value of lastElement in arr[0].

Linked List Data Structure Questions

11. Difference between Arrays and Linked Lists

What is the difference between Arrays and Linked Lists?

12. Singly Linked List

What makes Singly Linked Lists unique?

13. Mystery Code

What does the following fragment of code do?

Node currentNode = list.headNode; while(currentNode != null){ currentNode = currentNode.nextNode; }

14. Circular Linked List

What is a circular linked list?

15. Linked List Storage

Are elements in a linked list stored consecutively in memory?

16. Insertion in a Singly Linked List (insert at End)

Problem Statement

Create the method void insertAtEnd(T data) that will take a generic type T value called data and insert that value at the end of a linked list.

Solution and Explanation

SinglyLinkedList.java

main.java

public class SinglyLinkedList<T> {
//Node inner class for SLL
    public class Node {
        public T data;
        public Node nextNode;
    }
    public Node headNode; //head node of the linked list
    public int size;      //size of the linked list
    //Constructor - initializes headNode and size
    public SinglyLinkedList() {
        headNode = null;
        size = 0;
    }
    //Helper Function that checks if List is empty or not 
    public boolean isEmpty() {
        if (headNode == null) return true;
        return false;
    }
    //Inserts new data at the start of the linked list
    public void insertAtHead(T data) {
        //Creating a new node and assigning it the new data value
        Node newNode = new Node();
        newNode.data = data;
        //Linking head to the newNode's nextNode
        newNode.nextNode = headNode;
        headNode = newNode;
        size++;
    }
    // Helper Function to printList
    public void printList() {
        if (isEmpty()) {
            System.out.println("List is Empty!");
            return;
        }
        Node temp = headNode;
        System.out.print("List : ");
        while (temp.nextNode != null) {
            System.out.print(temp.data.toString() + " -> ");
            temp = temp.nextNode;
        }
        System.out.println(temp.data.toString() + " -> null");
    }
    
    //Inserts new data at the end of the linked list
    public void insertAtEnd(T data) {
        //if the list is empty then call insertATHead()
        if (isEmpty()) {
            insertAtHead(data);
            return;
        }
        //Creating a new Node with value data 
        Node newNode = new Node();
        newNode.data = data;
        newNode.nextNode = null;
        Node last = headNode;
        //iterate to the last element 
        while (last.nextNode != null) {
            last = last.nextNode;
        }
        //make newNode the next element of the last node
        last.nextNode = newNode;
        size++;
    }
}

Time Complexity: $O(n)$

If the list is empty, the situation is exactly like insertion at the head.

Otherwise, we can use a loop to reach the tail of the list and set our new node as the nextNode of the last node.

17. Search in a Singly Linked List

Problem Statement

Create the function searchNode (T data) that takes a generic type T value and searches the elements of our Singly Linked List for a node that matches T.

If it is within the linked list, return true. If value T is not in in the linked list, return false

Solution and Explanation:

SinglyLinkedList.java

main.java

class CheckSearch {  
    public static void main(String args[]) {
        SinglyLinkedList<Integer> sll = new SinglyLinkedList<Integer>(); 
        for (int i = 1; i <= 10; i++) {
            sll.insertAtEnd(i);
        }

        if(sll.searchNode(3)) {   // Calling search function
            System.out.println("Value: 3 is Found");
        }
        else {
            System.out.println("Value: 3 is not Found");
        }

        if(sll.searchNode(15)) {   // Calling search function
            System.out.println("Value: 15 is Found");
        }
        else {
            System.out.println("Value: 15 is not Found");
        }
    }
}

Time Complexity: $O(n)$

In this function, we traverse through the list and check whether the currentNode’s value of data matches the searched value data.

If it does, we will return True. Otherwise, we will return False.

18. Return the Nth node from End

Problem Statement

Create the method Object nthElementFromEnd(SinglyLinkedList<T> list, int n) that takes a linked list and returns the nth element from the end of the linked list.

Solution and Explanation:

SinglyLinkedList.java

main.java

 public static <T> Object nthElementFromEnd(SinglyLinkedList<T> list, int n) {
        int size = list.getSize();
        n = size - n + 1; //we can use the size variable to calculate distance from start
        if (size == 0 || n > size) {
            return null; //returns null if list is empty or n is greater than size
        }
        SinglyLinkedList.Node current = list.getHeadNode();
        int count = 1;
        //traverse until count is not equal to n
        while (current != null) {
            if (count == n)
                return current.data;
            count++;
            current = current.nextNode;
        }
        return null;
    }
    public static void main( String args[] ) {
        SinglyLinkedList<Integer> sll = new SinglyLinkedList<Integer>();
        sll.printList(); //list is empty
        System.out.println("3rd element from end : " + nthElementFromEnd(sll, 3)); //will return null
        for(int i=0; i<15; i+=2){
            sll.insertAtHead(i);
        }
        sll.printList(); // List is 14 -> 12 -> 10 -> 8 -> 6 -> 4 -> 2 -> 0 -> null
        System.out.println("3rd element from end : " + nthElementFromEnd(sll, 3)); //will return 4
        System.out.println("10th element from end : " + nthElementFromEnd(sll, 10));//will return null
    }
}

Time Complexity: $O(n)$

In the above solution, we first use the getter function list.getSize() to access the length of the list. Then we find the node which is at x position from the start using the equation:

$Position = size - n + 1$

19. Reverse a Linked List

Problem Statement

Create the method public static <T> void reverse(SinglyLinkedList<T> list) that will take a linked list as input and reverse its contents such that the final element from the input linked list is the first element of the output linked list.

Solution and Explanation:

SinglyLinkedList.java

main.java

class CheckReverse {
    public static void main( String args[] ) {
        SinglyLinkedList<Integer> list = new SinglyLinkedList<Integer>();
        for(int i = 0; i < 15; i+=2)
            list.insertAtEnd(i);
        System.out.print("Before ");
        list.printList();
        reverse(list);
        System.out.print("After ");
        list.printList();
    }
    public static <T> void reverse(SinglyLinkedList<T> list){
    SinglyLinkedList<T>.Node previous = null; //To keep track of the previous element, will be used in swapping links
            SinglyLinkedList<T>.Node current = list.headNode; //firstElement
            SinglyLinkedList<T>.Node next = null;
 
            //While Traversing the list, swap links
            while (current != null) {
                    next = current.nextNode;
                    current.nextNode = previous;
                    previous = current;
                    current = next;
            }
            //Linking Head Node with the new First Element
            list.headNode = previous;
    }
}

Time Complexity: $O(n)$

The loop that iterates through the list is the key to this solution. For any current node, its link with the previous node is reversed, and the variable next stores the next node in the list:

Store the current node’s nextNode in next

Set current node’s nextNode to previous (reversal)

Make the current node the new previous so that it can be used for the next iteration

Use next to move on to the next node

In the end, we simply point the head to the last node in our loop.

20. Find if Doubly Linked-list is a Palindrome

Problem Statement

Create the method isPalindrome(DoublyLinkedList<T> list) that takes a doubly linked list and returns if the list is a palindrome (the same if written in reverse).

It will return true if the linked list is a palindrome, or false if it’s not.

Solution and Explanation

DoublyLinkedList.java

main.java

public class DoublyLinkedList<T> {
    //Node inner class for DLL
    public class Node {
        public T data;
        public Node nextNode;
        public Node prevNode;
    }
    public Node headNode;
    public Node tailNode;
    public int size;
    public DoublyLinkedList() {
        this.headNode = null;
        this.tailNode = null;
    }
    public boolean isEmpty() {
        if (headNode == null && tailNode == null)
            return true;
        return false;
    }
    public Node getHeadNode() {
        return headNode;
    }
    public Node getTailNode() {
        return tailNode;
    }
    public int getSize() {
        return size;
    }
    public void insertAtHead(T data) {
        Node newNode = new Node();
        newNode.data = data;
        newNode.nextNode = this.headNode; //Linking newNode to head's nextNode
        newNode.prevNode = null;
        if (headNode != null)
            headNode.prevNode = newNode;
        else
            tailNode = newNode;
        this.headNode = newNode;
        size++;
    }
    public void insertAtEnd(T data) {
        if (isEmpty()) {
            insertAtHead(data);
            return;
        }
        Node newNode = new Node();
        newNode.data = data;
        newNode.nextNode = null;
        newNode.prevNode = tailNode;
        tailNode.nextNode = newNode;
        tailNode = newNode;
        size++;
    }
    public void printList() {
        if (isEmpty()) {
            System.out.println("List is Empty!");
            return;
        }
        Node temp = headNode;
        System.out.print("List : null <- ");
        while (temp.nextNode != null) {
            System.out.print(temp.data.toString() + " <-> ");
            temp = temp.nextNode;
        }
        System.out.println(temp.data.toString() + " -> null");
    }
    public void printListReverse() {
        if (isEmpty()) {
            System.out.println("List is Empty!");
            return;
        }
        Node temp = tailNode;
        System.out.print("List : null <- ");
        while (temp.prevNode != null) {
            System.out.print(temp.data.toString() + " <-> ");
            temp = temp.prevNode;
        }
        System.out.println(temp.data.toString() + " -> null");
    }
    public void deleteByValue(T data) {
        //if empty then simply return
        if (isEmpty())
            return;
        //Start from head node
        Node currentNode = this.headNode;
        if (currentNode.data.equals(data)) {
            //data is at head so delete from head
            deleteAtHead();
            return;
        }
        //traverse the list searching for the data to delete
        while (currentNode != null) {
            //node to delete is found
            if (data.equals(currentNode.data)) {
                currentNode.prevNode.nextNode = currentNode.nextNode;
                if (currentNode.nextNode != null)
                    currentNode.nextNode.prevNode = currentNode.prevNode;
                size--;
            }
            currentNode = currentNode.nextNode;
        }
    }
    public void deleteAtHead() {
        if (isEmpty())
            return;
        headNode = headNode.nextNode;
        if (headNode == null)
            tailNode = null;
        else
            headNode.prevNode = null;
        size--;
    }
    public void deleteAtTail() {
        if (isEmpty())
            return;
        tailNode = tailNode.prevNode;
        if (tailNode == null)
            headNode = null;
        else
            tailNode.nextNode = null;
        size--;
    }
}

Time Complexity: $O(n)$

We start by taking pointers to headNode and tailNode (lines 3-4).

Next, we check for a corner-case, when the linked list is empty, an empty linked-list is a palindrome so we return true (lines 5-7).

Then, we simply traverse the linked list from both ends simultaneously and see if the traversals result in the same sequence of values (lines 8-14).

If that is not the case, the linked list is not a palindrome (lines 9-11), otherwise, it is.

String Data Structure Questions

21. Creating a String Object

Do both of these statements create a string?

String str = new String("abc"); //or String str1 = "abc";

22. Storage of Strings

Where are strings stored in memory?

23. Advantage of Immutability

What is one advantage of the data type’s immutable property?

24. Mutable Strings in Java

Can you create a mutable string in Java? If so, how?

25. Equals Behavior

What is the difference between equals() method and == operator?

26. Reverse Words in a Sentence

Problem Statement

Create an algorithm that takes a string of multiple words and returns the same string with the words in reversed order.

Solution and Explanation:

class ReverseWords {
  // Null terminating strings are not used in java
  public static void strRev(char[] str, int start, int end) {
    if (str == null || str.length < 2) {
      return;
    }
    while (start < end) {
      char temp = str[start];
      str[start] = str[end];
      str[end] = temp;
      start++;
      end--;
    }
  }
  public static void reverseWords(char[] sentence) {
    // Here sentence is a null-terminated string ending with char '\0'.
    if (sentence == null || sentence.length == 0) {
      return;
    }
    // To reverse all words in the string, we will first reverse
    // the string. Now all the words are in the desired location, but
    // in reverse order: "Hello World" -> "dlroW olleH".
    int len = sentence.length;
    strRev(sentence, 0, len - 2);
    // Now, let's iterate the sentence and reverse each word in place.
    // "dlroW olleH" -> "World Hello"
    int start = 0;
    int end;
    while (true) {
      // find the  start index of a word while skipping spaces.
      while (sentence[start] == ' ') {
        ++start;
      }
      if (start >= sentence.length - 1) {
        break;
      }
      // find the end index of the word.
      end = start + 1;
      while (end < sentence.length - 1 && sentence[end] != ' ') {
        ++end;
      }
      // let's reverse the word in-place.
      strRev(sentence, start, end - 1);
      start = end;
    }
  }
  static char[] getArray(String t) {
    char[] s = new char[t.length() + 1];
    int i = 0;
    for (; i < t.length(); ++i) {
      s[i] = t.charAt(i);
    }
    return s;
  }
  public static void main(String[] args) {
    char[] s = getArray("Hello World!");
    System.out.println(s);
    reverseWords(s);
    System.out.println(s);
  }
}

Time Complexity: $O(n)$

This works in two general steps.

First, we reverse all characters in the string such that the final character becomes the first.

The final word will now be first, however, the word itself will also be in reverse order.

Next, we traverse the reversed string and now reverse each word in place.

The characters of each word will then be in the correct order while the position of each word is still reversed from the originally passed string.

27. Find all Palindrome Substrings

Problem Statement

Write an algorithm that takes a string and finds all non-single letter palindromes within the input string.

Solution and Explanation:

class PalindromeSubStrings{
  public static boolean isPalindrome(String input, int i, int j) {
    while(j > i){
      if(input.charAt(i) != input.charAt(j))
        return false;
      i++;
      j--;
    }
    return true;
  }
  public static int findAllPalindromeSubstrings(String input) {
    int count = 0;
    for(int i = 0 ; i < input.length() ; i++) {
      for(int j = i + 1 ; j < input.length() ; j++) {
        if(isPalindrome(input,i,j)){
          System.out.println(input.substring(i,j+1));
          count++;
        }
      }
    }
  
    return count;
  }
  public static void main(String[] args) {
    String str = "aabbbaa";
    int count = findAllPalindromeSubstrings(str);
    System.out.println("Total palindrome substrings: " + count);
  }
}

Time Complexity: $O(n^2)$

For each letter in the input string, start expanding to the left and right while checking for even and odd length palindromes. Move to the next letter if we know a palindrome doesn’t exist.

We expand one character to the left and right and compare them. If both of them are equal, we print out the palindrome substring.

28. Longest Substring with K Distinct Characters

Problem Statement

Given an algorithm that takes a string and integer K and returns the length of the longest substring with no more than K distinct characters.

Solution and Explanation

import java.util.*;
class LongestSubstringKDistinct {
  public static int findLength(String str, int k) {
    if (str == null || str.length() == 0 || str.length() < k)
      throw new IllegalArgumentException();
    int windowStart = 0, maxLength = 0;
    Map<Character, Integer> charFrequencyMap = new HashMap<>();
    // in the following loop we'll try to extend the range [windowStart, windowEnd]
    for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
      char rightChar = str.charAt(windowEnd);
      charFrequencyMap.put(rightChar, charFrequencyMap.getOrDefault(rightChar, 0) + 1);
      // shrink the sliding window, until we are left with 'k' distinct characters in the frequency map
      while (charFrequencyMap.size() > k) {
        char leftChar = str.charAt(windowStart);
        charFrequencyMap.put(leftChar, charFrequencyMap.get(leftChar) - 1);
        if (charFrequencyMap.get(leftChar) == 0) {
          charFrequencyMap.remove(leftChar);
        }
        windowStart++; // shrink the window
      }
      maxLength = Math.max(maxLength, windowEnd - windowStart + 1); // remember the maximum length so far
    }
    return maxLength;
  }
  public static void main(String[] args) {
    System.out.println("Length of the longest substring: " + LongestSubstringKDistinct.findLength("araaci", 2));
    System.out.println("Length of the longest substring: " + LongestSubstringKDistinct.findLength("araaci", 1));
    System.out.println("Length of the longest substring: " + LongestSubstringKDistinct.findLength("cbbebi", 3));
  }
}

Time Complexity: $O(n)$

This problem follows the Sliding Window pattern.

We can use a HashMap to remember the frequency of each character we have processed.

First, we will insert characters from the beginning of the string until we have K distinct characters in the HashMap.

These characters will be our sliding window. We are asked to find the longest such window having no more than K distinct characters. We will remember the length of this window as the longest window so far.

After this, we will keep adding one character in the sliding window (i.e., slide the window ahead).

In each step, we will try to shrink the window from the beginning if the count of distinct characters in the HashMap is larger than K. We will shrink the window until we have no more than K distinct characters in the HashMap.

While shrinking, we’ll decrement the character’s frequency going out of the window and remove it from the HashMap if its frequency becomes zero.

At the end of each step, we’ll check if the current window length is the longest so far, and if so, remember its length.

29. Fruit Basket Problem

Problem Statement

With a given array of characters where each character represents a fruit tree, place the maximum number of fruits in each of 2 baskets. The only restriction is that each basket can have only one type of fruit.

You can start with any tree, but you can’t skip a tree once you have started. You will pick one fruit from each tree until you cannot, i.e., you will stop when you have to pick from a third fruit type.

Write a function to return the maximum number of fruits in both the baskets.

Solution and Explanation:

import java.util.*;
class MaxFruitCountOf2Types {
  public static int findLength(char[] arr) {
    int windowStart = 0, maxLength = 0;
    Map<Character, Integer> fruitFrequencyMap = new HashMap<>();
    // try to extend the range [windowStart, windowEnd]
    for (int windowEnd = 0; windowEnd < arr.length; windowEnd++) {
      fruitFrequencyMap.put(arr[windowEnd], fruitFrequencyMap.getOrDefault(arr[windowEnd], 0) + 1);
      // shrink the sliding window, until we are left with '2' fruits in the frequency map
      while (fruitFrequencyMap.size() > 2) {
        fruitFrequencyMap.put(arr[windowStart], fruitFrequencyMap.get(arr[windowStart]) - 1);
        if (fruitFrequencyMap.get(arr[windowStart]) == 0) {
          fruitFrequencyMap.remove(arr[windowStart]);
        }
        windowStart++; // shrink the window
      }
      maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
    }
    return maxLength;
  }
  public static void main(String[] args) {
    System.out.println("Maximum number of fruits: " + 
                          MaxFruitCountOf2Types.findLength(new char[] { 'A', 'B', 'C', 'A', 'C' }));
    System.out.println("Maximum number of fruits: " + 
                          MaxFruitCountOf2Types.findLength(new char[] { 'A', 'B', 'C', 'B', 'B', 'C' }));
  }
}

Time Complexity: $O(n)$

This problem follows the Sliding Window pattern and is quite similar to the Longest Substring with K Distinct Characters.

In this problem, we need to find the length of the longest subarray with no more than two distinct characters (or fruit types!).

This transforms the current problem into the Longest Substring with K Distinct Characters where K=2.

30. Print All Combinations of Balanced Braces

Problem Statement

Given n pairs of parentheses, print all combinations of parentheses for a balanced, symmetrical pattern.

Solution and Explanation:

class AllBraces{
  static void print(ArrayList<ArrayList<Character>> arr) {
    for (int i = 0; i < arr.size(); i++) {
      System.out.println(arr.get(i).toString());
    }
  }
  static void printAllBacesRec(
    int n,
    int leftCount,
    int rightCount, ArrayList<Character> output,
    ArrayList<ArrayList<Character>> result) {
    if (leftCount >= n && rightCount >=n) {
      result.add((ArrayList)output.clone());
    }
    if (leftCount < n) {
      output.add('{');
      printAllBacesRec(n, leftCount + 1, rightCount, output, result);
      output.remove(output.size() - 1);
    }
    if (rightCount < leftCount) {
      output.add('}');
      printAllBacesRec(n, leftCount, rightCount + 1, output, result);
      output.remove(output.size() - 1);
    }
  }
  static ArrayList<ArrayList<Character>> printAllBraces(int n) {
    ArrayList<ArrayList<Character>> result = new ArrayList<ArrayList<Character>>();
    ArrayList<Character> output = new ArrayList<Character>();
    printAllBacesRec(n, 0, 0, output, result);
    return result;
  }
  
  public static void main(String[] args) {
    ArrayList<ArrayList<Character>> result = new ArrayList<ArrayList<Character>>();
    result =  printAllBraces(3);
    print (result);
  }
}

Time Complexity: $O(2^n)$

The key to this solution is a recursive approach. We’ll maintain counts of two variables left_braces and right_braces.

Each iteration, we’ll see if left_braces count is lower than n. If yes, we add to left_braces and recurse into the next step.

If right_braces is less than left_braces, we’ll add to right_braces and recurse.

We stop the recursion process when both left_braces and right_braces are equal to n.

Stack and Queue Data Structure Questions

Implement Queue using Stacks

How does dequeue work for Queue elements?

Is a Queue Last in First Out (LIFO) or First in First Out (FIFO)?

What is a postfix expression?

Evaluate Stack prefix expressions

Generate Binary Numbers from 1 to n using Queue

Reverse the First K Elements of a Queue

Sort the Values in a Stack

Next Greater Element using Stack

How does a Priority Queue differ from a regular Queue?

Tree Data Structure Questions

Check if Two Binary Trees are Identical

What is the difference between a serialized and deserialized Binary Tree?

What types of solutions are suited for breadth-first search (BFS)?

How does post-order traversal compare with preorder traversal?

Nth Highest Number in Binary Search Tree (BST)

Print all Leaf Nodes of a Binary Tree

Find the Greatest Sum of a Path Beginning at the Root Node

Check if Left and Right Subtrees are Identical

Write an In-Order Iterator for a Binary Tree

Reverse Level Order Traversal

What to learn next

Congratulations on finishing those 50 questions!

The best way to prepare for coding interviews is the practice you’re doing right now. Soon, you’ll know all the question types you could encounter at your next interview.

To help you prepare for interviews, Educative has created the course Grokking Coding Interview Patterns in Java.

You’ll learn the 24 patterns behind every coding interview question, so you can be prepared to answer any problem you might face using Java.

Simplify your coding interview prep today! Get a structured, pattern-based approach to solving any coding interview question, without having to drill endless practice problems.

Happy learning!

Continue reading about Data Structures and Interview Prep

Top Data Structures and Algorithms every developer must know

Crack the Top 40 Java Coding Interview Questions

Cracking the top Amazon coding interview questions

WRITTEN BYRyan Thelin

Join a community of more than 1.6 million readers. A free, bi-monthly email with a roundup of Educative's top articles and coding tips.

Learn in-demand tech skills in half the time

SOLUTIONS

For Enterprise

For Individuals

For HR & Recruiting

For Bootcamps

PRODUCTS

Educative Learning

Educative Onboarding

Educative Skill Assessments

Educative Projects

Pricing

For Enterprise

For Individuals

Free Trial

LEGAL

Privacy Policy

Terms of Service

Business Terms of Service

CONTRIBUTE

Become an Author

Become an Affiliate

Become a Contributor

RESOURCES

Educative Blog

EM Hub

Educative Sessions

Educative Answers

ABOUT US

Our Team

Careers
Hiring

Frequently Asked Questions

Contact Us

Press

MORE

GitHub Students Scholarship

Course Catalog

Early Access Courses

Earn Referral Credits

CodingInterview.com

Crack the Top 50 Java Data Structure Interview Questions

Practice 100+ Java data structure questions in one place Get hands-on experience with all the best Java questions from across our course library. Ace the Java Coding Interview

Array Data Structure Questions

1. Array initialization

2. Loops and Array size

3. Linear or non-linear Data Structure

4. Default Values

5. Common Error Message

6. Merge Two Sorted Arrays

7. Find Two Numbers that Add up to n

8. Find Minimum Value in Array

9. Rearrange Positive & Negative Values

10. Right Rotate the Array by One Index

Linked List Data Structure Questions

11. Difference between Arrays and Linked Lists

12. Singly Linked List

13. Mystery Code

14. Circular Linked List

15. Linked List Storage

16. Insertion in a Singly Linked List (insert at End)

17. Search in a Singly Linked List

18. Return the Nth node from End

19. Reverse a Linked List

20. Find if Doubly Linked-list is a Palindrome

String Data Structure Questions

21. Creating a String Object

22. Storage of Strings

23. Advantage of Immutability

24. Mutable Strings in Java

25. Equals Behavior

26. Reverse Words in a Sentence

27. Find all Palindrome Substrings

28. Longest Substring with K Distinct Characters

29. Fruit Basket Problem

30. Print All Combinations of Balanced Braces

Stack and Queue Data Structure Questions

Tree Data Structure Questions

What to learn next

Continue reading about Data Structures and Interview Prep

Practice 100+ Java data structure questions in one place
Get hands-on experience with all the best Java questions from across our course library.

Ace the Java Coding Interview

7. Find Two Numbers that Add up to `n`