Crack the Top 50 Java Data Structure Interview Questions

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.

Answer any Java interview problem by learning the patterns behind common questions.

Grokking the Coding Interview Patterns

I created Grokking the Coding Interview because I watched too many talented engineers fail interviews they should have passed. At Microsoft and Meta, I saw firsthand what separated the candidates who succeeded from the ones who didn't. It wasn't how many LeetCode problems they'd solved. It was whether they could look at an unfamiliar problem and know how to approach it the right way. That's what this course teaches. Rather than throwing hundreds of disconnected problems at you, we organize the entire coding interview around 28 fundamental patterns. Each pattern is a reusable strategy. Once you understand two pointers, for example, you can apply them to dozens of problems you've never seen before. The course walks you through each pattern step by step, starting with the intuition behind it, then building through increasingly complex applications. As with every course on Educative, you will practice in a hands-on way with 500+ challenges, 17 mock interviews, and detailed explanations for every solution. The course is available in Python, Java, JavaScript, Go, C++, and C#, so you can prep in the language you'll actually use in your interview. Whether you're preparing for your first FAANG loop or brushing up after a few years away from interviewing, this course will give you a repeatable framework for cracking the coding interview.

85hrs

Intermediate

579 Challenges

580 Quizzes

Java data structure interview roadmap: Beginner to advanced#

Preparing for Java data structure interviews can feel overwhelming because there are hundreds of possible questions and dozens of problem-solving patterns. Many candidates make the mistake of jumping straight into difficult problems before mastering the fundamentals, which often leads to frustration and slow progress.

A better approach is to think of interview preparation as a progression. Just as you wouldn't learn advanced calculus before basic algebra, you shouldn't tackle complex graph algorithms before becoming comfortable with arrays, strings, and linked lists. This roadmap organizes common Java data structure interview topics into beginner, intermediate, and advanced levels so you can focus on the right concepts at the right time.

Difficulty overview#

Beginner questions#

At this level, interviewers want to verify that you understand core data structures and can write clean, correct code. These questions often appear in phone screens and entry-level interviews.

Array initialization#

Difficulty: Beginner
Concepts tested: Arrays, indexing, memory layout

Interviewers use this question to verify that you understand how arrays are declared, initialized, and accessed in Java.

Default values in arrays#

Difficulty: Beginner
Concepts tested: Java memory model, default initialization

This question checks whether you know how Java initializes primitive and reference arrays automatically.

Find the minimum value in an array#

Difficulty: Beginner
Concepts tested: Iteration, comparison logic

A simple problem that evaluates your ability to traverse data structures efficiently.

Merge two sorted arrays#

Difficulty: Beginner
Concepts tested: Arrays, two pointers

Interviewers often use this problem to introduce pattern-based thinking while keeping implementation complexity low.

Difference between arrays and linked lists#

Difficulty: Beginner
Concepts tested: Time complexity, memory trade-offs

This question measures your understanding of data structure selection and performance implications.

String creation and immutability#

Difficulty: Beginner
Concepts tested: Strings, memory management

Java strings appear frequently in interviews because immutability affects both performance and correctness.

Intermediate questions#

Intermediate questions focus less on syntax and more on applying common patterns to solve realistic problems. This is where most software engineering interviews spend the majority of their time.

Reverse a linked list#

Difficulty: Intermediate
Common pattern: Pointer manipulation

Interviewers expect you to understand linked list traversal and node re-linking. Follow-up questions often involve recursive solutions.

Nth node from the end#

Difficulty: Intermediate
Common pattern: Fast and slow pointers

This problem tests whether you can use multiple pointers efficiently without extra memory.

Longest substring with K distinct characters#

Difficulty: Intermediate
Common pattern: Sliding window

A classic interview problem that introduces dynamic window expansion and contraction.

Fruit Basket problem#

Difficulty: Intermediate
Common pattern: Sliding window with hash maps

Interviewers use this problem to evaluate your ability to combine multiple data structures within a single solution.

Queue using stacks#

Difficulty: Intermediate
Common pattern: Data structure transformation

This question tests your understanding of stack and queue behavior as well as amortized complexity.

Tree traversals#

Difficulty: Intermediate
Common pattern: DFS and BFS

Candidates should be comfortable with preorder, inorder, postorder, and level-order traversals.

Advanced questions#

Advanced questions evaluate deeper algorithmic thinking, optimization skills, and the ability to reason about complex recursive or graph-based systems.

Print all combinations of balanced braces#

Difficulty: Advanced
Core concepts: Recursion, backtracking

Common follow-up: Generate combinations efficiently and analyze time complexity.

Complex tree problems#

Difficulty: Advanced
Core concepts: Tree recursion, divide-and-conquer

Interviewers may ask for diameter calculations, lowest common ancestors, or path-based optimizations.

Binary tree iterators#

Difficulty: Advanced
Core concepts: Trees, stacks, iterator design

These problems test your ability to combine data structures with object-oriented design.

Reverse level-order traversal#

Difficulty: Advanced
Core concepts: BFS, queues, stacks

A common follow-up involves optimizing space complexity.

Graph cloning#

Difficulty: Advanced
Core concepts: Graph traversal, hash maps

Candidates must handle cycles correctly while preserving graph structure.

Advanced recursion challenges#

Difficulty: Advanced
Core concepts: Recursion, state management, backtracking

These questions often separate strong candidates from average ones because they require careful reasoning rather than memorization.

Patterns to master at each level#

One of the biggest interview preparation breakthroughs happens when you stop viewing problems as isolated questions and start recognizing the patterns behind them. A single sliding window technique, for example, can solve dozens of seemingly different interview questions.

Recommended preparation schedule#

Week 1: Arrays and strings#

Focus on array traversal, searching, sorting concepts, string manipulation, and hash-based lookups. These topics appear in almost every interview.

Week 2: Linked lists#

Learn pointer manipulation, reversing lists, cycle detection, and common traversal techniques.

Week 3: Stacks and queues#

Practice stack-based parsing, monotonic stacks, queue implementations, and breadth-first processing patterns.

Week 4: Trees and traversals#

Master DFS, BFS, recursive tree problems, and binary search trees.

Week 5: Pattern-based practice#

Start combining concepts through sliding window, two-pointer, hashing, and recursion problems.

Week 6: Mock interviews#

Simulate real interview conditions by solving problems aloud and explaining your thought process while coding.

What difficulty level should you target?#

New graduates#

Focus heavily on Beginner and Intermediate questions. Most entry-level interviews emphasize fundamentals and communication rather than advanced algorithms.

Junior engineers#

You should be highly comfortable with Intermediate problems and begin solving selected Advanced questions.

Mid-level and senior engineers#

Expect Advanced algorithmic discussions, optimization questions, and deeper conversations about trade-offs and scalability.

Progression roadmap#

The goal is not to rush through the levels but to build confidence and pattern recognition at each stage.

Interview preparation guidance#

As you progress through this roadmap, spend less time memorizing solutions and more time understanding why a solution works. Interviewers rarely care whether you've seen a specific problem before. They care about how you approach unfamiliar challenges, communicate your reasoning, and adapt your solution when requirements change.

When practicing:

Solve problems without looking at answers immediately.
Focus on recognizing patterns rather than memorizing code.
Explain your thought process out loud.
Revisit older problems after a few days.
Participate in mock interviews whenever possible.

Most candidates struggle because they jump directly into advanced problems before mastering the fundamentals. Interview success comes from building skills progressively, recognizing patterns, and developing confidence through consistent practice.

A structured roadmap is almost always more effective than randomly solving problems from different categories. By mastering each level before moving to the next, you'll develop the problem-solving intuition that interviewers are actually looking for.

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

Java

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.

Java

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.

Java

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

Java

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

Java

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].

Answer any Java interview problem by learning the patterns behind common questions

Grokking the Coding Interview Patterns

I created Grokking the Coding Interview because I watched too many talented engineers fail interviews they should have passed. At Microsoft and Meta, I saw firsthand what separated the candidates who succeeded from the ones who didn't. It wasn't how many LeetCode problems they'd solved. It was whether they could look at an unfamiliar problem and know how to approach it the right way. That's what this course teaches. Rather than throwing hundreds of disconnected problems at you, we organize the entire coding interview around 28 fundamental patterns. Each pattern is a reusable strategy. Once you understand two pointers, for example, you can apply them to dozens of problems you've never seen before. The course walks you through each pattern step by step, starting with the intuition behind it, then building through increasingly complex applications. As with every course on Educative, you will practice in a hands-on way with 500+ challenges, 17 mock interviews, and detailed explanations for every solution. The course is available in Python, Java, JavaScript, Go, C++, and C#, so you can prep in the language you'll actually use in your interview. Whether you're preparing for your first FAANG loop or brushing up after a few years away from interviewing, this course will give you a repeatable framework for cracking the coding interview.

85hrs

Intermediate

579 Challenges

580 Quizzes

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++;
    }
}

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

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
    }
}

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.

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

Java

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

Java

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

Java

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:

Java

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

Java

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

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#

Frequently Asked Questions

What are the Types of Data Structures in Java?

Some common types of data structures in Java: -Array -Linked List -Stack -Queue -Binary Tree -Binary Search Tree -Heap -Hashing -Graph

How to prepare for a DSA interview?

Data structures and algorithms (DSA) rely heavily on core programming concepts. It’s essential to have a strong base in basic coding to grasp them effectively. Start by practicing your code in a programming language that you’re comfortable with, and then steadily enhance your coding abilities.

How do I prepare for a data structure interview?

Review key concepts: Focus on fundamental data structures (arrays, linked lists, stacks, queues, trees, graphs, hash tables).
Practice coding: Solve problems on platforms like LeetCode, HackerRank, or CodeSignal.
Understand algorithms: Study sorting, searching, and traversal algorithms and practice writing them from scratch.
Mock interviews: Simulate real interview scenarios to improve problem-solving speed and communication.

Difficulty	Topics	Typical Interview Stage	Goal
Beginner	Arrays, strings, basic linked lists	Initial screens	Master fundamentals
Intermediate	Trees, stacks, queues, sliding window	Technical interviews	Apply common patterns
Advanced	Graphs, recursion, dynamic programming, complex tree problems	Final rounds	Demonstrate problem-solving depth

Beginner	Arrays, hashing, two pointers
Intermediate	Sliding window, linked lists, BFS/DFS
Advanced	Recursion, backtracking, tree algorithms

Crack the Top 50 Java Data Structure Interview Questions

Java data structure interview roadmap: Beginner to advanced#

Difficulty overview#

Beginner questions#

Array initialization#

Default values in arrays#

Find the minimum value in an array#

Merge two sorted arrays#

Difference between arrays and linked lists#

String creation and immutability#

Intermediate questions#

Reverse a linked list#

Nth node from the end#

Longest substring with K distinct characters#

Fruit Basket problem#

Queue using stacks#

Tree traversals#

Advanced questions#

Print all combinations of balanced braces#

Complex tree problems#

Binary tree iterators#

Reverse level-order traversal#

Graph cloning#

Advanced recursion challenges#

Patterns to master at each level#

Recommended preparation schedule#

Week 1: Arrays and strings#

Week 2: Linked lists#

Week 3: Stacks and queues#

Week 4: Trees and traversals#

Week 5: Pattern-based practice#

Week 6: Mock interviews#

What difficulty level should you target?#

New graduates#

Junior engineers#

Mid-level and senior engineers#

Progression roadmap#

Interview preparation guidance#

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#

What to learn next#

Continue reading about Data Structures and Interview Prep#

Frequently Asked Questions

What are the Types of Data Structures in Java?

How to prepare for a DSA interview?

How do I prepare for a data structure interview?

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