16 Java Intermediate Level Binary Search Interview Questions & Answers

This interview question concentrates on the developer's skills with Java array and binary search.

You are given an array of integer nums and an integer limit. You will choose an integer divisor, divide all the integers of nums by divisor, and will add the divisions’ result. Find the smallest divisor such that the sum is less than or equal to the limit.

The result of a division is rounded to the nearest integer greater than the actual real result (i.e ceil of the division). For example:- 17 / 3 = 6, and 30 / 6 = 5.

/*Example*/

nums = [1, 2, 5, 9]		limit = 6
expected output = 5
explanation:
●	if the divisor were smaller (say 4), the sum after division would be 7 (1 + 1 + 2 + 3) which is greater than limit.
●	if the divisor were greater (say 6), the sum after division would be 5 (1 + 1 + 1 + 2) which is smaller than limit.

Solution:

We can use binary search. Let’s say min is the smallest divisor required. There are two observations:
● Given a divisor smaller than min, the sum after division will always be greater than the limit.
● Given a divisor larger than or equal to min, the sum after division will always be less than or equal to the limit.

divisors- 1 2 … min min + 1 min + 2 max-divisor
is sum F F F T T T T
less than
or equal
to limit

import java.util.*;
 
class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int left = 1;
        int right = Arrays.stream(nums).max().getAsInt();
        while(left < right) {
            int mid = left + (right -left) / 2;
       	 
            // is sum less than or equal to limit
            boolean isOk = isLessOrEqLimit(mid, nums, threshold);
            if (isOk) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    
    boolean isLessOrEqLimit(int divisor, int[] nums, int limit) {
        int sum = 0;
        for (int num : nums) {
            double quotient = ((double)num / (double)divisor);
            quotient = Math.ceil(quotient);
            sum += (int)quotient;
        }
        return sum <= limit;
    }
 
}

Time complexity- O(n log (max number))
Space complexity- O(1)

This interview question concentrates on the developer's skills with Java binary search and loops.

You own a garden which has flowers arranged in a row. The flowers have not bloomed yet. You need to make m bouquets. To make one bouquet, you need k adjacent flowers from the garden. For the ith flower, the adjacent flowers are (i - 1)th and (i + 1)th flowers.
The garden has n flowers. You are given an array bloomDay of size n. The ith flower will bloom on day bloomDay[i]. One flower can be used to make at most one bouquet.
Your task is to find the minimum number of days you need to wait so that enough flowers have bloomed to make m bouquets. If it is impossible to make m bouquets, return -1.

/*Example*/

bloomDay = [1, 10, 3, 10, 2]	m = 3		k = 1
expected output = 3
explanation:- x represents that the flower at that position has bloomed
after day 1:- [x, _, _, _, _]
after day 2:- [x, _, _, _, x]
after day 3:- [x, _, x, _, x]	After 3 days, we can make 3 bouquets.

Solution:

We can use binary search for it. Let’s say min is the minimum of days required. If we are asked:
● Can we make m bouquets in days less than min? The answer is definitely no.
● Can we make m bouquets in days greater than or equal to min? The answer is definitely yes.

0 1 … min - 1 min min + 1 … max-possible
F F F F T T T T

We can do the binary search from 0 to max-possible. We will check if we can make m bouquets in a mid number of days or not. We will update the variables accordingly as in the code. The value of max-possible is the maximum of bloomDay array i.e. the maximum number of days that a flower will take to bloom.

To check if we can make m bouquets in a mid number of days or not, we will use canMake function. We will see which flowers will bloom on or before the day days. After checking bloomed flowers, we see the number of adjacent flowers and then count the number of bouquets that can be formed using those adjacent flowers.

class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        if (m * k > bloomDay.length) {
            return -1;
        }
        int left = 1;
        int right = Arrays.stream(bloomDay).max().getAsInt();
        
        while(left < right) {
            int mid = left + (right -left) / 2;
            if (canMake(mid, bloomDay, m, k)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    
    
    public boolean canMake(int days, int[] bloomDays, int m, int k) {
        int bouquetsMade = 0;
        int adjFlowers = 0;
        
        for (int day : bloomDays) {
            // the current flower has not
            // bloomed yet before or on `day`
            if (day > days) {
                adjFlowers = 0;
                continue;
            }
            
            // the flower has bloomed
            bouquetsMade += (int)Math.floor((adjFlowers + 1) / k);
            adjFlowers = (adjFlowers + 1) % k;
        }
        return bouquetsMade >= m;
    }

}

Time complexity- O(log (max-possible))
Space complexity- O(1)

This interview question concentrates on the developer's skills with Java functions and binary search.

There are n bags. Each bag contains some number of balls given by array nums. The ith bag contains nums[i] number of balls. You need to do some operations on the array. In one operation, you take a bag and divide it into two bags containing a positive number of balls. For example, if you had a bag with 6 balls, you can do one operation and divide it into two bags containing 2 and 4 balls. You are also given an input parameter maxOperations which is the maximum number of operations that you can perform.

The penalty on all the bags is the maximum number of balls in a bag. Your task is to minimize the penalty in maxOperations number of operations.

/*Example*/

nums = [7, 6, 17]		maxOperations = 2
expected output = 7
explanation:
after first operation:- [7, 6, 7, 10]
after second operation:- [7, 6, 7, 7, 3]
the maximum number of balls is 7. So the penalty is 7.

Solution:

We can use binary search for it. Let’s say min is the minimum penalty that is possible using maxOperations. If we are asked:
● Can we have a penalty of less than min? The answer is no.
● Can we have a penalty greater than or equal to min? The answer is definitely yes.

1 2 … min - 1 min min + 1 … max-possible
F F F F T T T T

We will do the binary search from 1 to max-possible. The value of max-possible is the maximum penalty that we can have which is the penalty before any operation. The function canDo returns if we can have a penalty using maxOperations.

class Solution {
    public int minimumSize(int[] nums, int maxOperations) {
        int left = 1;
        int right = Arrays.stream(nums).max().getAsInt();
        
        while(left < right) {
            int mid = left + (right -left) / 2;
            if (canDo(mid, nums, maxOperations)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    
    public boolean canDo(int penalty, int[] nums, int maxOperations) {
        int operationsCount = 0;
        
        for (int num : nums) {
            // Typecasting int to double to get values after decimal
            double count = (double)num / (double)penalty;
            count = Math.ceil(count) - 1;
            operationsCount += (int)count;
        }
        
        return operationsCount <= maxOperations;
    }
    
}

Time complexity- O(log (max-possible))
Space complexity- O(1)

This question shows the developer's ability to work with Java binary and linear search.

You are given sorted array nums. All the integers occur twice except one integer. Find the single occurring integer.

/*Example*/

Given nums = [1, 1, 2, 2, 3, 3, 4, 8, 8]
Expected output = 4

Solution:

Approach I (linear search):

The array is 0-indexed. So for the duplicate integers, if one integer is at even index, the next should be at odd index until the single integer is encountered.
integers:- |1 1| |2 2| |3 3| |4| |8 8|
indices:- |0 1| |2 3| |4 5| |6| |7 8|
pair pair pair single pair (odd-even)
(even-odd) (even-odd) (even-odd)

So we will iterate over the odd indices and will compare its value with the value at the previous even index. If they are equal, we continue to look for the next odd index. If they are not equal, it means the integer at the previous even index is the required single integer. As we take the elements in pairs we will initialize the res variable with the last element as it may get skipped in case it is the last element or the only element.

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int res = nums[nums.length - 1];
        
        for (int i = 1; i < nums.length; i += 2) {
            if(nums[i] != nums[i - 1]) {
                res = nums[i - 1];
                break;
            }
        }
        
        return res;
    }
    
}

Time complexity- O(n)
Space complexity- O(1)

Approach II (binary search):

Let’s say the index of the single element is idx. From the above approach, it can be observed that,
For indices less than idx, the duplicate numbers are at even-odd indices, that is, the first duplicate is at an even index and the next duplicate is at the next odd index. Say these integers form the left partition.

For indices greater than idx, the duplicate numbers are at odd-even indices, that is, the first duplicate is at an odd index and the next duplicate is at the next even index. Say these integers form the right partition.
integers:- 1 1 2 2 3 3 4 8 8
indices:- 0 1 2 3 4 5 6 7 8
|<------------------------>| | |<--->|
left-partition single right-partition
integer

In such a scenario, we can use binary search. For the middle index mid, we will convert mid to an even index. Then we will compare it with integers at the next odd index, that is, we will compare nums[mid] with nums[mid + 1]. If they are equal, it means mid is an index of left-partition, so we will update left with mid + 2 (we are not updating it to mid + 1, because we already checked it). If they are not equal, it means mid is an index of right-partition, so we will update right to mid. After the loop, the left will be the index of the single number.

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
    
        while (left < right) {
            int mid = (left + right) / 2;
        
            if (mid % 2 == 1) mid--;
        
            if (nums[mid] != nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 2;
            }
        }
        
        return nums[left];
    }
    
}

Time complexity- O(log n)
Space complexity- O(1)

This question focuses on Java methods.

You have to implement a class TimeMap. There are two methods in this class: set and get. The class is a key-value store with associated timestamps.

=> The method set is called with three parameters:- key, value, and timestamp. The store stores these passed parameters in a data structure in the class. It returns no value.
=> The get method is called with two parameters: key and timestamp. This method retrieves the latest value corresponding to the key before the timestamp. If there is no such value, it returns the empty string “”.

/*Example*/

●	Calls:
â—‹	initialize TimeMap
â—‹	.set("foo", "bar", 1)
○	.get("foo", 1)			// returns “bar”
○	.get("foo", 3)			// returns “bar”
â—‹	.set("foo", "bar2", 4)
○	.get("foo", 4)			// returns “bar2”
○	.get("foo", 5)			// returns “bar2”
●	Calls:-
â—‹	initialize TimeMap
â—‹	.set("love", "high", 10)
â—‹	.set("love", "low", 20)
○	.get("love", 4)			// returns “”
○	.get("love", 10)			// returns “high”
○	.get("love", 15)			// returns “high”
○	.get("love", 20)			// returns “low”
○	.get("love", 25)			// returns “low”
â—‹	.set("super", "high", 30)
○	.get("super", 30)		// returns “high”
○	.get("super", 1)			// returns “”

Constraint
●	The value of timestamps for each get method call will be strictly increasing.

class TimeMap {

    /** Initialize your data structure here. */
    public TimeMap() {
        
    }
    
    public void set(String key, String value, int timestamp) {
        
    }
    
    public String get(String key, int timestamp) {
        
    }
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap obj = new TimeMap();
 * obj.set(key,value,timestamp);
 * String param_2 = obj.get(key,timestamp);
 */

Solution:

We will use a map to store keys and corresponding values and timestamps. We are naming the map as a store. For each key in the map, we will have an array (we call this array timedValues). Each element of the timedValues is an array of size 2. The first element is a timestamp and the other is the corresponding value.

For example 1, the final store will be:-
{
“foo” -> [[1, “bar”], [4, “bar2”]]
}
For example 2, the final store will be:-
{
“love” -> [[10, “high”], [20, “low”]],
“super” -> [[30, “high”]],
}

The set method will push to timedValues corresponding to the given key.
The get method will get the timedValues array corresponding to the given key. Since timedValues are always sorted in increasing order, we can do a binary search over timedValues to find the value with the largest timestamp less than or equal or passed timestamp in the function.

There may be a case when we don’t have a particular key in the store yet and we call either get or set for this key. We will create a helper function: getTimedValues. We will use this function to retrieve timeValues corresponding to that key. If the key already exists, we will return the timeValues straightway. If it doesn’t, we first set an empty array corresponding to that key and then return it.

class TimeMap {

    private HashMap<String, ArrayList<Pair<Integer, String>>> store;
        
    /** Initialize your data structure here. */
    public TimeMap() {
        store = new HashMap<String, ArrayList<Pair
<Integer, String>>>();
    }
    
    public void set(String key, String value, int timestamp) {
        ArrayList<Pair<Integer, String>> timedValues = 
getTimedValues(key);
        timedValues.add(new Pair(timestamp, value));
    }
    
    public String get(String key, int timestamp) {
        ArrayList<Pair<Integer, String>> timedValues = 
getTimedValues(key);
        
        int left = 0;
        int right = timedValues.size();
        
        while(left < right) {
            int mid = (left + right) / 2;
            if (timedValues.get(mid).getKey() > timestamp) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        if (right == 0) return "";
        
        return timedValues.get(right - 1).getValue();
    }
    
    private ArrayList<Pair<Integer, String>> getTimedValues
(String key) {
        if (!store.containsKey(key)) {
            store.put(key, new ArrayList<Pair<Integer, String>>());
        }
        
        return store.get(key);
    }
    
}

Time complexity for constructor- O(1)
Space complexity for constructor- O(1)
Time complexity for one call of set- O(1)
Space complexity for one call of set- O(1)
Time complexity for one call of get- O(log n) // n is the maximum number of calls to set
Space complexity for one call of get- O(1)

This question shows the developer's ability to work with Java array elements.

You are given three positive integers n, index, and maxSum. Your task is to create new array nums of length n which satisfies the following conditions:

1. nums[i] > 0, for 0 <= i < n, that is, nums[i] is a positive integer;
2. abs(nums[i] - nums[i + 1]) <= 1, for 0 <= i < n, that is, the difference between two adjacent number must be at most 1;
3. the sum of all integers in nums is less than or equal to maxSum;
4. nums[index] is maximized.
Return the maximized integer nums[index]. It is guaranteed that the solution exists.

/*Example*/

Given:
	n = 4
	index = 2
	maxSum = 6
Expected output: 2
Explanation: nums = [1, 2, 2, 1] is the array which satisfies all conditions. And nums[index] = 2. There is one more array nums = [1, 2, 2, 1] which satisfies all conditions with the same maximized nums[index] = 2.

Solution:

The value of each element in nums is at least 1. So we will subtract n (number of elements) from maxSum, so that the condition nums[i] > 0 is relaxed to nums[i] >= 0. We will see later the reason for doing this.

Let indexedValue be the value at index of nums, that is, indexedValue = nums[index]. Let maxIndexedValue be the maximum value of indexedValue possible which satisfies all the given four conditions. So if we are asked:

● Is there an array nums with indexedValue greater than maxIndexedValue such that it satisfies all the conditions except condition 4? The answer is definitely no.
● Is there an array nums with indexedValue less than or equal to maxIndexedValue such that it satisfies all the conditions except condition 4? The answer is definitely yes.
In such a scenario, we can perform a binary search over the values of indexedValue. The values of indexedValue range from 0 to maxSum (after subtracting n). The binary search will help us to find indexedValue which satisfies condition 4. (say this task is #task_1)
Now, for a given value of indexedValue, we will try to generate an array nums (say this task is #task_2). The generated array must satisfy the first three conditions. We need to generate any one of that array such that its sum is less than or equal to maxSum. The Arithmetic Progression sequence on both sides is the optimal way to do this. For example, let’s say index = 3, maxSum = 10, indexedValue = 4, n = 6
● nums = 0 1 2 3 2 1
this is AP around the index 3 with value 3, the sum of the array is 9 which <= 10.
● nums = 0 2 2 3 2 1
this is AP around the index 3 with value 3, the sum of the array is 10 which <= 10.
● nums = 0 2 3 3 2 1
this is AP around the index 3 with value 3, the sum of the array is 11 which > 10.

When we select the array to be AP on both sides of the index, we can deterministically say that if the array is possible or not because there will be no other possible array with a sum less than the AP array.

We know, that if we are given the first and the last term of an AP, the sum of this AP is:-
sum = (first_term + last_term) * no_of_terms / 2

Thus for #task_2 we need not generate the whole array, actually. We need to find the first_term on both sides of indexedValue and sum them according to the above formula and check it against maxSum. Now take an example with indexedValue = 3, index = 5, and n = 7, the following is the array with AP:

nums = 0 0 0 1 2 3 2
indices = 0 1 2 3 4 5 6
On the right side, the first_term is 2. We can find it using:-
indexedValue - no_of_terms_on_right_side
= indexedValue - (n - 1 - index)

On the left side, the first_term is 1. We can find it using:
indexedValue - no_of_terms_on_left_side
= indexedValue - index (this results in negative, so we can choose 0 instead.
= Math.max(indexedValue - index, 0)

Here it doesn’t matter if the first term is 0 or 1. The sum remains the same. That’s why we subtracted n from maxSum at the start of the solution to relax the condition 1 to include 0. So we will include the max thing to the right side too. So:

first_term_on_right_side = Math.max(indexedValue - (n - 1 - index), 0)
first_term_on_left_side = Math.max(indexedValue - index, 0)

class Solution {
    public int maxValue(int n, int index, int maxSum) {
        maxSum -= n;
        
        int left = 0;
        int right = maxSum;
        
        while (left < right) {
            int mid = (left + right + 1) / 2;
            
            if (sumWithIndexedValue(mid, index, n) > maxSum) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        
        return left + 1;
    }
    
    private long sumWithIndexedValue(int indexedValue, int index, int n) {
        long leftMin = Math.max(indexedValue - index, 0);
        long leftSum = apSum(indexedValue, leftMin);
        
        long rightMin = Math.max(indexedValue - (n - 1 - index), 0);
        long rightSum = apSum(indexedValue, rightMin);
        
        return leftSum + rightSum - indexedValue;
    }
    
    private long apSum(long a, long b) {
        return (a + b) * (a - b + 1) / 2;
    }
    
}

Time complexity- O(log(maxSum))
Space complexity- O(1)

This question shows the interviewer that the developer is able to work with Java strings and arrays.

Let f(str) frequency of the lexicographically smallest character in non-empty string str. For example f(“fbeb”) = 2 because the lexicographically smallest character is “b”, which has a frequency of 2.

You are given two string array queries and words. For each string queries[i] in queries, find the number of strings in words such that f(queries[i]) < f(word) for each word in words.
Your task is to return an array answer such that answer[i] is the answer to the ith query.

/*Example*/

Given:
queries = ["bbb", "cc"]
words = ["a", "aa", "aaa", "aaaa"]
Expected output: [1, 2]
Explanation: For the first query only f("bbb") < f("aaaa"). For the second query both f("cc") < f("aaa") and f("cc") < f("aaaa").

Solution:

The first step will be finding the frequencies for each string in queries and words. We will implement the function findFreqSmallestChar corresponding to f(str), that is, findFreqSmallestChar will find the frequency of the lexicographically smallest character in the given string. We will collect these frequencies in queriesFreqs and wordsFreqs for queries and words respectively.
Then we will sort the wordsFreqs array.

Now, for each query = queries[i], we will count the required number of words. There will be queryFreq = queriesFreqs[i] corresponding to query. The answer to the query will be equal to the count of frequencies in wordsFreqs which are greater than queryFreq. Let the answer to the query is queryAnswer. To find queryAnswer, we will do the binary search over wordsFreqs and find the smallest index idx such that queryFreq > wordsFreqs[idx]. Then, queryAnswer = wordsFreqs.length - idx. We will do this for each query.

class Solution {
    public int[] numSmallerByFrequency(
        String[] queries,
        String[] words
    ) {
        
        List<Integer> queriesFreqs = new ArrayList<>();
        List<Integer> wordsFreqs = new ArrayList<>();
        
        for(String query : queries) {
            int freq = findFreqSmallestChar(query);
            queriesFreqs.add(freq);
        }

        for(String word : words) {
            int freq = findFreqSmallestChar(word);
            wordsFreqs.add(freq);
        }
    
        Collections.sort(wordsFreqs);
        int res[] = new int[queriesFreqs.size()];
        
        for(int i = 0; i < queriesFreqs.size(); i++) {
            res[i] = countWordsWithGreaterFreq(
                queriesFreqs.get(i),
                wordsFreqs
            );
        };
        
        return res;
    }
 
    private int findFreqSmallestChar(String str) {
        int freqSmallestChar = 0;
        char smallestChar = str.charAt(0);

        for (int i = 0; i < str.length(); i++) {
            char currChar = str.charAt(i);
            
            if (currChar > smallestChar) continue;
            if (currChar == smallestChar) freqSmallestChar++;
            else {
                smallestChar = currChar;
                freqSmallestChar = 1;
            }
        }
        
        return freqSmallestChar;
    }
 
    private int countWordsWithGreaterFreq(
        int queryFreq,
        List<Integer> wordsFreqs
    ) {
        
        int left = 0;
        int right = wordsFreqs.size();
    
        while(left < right) {
            int mid = left + (right - left) / 2;
            
            if (wordsFreqs.get(mid) > queryFreq) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        int queryAnswer = wordsFreqs.size() - left;
        return queryAnswer;
    }
    
}

n = length of queries array
m = length of words array
Time complexity- O((m + n) logm)
Space complexity- O(m + n)

This question focuses on Java intervals and the ability of the developer to perform a binary search.

You are given an array intervals, where intervals[i] = [starti, endi] and each starti is unique.
The right interval for an interval i is an interval j such that startj >= endi and startj is minimized. Your task is to return an array of right interval indices for each interval i. If no right interval exists for interval i, then put -1 at index i.

/*Example*/

Given intervals = [[3, 4], [2, 3], [1, 2]]
Expected output: [-1, 0, 1]
Explanation: There is no right interval for [3, 4].
The right interval for [2, 3] is [3, 4].
The right interval for [1, 2] is [2, 3].

Solution:

We will sort the interval array according to the start of the intervals. Then, for each interval, we do a binary search over the sorted intervals to find the corresponding right interval.

Since after sorting the original index for a particular interval is lost, we store the original indices corresponding to all the intervals in the map startIdxMap. The keys of startIdxMap will be the start of intervals and the values will be corresponding original indices.

When we find the right interval in the sorted intervals, we find the corresponding original indices for both the current interval and the right interval in intervalOriginalIdx and rightIntervalOriginalIdx respectively. We put the answers at the correct places in the answer array and return the array.

class Solution {
    public int[] findRightInterval(int[][] intervals) {
        Map<Integer, Integer> startIdxMap = new HashMap();
    
        for(int idx = 0; idx < intervals.length; idx++){
            int start = intervals[idx][0];
            startIdxMap.put(start, idx);
        }
    
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    
        int answer[] = new int[intervals.length];
    
        for (int i = 0; i < intervals.length; i++) {
            int intervalEnd = intervals[i][1];
    
            int left = 0;
            int right = intervals.length;
            int rightStart = Integer.MIN_VALUE;
    
            while(left < right) {
                int mid = (left + right) / 2;
                
                if (intervals[mid][0] >= intervalEnd) {
                    right = mid;
                    rightStart = intervals[mid][0];
                } else {
                    left = mid + 1;
                }
            }
        
            int intervalOriginalIdx =
                startIdxMap.get(intervals[i][0]);
 
            if (rightStart == Integer.MIN_VALUE) {
                // no right interval
                answer[intervalOriginalIdx] = -1;
            } else {
                int rightIntervalOriginalIdx =
                    startIdxMap.get(rightStart);
                answer[intervalOriginalIdx] =
                    rightIntervalOriginalIdx;   
            }
        }
        
        return answer;
    }
    
}

n = number of intervals
Time complexity- O(n logn)
Space complexity- O(n)

This interview question shows the developer's skills with Java ranges and functions.

You are on a planet Earth in a different universe. You discovered a different kind of magnetic force between some special balls when placed in special baskets. If two balls are placed in two buckets separated by distance d, then the magnetic force between the balls is equal to d units.

You are given the positions of n baskets in array baskets. You also have m balls. Your task is to place these m balls in these buckets such that the minimum magnetic force between any two balls is maximum.

/*Example*/

Given baskets = [1, 2, 3, 4, 7]		m = 3
Expected output: 3
Explanation: After placing balls in baskets 1, 4, 7, the magnetic force between these balls 3, 3, 6. So the minimum magnetic force between any two balls is 3. We can not place balls in any other way such that the minimum magnetic force is larger.

Solution:

First of all, we sort the positions of the given baskets. Then we will do the binary search over these positions.

Let’s say countBallsWithMinForce is a function that counts the number of balls that can be placed in the given baskets such that the minimum magnetic force between those balls is at least minimumForce. We seek to find the largest minimumForce such that,
countBallsWithMinForce(minimumForce) == m

That is, we need to find such a minimum magnetic force so that the number of balls that can be placed with that force is exactly equal to m.
● If the countBallsWithMinForce(minimumForce) > m , we have too many balls placed, so minimumForce is too small.
● If the countBallsWithMinForce(minimumForce) < m , we don't have enough balls placed, so minimumForce is too large.
Because countBallsWithMinForce(minimumForce) is monotonically decreasing with respect to minimumForce, we can use binary search to find the optimal minimumForce.

class Solution {
    public int maxDistance(int[] baskets, int m) {
        int n = baskets.length;
        Arrays.sort(baskets);
    
        int left = 1;
        int right = baskets[n - 1] - baskets[0] + 1;
    
        while(left < right) {
            int mid = (left + right) / 2;
            
            int ballsCountWithForceMid = 
                countBallsWithMinForce(mid, baskets);
        
            if (ballsCountWithForceMid < m) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left - 1;
    }
 
    private int countBallsWithMinForce(
        int minimumForce,
        int[] baskets
    ) {
        int count = 1;
        int currPosition = baskets[0];
    
        for (int i = 1; i < baskets.length; i++) {
            int force = baskets[i] - currPosition;
            if (force < minimumForce) continue;
            
            count++;
            currPosition = baskets[i];
        }
        
        return count;
    }

}

n = number of baskets
Time complexity- O(n (logn + log(max position))
Space complexity- O(1)

This interview question concentrates on the developer's ability to work with Java arrays.

There was a sorted integer array nums of length n containing distinct numbers. nums is rotated by a pivot index k to form rotatedNums array, that is, rotatedNums = [nums[k], nums[k + 1], ..., nums[n - 1], nums[0], nums[1], ..., nums[k - 1]]. For example, if nums = [0, 1, 2, 3, 4, 5, 6, 7] and k = 3, then rotatedNums = [3, 4, 5, 6, 7, 0, 1, 2].

You are given rotatedNums and an integer target. Your task is to search the index of the target in rotatedNums. If it does not exist, return -1.

/*Example*/

Given rotatedNums = [4, 5, 6, 7, 0, 1, 2]	target = 0
Expected output: 4

Solution:

The given array rotatedNums is not fully sorted. So we can not do a binary search directly.
Consider rotatedNums = [3, 4, 5, 6, 7, 0, 1, 2].

● If we wish to search 1, we can adjust the array to [-Infinity, -Infinity, -Infinity, -Infinity, -Infinity, 0, 1, 2] and then we can perform binary search easily.
● If we wish to search 5, we can adjust the array to [3, 4, 5, 6, 7, Infinity, Infinity, Infinity], and then we can perform a binary search easily.

The catch is that we won't actually adjust the array. We will calculate this on the fly. Let’s call the rotated subarray [3, 4, 5, 6, 7] as the left side and [0, 1, 2] as the right side. A number is on the left side if num >= rotatedNums[0], otherwise it is on the right side.

If the target and rotatedNums[mid] are on the same side, we just take num = rotatedNums[mid]. If they are not on the same side, we take num to be equal to either Integer.MAX_VALUE or Integer.MIN_VALUE. If the target is on the left side, the num will be Integer.MAX_VALUE, otherwise it will be Integer.MIN_VALUE.

class Solution {
    public int search(int[] rotatedNums, int target) {
        int left = 0;
        int right = rotatedNums.length - 1;
        boolean isTargetOnLeftSide = target >= rotatedNums[0];
        
        while(left < right) {
            int mid = left + (right - left) / 2;
            int num = rotatedNums[mid];
            boolean isNumOnLeftSide = num >= rotatedNums[0];
        
            if (isTargetOnLeftSide != isNumOnLeftSide) {
                num = isTargetOnLeftSide 
                    ? Integer.MAX_VALUE 
                    : Integer.MIN_VALUE;
            }
            
            if (num >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return rotatedNums[left] == target ? left : -1;
    }
    
}

n = number of baskets
Time complexity- O(logn)
Space complexity- O(1)

This interview question shows the interviewer that the developer is able to work with Java indexes.

There are some houses and heaters placed on a horizontal line. You are given the positions of the houses and heaters in array houses and heaters. All the heaters have the same radius up to which they can heat. A house can be warmed if it is within the radius range of at least one heater. Your task is to find the minimum radius of the heaters such that all houses can be warmed.

/*Example*/

Given	houses = [1, 2, 3, 6]		heaters = [1, 4]
Expected output: 2
Explanation: The heater at position 1 can warm houses at positions 1 and 2 requiring a radius of 1. The heater at position 4 can warm houses at positions 3 and 6 requiring a radius of 2. Thus all the houses are warmed. If we increase the radius, all the houses will still be warmed. But if we decrease the radius of the second heater to 1, the house at position 6 can not be warmed. So the minimum radius is 2.

Solution:

First of all, we will sort the heaters array. Then, for each house, we will find the nearest heater so that it can be warmed.

To find the nearest heater for a house with position housePos, we will binary search over heaters array to find the nearest heater on the right side to housePos. We use the findRightHeater function for this. It will return the index of the right heater. If the right heater does not exist (it means there is no heater on the right side of housePos), it returns -1.

When we have the index of the right heater (in rightHeaterIdx), we find the positions of the right and left heaters. If any heater does not exist, we use Infinity to represent it at infinity position and can’t be used to warm the house. These positions are stored in rightHeaterPos and leftHeaterPos. Then we find the distances of these heaters from the house and find the distance of the nearest heater in nearestHeaterDist. Then we update the result accordingly. And return it at the end.

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        
        int result = Integer.MIN_VALUE;
    
        for (int housePos : houses) {
            int rightHeaterIdx = findRightHeater(
                housePos, 
                heaters
            );
        
            int rightHeaterPos = findRightHeaterPos(
                rightHeaterIdx,
                heaters
            );
            
            int leftHeaterPos = findLeftHeaterPos(
                rightHeaterIdx,
                heaters
            );
        
            int rightHeaterDist = Math.abs(housePos - rightHeaterPos);
            int leftHeaterDist = Math.abs(housePos - leftHeaterPos);
        
            int nearestHeaterDist = Math.min(
                rightHeaterDist,
                leftHeaterDist
            );
            result = Math.max(result, nearestHeaterDist);
        }
        
        return result;
    }
    
    private int findRightHeaterPos(
        int rightHeaterIdx, 
        int[] heaters
    ) {
        if (rightHeaterIdx == -1) return Integer.MAX_VALUE;
        return heaters[rightHeaterIdx];
    }
 
    private int findLeftHeaterPos(int rightHeaterIdx, int[] heaters) {
        if (rightHeaterIdx == 0) return Integer.MAX_VALUE;
        if (rightHeaterIdx == -1) return heaters[heaters.length - 1];
        return heaters[rightHeaterIdx - 1];
    }
 
    private int findRightHeater(int housePos, int[] heaters) {
        int left = 0;
        int right = heaters.length;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (heaters[mid] >= housePos) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        if (left == heaters.length) return -1;
        return left;
    }

}

n = number of houses
m = number of heaters
Time complexity- O((m + n) logm)
Space complexity- O(1)

This question focuses on the developer's skills working with Java binary search.

A scientist has an index h if h of their n papers have at least h citations each, and the other n − h papers have no more than h citations each.

You are given n citations of a scientist in array citations in sorted order. Your task is to find the h-index of the scientist.

/*Example*/

Given: citations = [0, 1, 4, 5, 6]
Expected output: 3
Explanation: The scientist has published 5 papers and they have received 0, 1, 4, 5, and 6 citations respectively. Out of these papers, 3 papers have received at least 3 citations and then the rest two papers have less than 3 citations.

Solution:

The task is very simple with binary search. For a given index idx, the number of citations after this index (including itself) is equal to citations.length - idx. We will find first such index idx such that citations[idx] >= citations.length - idx, that is, we will find a first paper which has citations (citations[idx]) greater than or equal to the number of papers which has equal to the greater number of citations (the required condition for h-index).

class Solution {
    public int hIndex(int[] citations) {
        int citationsCount = citations.length;
        int left = 0;
        int right = citations.length;
        
        while(left < right) {
            int mid = left + (right - left) / 2;
            
            if (citations[mid] >= citationsCount - mid) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return citationsCount - left;
    }

}

n = number of citations
Time complexity- O(logn)
Space complexity- O(1)

This question focuses on Java ranges and binary searches.

You work in an office. Your commute to the office from your home by train. You have to change many trains to go to the office. The distance covered by each train is given in array distances in km. After the first train, you take the second train, then the third, and so on. The last train reaches your office. Every train departs when the previous train has arrived. It departs only on integer hours. For example, if the first train arrives at 1.5 hours, you must wait for an additional 0.5 hours, and the second train will depart at 2 hours.

All the trains travel at the same speed. You are given a floating-point number of hours. Your task is to find the minimum speed of trains (integer in kilometers per hour) such that you can reach the office within hours. If you can’t reach the office on time, return -1.

/*Example*/

Given: distances = [1, 3, 2]		hour = 2.7
Expected output: 3
Explanation:
●	The first train takes 1/3 = 0.333 hours.
●	We wait for 0.667 hours. Then the second train departs. It takes 3/3 = 1 hours. So total 2 hours.
●	We are at integer hour. So the third train departs immediately. It takes 2/3 = 0.667 hours. Total time is 2.667 hours. 
Constraint
●	hours will have at most two digits after the decimal point.
●	the required speed won’t exceed 107.

Solution:

Since the required speed ranges between 1 and 107, we can do a binary search over this range. For each speed that we are checking, we will find the required to reach the office using the function findTimeRequired. If we can reach this speed (time <= hours), we narrow our search from the right end, otherwise we narrow our search from the left end.

class Solution {
    public int minSpeedOnTime(int[] distances, double hours) {
        int left = 1;
        int right = (int)Math.pow(10, 7) + 1;
        int ans = -1;
    
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            double time = findTimeRequired(distances, mid);
            if (time <= hours) {
                right = mid;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return ans;
    }
    
    private double findTimeRequired(int[] distances, double speed) {
        int lastDistIdx = distances.length - 1;
        double time = 0;
        
        for (int i = 0; i < lastDistIdx; i++) {
            time += Math.ceil(distances[i] / speed);
        }
        
        time += distances[lastDistIdx] / speed;
        return time;
    }

}

n = number of trains
m = maximum speed of train i.e. 107
Time complexity- O(n logm)
Space complexity- O(1)

This question shows the developer's ability to work with Java binary search.

There was a sorted integer array nums of length n containing distinct numbers. nums is rotated by a pivot index k to form rotatedNums array, that is, rotatedNums = [nums[k], nums[k + 1], ..., nums[n - 1], nums[0], nums[1], ..., nums[k - 1]]. For example, if nums = [0, 1, 2, 3, 4, 5, 6, 7] and k = 3, then rotatedNums = [3, 4, 5, 6, 7, 0, 1, 2].

You are given the array rotatedNums. Your task is to find the smallest number in the array.

/*Example*/

Given rotatedNums = [3, 4, 5, 1, 2]
Expected output: 1

Given rotatedNums = [11, 13, 15, 17]
Expected output: 11

Solution:

If the first number is smaller than the last number, it means it is the original array. So we return the first number directly.

Otherwise, we do a binary search over the array. Let's take the example of a rotated array [5, 6, 7, 8, 1, 2, 3, 4]. Let’s call the parts [5, 6, 7, 8] and [1, 2, 3, 4] the left and the right parts respectively. All the numbers in the right part are smaller than the first number in the array and smaller than or equal to the last number. We need to find the smallest number in the right part. We will do a binary search over the whole array. If the number at index mid is:

● smaller than the first number in the array and smaller than or equal to the last number, it is in the right part. So we shrink the right pointer,
● otherwise, it is the left part. So we shrink the left pointer.
After the loop ends, the left pointer will be the index of the minimum number.

class Solution {
    public int findMin(int[] rotatedNums) {
        int lastNumIndex = rotatedNums.length - 1;
        
        // rotated by k = 0 or n
        // which means it the original array
        if (rotatedNums[0] < rotatedNums[lastNumIndex]) {
            return rotatedNums[0];
        }
        
        int left = 0;
        int right = lastNumIndex;
    
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            boolean isSmallerThanFirst = 
                rotatedNums[mid] < rotatedNums[0];
            boolean isSmallerThanLast = 
                rotatedNums[mid] <= rotatedNums[lastNumIndex];
        
            if (isSmallerThanFirst && isSmallerThanLast) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return rotatedNums[left];
    }

}

Time complexity- O(logn)
Space complexity- O(1)

This question allows the interviewer to see the developer's skills working with Java arrays and binary searches.

You are given a sorted integer array arr. You are also given two integers k and num. Your task is to find k closest integers to num in arr. The closest integers to an integer num are num - 1 and num + 1; the next closest integers are num - 2 and num + 2 and so on. The result should be sorted in ascending order.

An integer a is closer to num than another integer b if:
● either |num - a| < |num - b|,
● or |num - a| == |num - b| and a < b

/*Example*/

Given	arr = [1, 2, 3, 4, 5]		k = 5		x = 3
Expected output: [1, 2, 3, 4]

Constraint
●	1 <= k <= arr.length

Solution:

Let’s say we have an index idx. Consider two numbers arr[idx] and arr[idx + k]. Let us assume that the numbers arr[idx], arr[idx + 1], …., arr[idx + k - 1] are the closest numbers to num. Now if these are the closest numbers to num, the average of the extreme numbers (arr[idx] and arr[idx + k - 1]) should be at least num and minimum possible. It means num should be at the middle element of the two extremes. If the average is less than num, it will be close to the larger extreme. If the average is much more than num, it will be close to the smaller extreme. Neither range will constitute the closest elements to num.

arr[idx] ..... num ..... arr[idx + k - 1]
(num is almost at middle)
arr[idx] .. num ... average ..... arr[idx + k - 1]
(average is much higher than num, so num is close to the left extreme)
arr[idx] ..... average ... num .. arr[idx + k - 1]
(average is lower num, so num is close to the right extreme)

More formally,
average = (arr[idx] + arr[idx + k - 1]) / 2
average >= num
and the average is the minimum possible.
As we increase idx, the average increases; as idx decreases the average decreases. So we can binary search over all the indexes (hence the array) to find the minimum idx such that The average is at least num.

After we find such an index (after the loop, left will be such index), we create a new array from arr from index left to left + k (exclusive). For this, we use the Arrays.copyOfRange method. The function creates a new array from the array between the passed indices. This takes three arguments:-
1. sourceArray :- This provides the source array to copy from.
2. startIndex (optional, defaults to 0):- This specifies the index from where to start copying.
3. endIndex :- This specifies the index at where to end copying exclusively.

After creating the subarray we convert it to a list by iterating through it and adding each element.

class Solution {
    public List<Integer> findClosestElements(
        int[] arr, 
        int k, 
        int num
    ) {
        int left = 0;
        int right = arr.length - k;
    
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (2 * num <= arr[mid] + arr[mid + k]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        List<Integer> closestElements = new ArrayList<>();
        
        for (int i = left ; i < left + k; i++) {
            closestElements.add(arr[i]);
        }
        
        return closestElements;
    }

}

Time complexity- O(logn + k)
Space complexity- O(1)

This question allows the interviewer to see the developer's skills working with Java arrays and binary searches.

You are given an array of positive integer weights. You need to initialize a data structure with given weights. The method pickIndex randomly returns an index between 0 and weights.length - 1. The probability of indices is proportional to their weight in the weights array. That is, the probability for the index is equal to weights[i] / sum (weights).

For example, if weights = [2, 3]. When pickIndex is called, the probability of getting index 0 is 2 / (2 + 3) = 40% while the probability of getting index 1 is 3 / (2 + 3) = 60%.

Your task is to provide an implementation for this DS such that pickIndex has minimum time complexity.

class Solution {
    public Solution(int[] w) {
        
    }
    
    public int pickIndex() {
        
    }
}

Solution:

We will find the accumulated weights (also known as prefix sums) in accWeights. For example if weights = [2, 5, 3, 4], then accWeights = [2, 7, 10, 14]. We will do this in the constructor function.
The max accumulated weight in the above array is 14 (that is the last element of the accWeights). In the pickIndex method, we will, first, find a random number between ranges [1, maxAccWeight]. Let this be randomAccWeight. Then using binary search, we will search the first such index in accWeights at which the accumulated weight is greater than or equal to randomAccWeight. That will be our required index.

How does this work?
Let weights = [2, 5, 3, 4], then accWeights = [2, 7, 10, 14]
Now, we get a random integer in the range [1, 14] with equal probability and is stored in randomAccWeight. There are 14 total possible values for randomAccWeight. Then we binary search this in the accumulated weights. So for the values of randomAccWeight, the searched indices will be:-
randomAccWeight searched index probability of getting the index
in the range
----------------------------------------------------------------------
[1, 2] 0 2 / 14
[3, 7] 1 5 / 14
[8, 10] 2 3 / 14
[11, 14] 3 4 / 14
As it can be seen that, the probability of getting an index is proportional to corresponding weight.

class Solution {
    
    private int accWeights[];

    public Solution(int[] weights) {
        int accWeights[] = new int[weights.length];
        accWeights[0] = weights[0];
 
        for (int i = 1; i < weights.length; i++) {
            accWeights[i] = accWeights[i - 1] + weights[i];
        }
        
        this.accWeights = accWeights;
    }
    
    public int pickIndex() {
        int left = 0;
        int right = accWeights.length - 1;
        int maxAccWeight = accWeights[right];
        int randomAccWeight = getRandomInt(1, maxAccWeight);
 
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (accWeights[mid] >= randomAccWeight) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }

    private int getRandomInt(int min, int max) {
        double random = Math.random() * (max - min + 1) + min;
        return (int) Math.floor(random);
    }
    
}

Space complexity of the data structure- O(n)
Time complexity of constructor- O(n)
Space complexity of constructor- O(n)
Time complexity of pickIndex O(logn)
Space complexity of pickIndex O(1)