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:
Get hands-on experience with all the best Java questions from across our course library.
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]);
}
Is an array a linear data structure?
What is the default value in boolean and integer arrays?
What error message will the following code throw?
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: 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.
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:
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.
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:
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.
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:
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.
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:
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]
.
What makes Singly Linked Lists unique?
What does the following fragment of code do?
Node currentNode = list.headNode;
while(currentNode != null){
currentNode = currentNode.nextNode;
}
What is a circular linked list?
Are elements in a linked list stored consecutively in memory?
Practice hundreds of Java interview questions on data structures, recursion, dynamic programming and more.
Educative’s Paths give you access to our best hands-on Java practice from across our course library.
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
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:
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.
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:
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:
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
.
Problem Statement
Create the method Object nthElementFromEnd(SinglyLinkedList<T> list, int n)
that takes a linked list and returns the n
th element from the end of the linked list.
Solution and Explanation:
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:
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:
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:
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:
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:
current
node’s nextNode
in next
current
node’s nextNode
to previous
(reversal)current
node the new previous
so that it can be used for the next iterationnext
to move on to the next nodeIn the end, we simply point the head to the last node in our loop.
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
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:
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.
Where are strings stored in memory?
What is one advantage of the data type’s immutable property?
Can you create a mutable string in Java? If so, how?
What is the difference between equals()
method and ==
operator?
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:
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.
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:
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.
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:
This problem follows the Sliding Window pattern.
We can use a HashMap to remember the frequency of each character we have processed.
K
distinct characters in the HashMap.K
distinct characters. We will remember the length of this window as the longest window so far.K
. We will shrink the window until we have no more than K
distinct characters in the HashMap.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:
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
.
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:
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
.
n
using QueueK
Elements of a QueueCongratulations on finishing those 50 questions!
The best way to prepare for your next programming interviews is the practice data structure questions like these. Soon, you’ll know all the question types you could encounter at your next interview.
To help you study these problem types, Educative has created the Learning Path, Ace the Java Coding Interview.
Paths offer a module-based collection of our top materials on a subject from across our course library.
By the end of this path, you’ll have honed your Java skills with over 100+ coding interview questions on data structures, recursion, dynamic programming, and more.
Happy learning!
Join a community of more than 1.3 million readers. A free, bi-monthly email with a roundup of Educative's top articles and coding tips.