15 Java Advanced Level Algorithms Interview Questions & Answers
Below is a list of our Java Advanced Level Algorithms interview questions. Click on any interview question to view our answer advice and answer examples. You may view 5 answer examples before our paywall loads. Afterwards, you'll be asked to upgrade to view the rest of our answers.
1. What does `myMethod()` in the following code do? Can you modify the code to process a doubly linked list?
class Node {
int value;
Node next; // line-3
String id;
static void myMethod(Node head) {
Node nextNode;
for (Node n=head; n!=null; ) {
nextNode = n.next;
while (nextNode!=null
&& nextNode.next!=null
&& nextNode.value==nextNode.next.value)
nextNode = nextNode.next;
if (nextNode==null)
n = n.next = null;
else { // line-16
n.next = nextNode.value==n.value?nextNode.next:nextNode;
n = n.next; // line-18
}
}
}
}This question tests your understanding of singly- and doubly-linked list data structures and your ability to code their logic in Java.
myMethod() processes the singly-linked list given by its head node in the parameter. myMethod() removes all but one of the nodes in each sequence of consecutive nodes that have the same value in the list.
The following changes make the code process on a doubly linked-list for the same solution:
1. Also declare a previous pointer on class `Node` -- replace line-3 with the following:
Node next, prev; 2. Also update the `prev` pointer value when a node is removed – insert the following if statement between lines 17 & 18:
if (n.next!=null)
n.next.prev = n;Written by Ayse Karaman on May 21st, 2021
2. What does the following code do? Can you simplify it?
Set<Integer> myMethod(Set<Integer> setA, Set<Integer> setB){
Set<Integer> setZ = new HashSet<>(setB);
setB.retainAll(setA);
setZ.removeAll(setA);
setB.addAll(setZ);
return setB;
}
This question tests your familiarity with the set operations both in the mathematical sense and Java Set construct.
In the first line of `myMethod()`, setZ is cloned from setB “at birthâ€-- all elements of setA are added to it in its constructor. So, these two sets have the same elements now.
retainAll() is the set intersection operation. The code –
setB.retainAll(setA);removes from setB all the elements that DO NOT exist in setA.
removeAll() is the set difference operation. It does the opposite of retainAll() in the sense that –
setZ.removeAll(setA);removes from setZ all the elements that DO exit in setA.
Since setB and setZ started out with the same elements, they now partition the original setB. In other words, setB and setZ have no elements in common, but they together have all the elements of the original setB.
addAll() takes the union of the sets. The code –
setB.addAll(setZ);adds all the elements of setZ to setB, which in turn restores setB to its original content.
So, myMethod() has no effect and it can be replaced with the following code:
Set<Integer> myMethod(Set<Integer> setA, Set<Integer> setB){
return setB;
}
Written by Ayse Karaman on May 21st, 2021
3. Which of the following 4 operations is faster on a HashSet<String> than on a LinkedList<String>?
The four operations are as follows:
1) remove(String)
2) add(String)
3) size(String)
4) equals(Object)
remove(String) takes longer on LinkedList than on HashSet.
Removing an element in a List involves locating that element in the list and this operation is a linear search, O(n).
HashSet internally uses a Map structure to store its elements. Entry search in a HashMap is O(1). Element deletion is also O(1) in the average case and O(log n) in the worst case, still faster than O(n) time of LinkedList.remove().
The other operations have the same complexity on LinkedList and HashSet. add(String) and size(String) take O(1), and equals(Object) takes O(n) time on both.
Written by Ryan Brown on May 21st, 2021
4. Which of the following two operations are faster in a LinkedList than on a TreeSet - `add(int)`, `contains(Object)`, `remove(Object)`? Explain why.
The correct answer is `add()` operation is faster on LinkedList than on TreeSet.
On a LinkedList, add() appends the given value to the end of the list. This operation takes constant, i.e. O(1) time.
TreeSet is a balanced binary search (BST) tree and maintains its elements in the order of their values. The add() operation inserts the given value in its place among the ordered elements and such operation on a balanced BST is O(log n).
contains() and remove() both take longer on LinkedList (O(n)) than on TreeSet (O(log n)).
Written by Ryan Brown on May 21st, 2021
5. Write a recursive method that returns true if the entries of a character array (char[]) constitute a palindrome, false otherwise.
public static boolean isPalindrome(char[] word, int index) {
if (index>=word.length/2)
return true;
if (word[word.length-index-1]!=word[index])
return false;
return isPalindrome(word, ++index);
}In order to call this method, use the following code:
public static boolean isPalindrome(char[] word) {
if (word==null)
return false;
return isPalindrome(word, 0);
}Written by Ryan Brown on May 21st, 2021
6. Suppose T is a full tree. Which of Depth-First Search (DFS) and Breadth-First Search (BFS) algorithms traverse a leaf of T soonest?
The correct answer is DFS. A DFS algorithm, as its name implies, traverses nodes at levels below the current node before it processes the rest of the nodes at the same level.
BFS does the opposite-- exhausts all known nodes at a level before it traverses a node in the level below. Since T is full, all of its leaves are at the same tree level. BFS reaches a leaf only after all internal nodes are traversed, while DFS reaches a leaf the soonest can be.
Written by Ryan Brown on May 21st, 2021
7. Write a method that takes two String parameters and returns true if these two String-s are anagrams of one another. Two strings are anagrams if they have the same number of each character.
The interviewer wants to see your approach to coding an algorithm using the appropriate data structures for it.
The following is an answer that you might give to this question:
static boolean compare(String str1, String str2) {
return parse(str1).equals(parse(str2));
}
static Map<Character, Integer> parse(String str) {
Map<Character, Integer> map = new HashMap<>();
Integer tmp;
char c;
for (int i=0; i<str.length(); i++) {
c=str.charAt(i);
if ((tmp=map.get(c))==null)
tmp=0;
map.put(c, ++tmp);
}
return map;
}This is an accurate and efficient solution for the question asked. It doesn’t cover the null cases, i.e. when one or both of the parameters `str1` and `str2` are null. However, edge cases are not crucial in the interview. The interviewer is interested in the solution logic you worked into your code.
The interviewer often wants to explore a variation or improvement on your code to see how you carry out that discussion and make the modifications. For this case, s/he is likely to refer to the following improvement possibly by bringing up whether it is always necessary to run the method parse():
static boolean compare(String str1, String str2) {
if (str1==null && str2==null)
return true;
if (str1==null || str2==null)
return false;
if (str1.length()!=str2.length())
return false;
return parse(str1).equals(parse(str2));
}In this modification, the compare() method is the same as before. compare() isn’t unnecessarily called if the two String-s have different lengths (anagrams necessarily have the same same length).
Another typical improvement is memory efficiency. The interviewer would ask whether you can do the same solution by using a single Map to preserve memory space. In the above solution, compare() is called twice, creating a Map each time. The following code uses only one Map and thus half the memory as the above code:
static boolean compare2(String str1, String str2) {
if (str1==null && str2==null)
return true;
if (str1==null || str2==null)
return false;
if (str1.length()!=str2.length())
return false;
Map<Character, Integer> map = new HashMap<>();
Integer tmp;
char c;
for (int i=0; i<str1.length(); i++) {
c=str1.charAt(i);
if ((tmp=map.get(c))==null)
tmp=0;
map.put(c, ++tmp);
}
for (int i=0; i<str2.length(); i++) {
c=str2.charAt(i);
if ((tmp=map.get(c))==null || --tmp<0)
return false;
map.put(c, tmp);
}
return true;
}Written by Ayse Karaman on May 21st, 2021
8. A String str is a pseudo-palindrome if str is a palindrome when all the 5 vowels of the English alphabet, upper-case and lower-case, are removed from it. Can you write an algorithm that returns True if a String is a pseudo-palindrome?
In addition to testing your coding ability, this question investigates how comfortable you are in adapting to concepts and designing their algorithmic solutions.
Following is an accurate and a well-sufficient answer in a typical case, especially in an interactive interview step:
Set<Character> VOWELS = new HashSet<>();
{
VOWELS.add('A'); VOWELS.add('E');
VOWELS.add('I'); VOWELS.add('O');
VOWELS.add('U');
}
boolean isVowel(char c) {
return VOWELS.contains(Character.toUpperCase(c));
}
boolean pseudoPalindrome1(String str) {
StringBuilder sb = new StringBuilder();
char c;
for (int i=0; i<str.length(); i++)
if (!isVowel(c=str.charAt(i)))
sb.append(c);
for (int i=0; i<sb.length()/2; i++)
if (sb.charAt(i)!=sb.charAt(sb.length()-i-1))
return false;
return true;
}The method pseudoPalindrome1() gives the accurate answer in O(n), which is the optimal complexity of an algorithm for this problem.
On the other hand, pseudoPalindrome2() in the following code provides an alternate solution with improved execution-time and memory performance. Note that pseudoPalindrome2() also uses the helper method isVowel() along with the VOWELS structure looked up by it:
boolean pseudoPalindrome2(String str) {
int start = 0, end = str.length()-1;
while (true) {
while (start<str.length() && isVowel(str.charAt(start)))
start++;
if (start>=end)
return true;
while (end>=0 && isVowel(str.charAt(end)))
end--;
if (start>=end)
return true;
if (str.charAt(start)!=str.charAt(end))
return false;
start++;
end--;
}
}pseudoPalindrome2() combines the solution logic into a single loop that iterates on each character of the input String at most once. By this, it eliminates the additional loop and the storage space (StringBuilder) used in pseudoPalindrome1().
Although pseudoPalindrome2() has the same asymptotic complexity as pseudoPalindrome1(), it outperforms pseudoPalindrome1() in the absolute time. Furthermore, pseudoPalindrome2() is an in-place algorithm – doesn’t use any auxiliary storage for processing its input. Its memory complexity is O(1), which is better than the O(n) memory complexity of pseudoPalindrome1().
Written by Ayse Karaman on May 21st, 2021
9. What does myMethod() in the following code do? Can you write its recursive version?
int myMethod(int[] intArray) {
int currentIndex=0;
for (int i=0; i<intArray.length; i++)
if (intArray[i]!=0)
intArray[currentIndex++]=intArray[i];
return currentIndex;
}With this question, the interviewer wants to see your comfort level with the code logic and your ability to write recursive algorithms.
myMethod() removes all the 0-s in the input array and moves to their places the values coming after them, retaining the order of values. In the end, all the non-zero values appear in the first K cells of intArray, where K is the number of such values in intArray. myMethod() returns this value K. The values in rest of the cells (cells with index K..intArray.length-1) aren’t any changed.
For example, suppose following is the array passed in to myMethod():
intArray = {0, 1, 0, 2, 0, 0, 3, 0, 0};After its processing myMethod() returns 3 and the array now has the following values:
intArray = {1, 2, 3, 2, 0, 0, 3, 0, 0};Following is the recursive version of myMethod():
int myMethodRecursive(int[] intArray, int size, int index) {
if (size==intArray.length)
return index;
if (intArray[size]!=0)
intArray[index++]=intArray[size];
return myMethodRecursive(intArray, ++size, index);
}Following is the caller of myMethodRecursive(int[], int, int) with the same parameter list as myMethod():
int myMethodRecursive(int[] intArray) {
return myMethodRecursive(intArray, 0, 0);
}Written by Ayse Karaman on May 21st, 2021
10. In the following code, the class Item implements Comparable for sorting its objects in decreasing order of nOfLikes. Write a Comparator for sorting Item-s in increasing order of their costs. What happens when you use that Comparator for sorting Item-s?
class Item implements Comparable<Item>{
int nOfLikes;
int cost;
@Override public int compareTo(Item o) {
return -this.nOfLikes+o.nOfLikes;
}
// other class members..
}This questions tests your knowledge of Comparable and Comparable, and their use with respect to one another.
Following is the Comparator that can be used to sort Item objects in order of their costs:
class ItemComparator implements Comparator<Item>{
@Override
public int compare(Item o1, Item o2) {
return o1.cost-o2.cost;
}
}When ItemComparator is used on a group of Item-s, Eg. Item[] itemsArray:
Arrays.sort(items, new ItemComparator());itemsArray is sorted in increasing order of Item costs, i.e., the order dictated in ItemComparator, with no regard to the order in their Comparable implementation. When both Comparable and Comparator exist on a class objects, Comparator takes full effect and the objects are sorted as if there is no Comparable implementation at all.
Written by Ayse Karaman on May 21st, 2021
11. What is hashCode() and equals() contract? How can you implement hashCode() for the following equals() implementation?
@Override
public boolean equals(Object obj) {
return this.hashCode()>=obj.hashCode();
}This question tests how well you know the use of equals() and hashCodes() methods, as well as your understanding of hashCode() & equals() contract.
hashCode() & equals() contract is as follows:
Whenever two objects are equal to one another (i.e. the equals() method of one of these objects returns true when invoked with the other object as its parameter), the hashCode() methods of these two objects MUST return the same value.
However, the question of whether a hashCode() method can be implemented for the above equals() is out of context. This is because, this equals() method doesn’t implement an equivalence relationship and breaks its own contract. With this implementation, for instance, for any given objects o1 and o2:
o1.equals(o2);
and
o2.equals(o1);
do not always return the same value as they should.
The only hashCode() to obey the hashCode() & equals() contract in this case would be one to return a fixed value regardless of the object:
@Override
public int hashCode() {
return 5;
}
However, such an implementation would be nothing but furthering the erroneous code and should be avoided at all costs.
Written by Ayse Karaman on May 21st, 2021
12. Given the following problem, can you write an algorithm for computing the maximum number of these marbles you can buy with a given K dollars? What is the computational complexity of your algorithm?
The array int[] costs shows the costs of N=costs.length marbles so that marble i costs costs[i] dollars. Maximum cost of a marble is $100. Can you write an algorithm for computing the maximum number of these marbles you can buy with a given K dollars? What is the computational complexity of your algorithm?
This question tests your comfort level on writing algorithmic code with Java. This question also tests your knowledge of sort algorithms.
This problem asks to maximize the number of marbles that can be bought with a fixed amount of money. Since no distinction is made between the marbles and thus they all are identical, the problem is simply about buying the cheapest possible marbles available at the moment, until all money is spent.
buyMarbles() method in the following code is a solution to this problem:
int buyMarbles(int[] costs, int K) {
Arrays.sort(costs);
int result = 0;
for (int ii: costs) {
if (K-ii>=0) {
K-=ii;
result++;
if (K<=0)
return result;
}
}
return result;
}
buyMarbles() first sorts the given marble costs, then iterates to buy on these costs, from smallest to largest, until all the K dollars are spent.
buyMarbles() uses Arrays.sort() of core Java in order to sort the marble costs. Arrays.sort() uses comparison sort algorithms, namely Quicksort and Merge-Sort depending on the number of items being sorted. Comparison sort algorithms operate in time O(n*log n), where n is the number of marbles in this case, i.e. the length of costs[] array. O(n*log n) is also the overall complexity of buyMarbles() since its for loop iterates on n entries, and all the code within the for loop execute in O(1) time.
In this problem, the marble costs are in a bound range of 0 to 100. With this, a faster non-comparison sort algorithm, namely counting sort is available for an improved computation time. buyMarbles2() in the following code is an alternate solution using counting sort:
int buyMarbles2(int[] costs, int K) {
int[] costsSorted = new int[100001];
for (int i:costs)
costsSorted[i]++;
int result = 0, amt;
for (int i=0; i<costsSorted.length; i++) {
if (costsSorted[i]==0)
continue;
amt = Math.min(K/i, costsSorted[i]);
if (amt>=0) {
K-=amt*i;
result+=amt;
if (K<=0)
return result;
}
}
return result;
}
In buyMarbles2(), it only takes O(n) time to sort the marble costs (the first for loop), as opposed to O(n*log n) time of buyMarbles(). The rest of buyMarbles2() run in O(n) time as well and this solution is an improvement to buyMarbles()’s above.
Written by Ryan Brown on May 21st, 2021
13. The following code successfully compiles, but doesn't run. What is wrong with it? Can you fix it?
Random rand = new Random();
List<String> list = new ArrayList<>();
for (int i=0; i<10; i++)
list.add(""+rand.nextInt());
for (String str:list)
if (str.startsWith("-"))
list.remove(str);This question tests your knowledge of the foreach loop during modification of a Collection, as well as the alternatives to modify list elements.
The code throws a java.util.ConcurrentModificationException. This is because, a Collection can not be modified while it is iterated in a foreach loop.
One way to resolve this error is the direct use of the Iterator on the collection for removing the entry:
Iterator<String> iter = list.iterator();
while (iter.hasNext())
if (iter.next().startsWith("-"))
iter.remove();Since the collection here is a List, a regular for loop can be used in the following way:
String str;
int K=list.size();
for (int i=0; i<K; i++)
if ((str=list.get(i)).startsWith("-")) {
list.remove(str);
i--;
K--;
}Since Java 8, the list can be iterated to remove entries as follows:
list.removeIf(e
-> e.startsWith("-"));The following code also works by making an additional iteration on the list elements:
Set<String> removeThese = new HashSet<String>();
for (String str : list)
if (str.startsWith("-"))
removeThese.add(str);
list.removeAll(removeThese);Written by Ryan Brown on May 21st, 2021
14. Write a method that prints the number of occurrences of each letter in a given String in the order they occur. Eg. When the String is "abcbb", the output should be "a - 1, b - 3, c - 1". What is the runtime efficiency of your algorithm?
This question tests your algorithmic skills and your ability to use some of the Java data structures.
Following is a solution for this problem:
void countCharsInOrder(String str) {
Map<Character, Integer> map = new HashMap<>();
List<Character> list = new LinkedList<>();
char c;
Integer cnt;
for (int i=0; i<str.length(); i++) {
c = str.charAt(i);
cnt=map.get(c);
if (cnt==null) {
cnt=0;
list.add(c);
}
map.put(c, ++cnt);
}
for (char cc:list)
System.out.println(cc+" - "+map.get(cc));
}The method countCharsInOrder() runs in time O(n) where n=str.length() and is optimal. This is because, the HashMap element operations get() and put() each take O(1) time. Not all element operations in a LinkedList are O(1), however adding the element to the end of the list is. String.charAt(int) looks up the specific character position in an internal array backing it up and thus takes constant time as well.
Since the for-loops iterate on the characters in the input string (distinct characters and even faster in the second for-loop), the overall complexity of countCharsInOrder() is linear and fastest possible.
Written by Ayse Karaman on May 21st, 2021
15. Given two sorted integer arrays, find the K-th smallest integer among all in these two arrays combined. What is the complexity of your algorithm?
This question investigates your algorithmic thinking, as well as your understanding of MERGE-SORT logic without naming it.
Following is a solution algorithm for this problem:
int kThSmallest(int[] A, int []B, int K) {
if (A.length+B.length<K)
return Integer.MIN_VALUE;
int count = 0;
int indA = 0, indB = 0;
int current;
while (true) {
if (A[indA]>B[indB] || indA>=A.length)
current = B[indB++];
else current = A[indA++];
if (indA>=A.length)
return count==K-1?current:B[indB+K-count-2];
if (indB>=B.length)
return count==K-1?current:A[indA+K-count-2];
if (++count == K) return current;
}
}kThSmallest() uses the order of elements there already are in the two input arrays. It iteratively looks up the two elements in the array fronts and picks the smallest of them. This in fact is the MERGE-SORT logic.
Since positional access in array takes constant time, the statements in the body of while-loop take constant time. The while-loop processes exactly one of the K smallest elements in each of its iterations except the last. In its iteration, it processes more than one of these K smallest integers if all the elements in one of the arrays are all consumed. This means kThSmallest() executes in time O(K).
Written by Ayse Karaman on May 21st, 2021