2 Java Beginner Level Binary Search Interview Questions & Answers
Below is a list of our Java Beginner Level Binary Search 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. Find the highest peak in the mountain array.
This interview question concentrates on the developer's skills with Java arrays and binary search.
You are given an array of a mountain of size at least 3. Each element in the array represents the altitude of peaks in the mountain. There exists one peak in the array at index i such that
â— the peaks from index 0 to index i are in ascending order:
arr[0] < arr[1] < … < arr[i - 1] < arr[i]
â— and, the peaks from index i to index size - 1 are in descending order:-
arr[i] > arr[i + 1] > … > arr[size - 2] < arr[size - 1]
Your task is to find the index i of highest peak.
/*Example*/
arr = [0, 1, 0]
expected output = 1
arr = [0, 4, 2, 1]
expected output = 1Solution:
We can scan all the elements of the array. When the next element is less than the previous element, the previous element will be the highest peak. We will return its index.
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int num = 0;
while(arr[num] < arr[num + 1]) num++;
return num;
}
}Time complexity- O(n)
Space complexity- O(1)
Approach II (binary search):
The condition arr[i] < arr[i + 1] will be true upto the required index i, and it will false afterwards. For example, given arr = [1, 2, 3, 4, 5, 6, 4, 3, 2, 1],
1 2 3 4 5 6 4 3 2 1
T T T T T F F F F F
In such a scenario, we can use binary search. We will find the first index which is false using binary search and will return it.
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int left = 0;
int right = arr.length - 1;
while(left < right) {
int mid = left + (right -left) / 2;
if (arr[mid] < arr[mid + 1]) {
left = mid + 1;
} else {
right = mid;
}
}
// left is the first index which makes the condition false
return left;
}
}Time complexity- O(log n)
Space complexity- O(1)
Written by Jennie Taylor on May 21st, 2021
2. What is the smallest letter greater than the target?
This interview question concentrates on the developer's skills working with Java arrays and binary search.
You are given an array of English lowercase letters in sorted order. You are also given a target letter. Your task is to find the smallest element in the array that is larger than the given target.
NOTE:- Letters do wrap around. It means if we don’t have any element in the array larger than the target, we return the smallest letter as the answer. See examples.
/*Example*/
letters = [“câ€, “gâ€, “lâ€]
target = “aâ€
expected output = “câ€
letters = [“câ€, “gâ€, “lâ€]
target = “câ€
expected output = “gâ€
letters = [“câ€, “gâ€, “lâ€]
target = “dâ€
expected output = “gâ€
letters = [“câ€, “gâ€, “lâ€]
target = “jâ€
expected output = “c†(letters wrapped around)
letters = [“câ€, “gâ€, “lâ€]
target = “kâ€
expected output = “c†(letters wrapped around)Solution:
This is a lot like a search for integers. So we can use binary search for this. We need to care about the “wrap around†case. For handling this, we increase our search space. Instead of using letters.length - 1 for right pointer, we will use letter.length. The left pointer after the loop will be the index of the letter satisfying the given condition. When we can not find any letter greater than the target, the value of left will be letters.length after the loop. Then we take modulo to return the first element of the array.
class Solution {
public char nextGreatestLetter(char[] letters, char target) {
int left = 0;
int right = letters.length;
while(left < right) {
int mid = left + (right -left) / 2;
if (letters[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return letters[left % letters.length];
}
}Time complexity- O(log n)
Space complexity- O(1)
Written by Jennie Taylor on May 21st, 2021