15 Python Intermediate Level Binary Search Interview Questions & Answers
Below is a list of our Python Intermediate 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. What is the smallest divisor with a given limit?
This question focuses on the developer's knowledge of Python binary search and arrays.
You are given an array of integers 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
def smallestDivisor(nums, limit):
# choose the range for making a binary search
mini, maxi = 1, max(nums)
while mini < maxi:
mid = (mini + maxi) // 2
# if mid passes the limit or not
if isLessOrEqLimit(mid, nums, limit):
maxi = mid
else:
mini = mid + 1
return mini
def ceil_divison(num, den):
''' returns ceil division of two numbers '''
return (num + den - 1) // den
def isLessOrEqLimit(divisor, nums, limit):
'''
returns true or false based on the limit and divisor
whether the final sum after division is under limit
or not
'''
divison_result = [ ceil_divison(num,divisor) for num in nums]
return sum(divison_result) <= limitTime complexity- O(n log(max_of_nums))
Space complexity- O(1)
Written by S. Kumar on May 22nd, 2021
2. What are the minimum number of days to make bouquets?
This question focuses on the developer's knowledge of Python 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.
def canMake(limit, bloomDay, m, k):
'''
return True if we can make m bouquets with
k adj flower within 'limit' days
'''
bouquetsMade, adjFlowers = 0, 0
for day in bloomDay:
# if there is a day which is not reached yet then
# mark the adjacent flower count to 0
if day > limit:
adjFlowers = 0
continue
# if day is reached then increase the bouquetsMade
# and adjacent flower
bouquetsMade += (adjFlowers + 1) // k
adjFlowers = (adjFlowers + 1) % k
return bouquetsMade >= m
def minDays(bloomDay, m, k):
if m * k > len(bloomDay):
return -1
mini, maxi = 1, max(bloomDay)
while mini < maxi:
mid = (mini + maxi) // 2
if canMake(mid, bloomDay, m, k):
maxi = mid
else:
mini = mid + 1
return miniTime complexity- O(n log(max_of_bloomDay))
Space complexity- O(1)
Written by S. Kumar on May 22nd, 2021
3. How can you minimize the maxOperations penalty?
This question focuses on the developer's knowledge of Python 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.
def minimumPenalty(nums, maxOperations):
left, right = 1, max(nums)
while left < right:
mid = (left + right) // 2
if canDo(mid, nums, maxOperations):
right = mid
else:
left = mid + 1
return left
def division(a, b):
'''
returns one less in ceil division of a/b
To get number of operations require to break 'a'
having 'b' as penalty
'''
return (a + b - 1) // b - 1
def canDo(penalty, nums, maxOperations):
'''
returns True if we can make given 'penalty'
possible within 'maxOperations'
'''
operationsRequired = 0
for ele in nums:
operationsRequired += division(ele, penalty)
return operationsRequired <= maxOperationsTime complexity- O(n log(max_of_nums))
Space complexity- O(1)
Written by S. Kumar on May 22nd, 2021
4. Find a single occurring integer in the given sorted array.
This question shows the developer's ability to use Python search effectively.
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 = 4Solution:
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 even indices and will compare its value with the value at the next odd 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 current even index is the required single integer.
def findSingle(nums: List[int]) -> int:
for i in range(0, len(nums) - 1, 2):
if nums[i] != nums[i + 1]:
return nums[i]
return nums[-1] # last elementTime 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.
def findSingle(nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
# make it even index
if mid % 2: mid -= 1
if nums[mid] == nums[mid + 1]:
left = mid + 2
else:
right = mid
return nums[left]Time complexity- O(log n)
Space complexity- O(1)
Written by S. Kumar on May 22nd, 2021
5. Create a key-value store with timestamp.
This interview question focuses on the developer's understanding of Python methods and their uses.
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:
def __init__(self):
"""
Initialize your data structure here.
"""
# TODO
def set(self, key: str, value: str, timestamp: int) -> None:
# TODO
def get(self, key: str, timestamp: int) -> str:
# TODOSolution:
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:
def __init__(self):
"""
Initialize your data structure here.
"""
self.store = {}
def getTimedValues(self, key):
if key not in self.store:
self.store[key] = []
return self.store[key]
def set(self, key: str, value: str, timestamp: int) -> None:
timedValues = self.getTimedValues(key)
timedValues.append([timestamp, value])
def get(self, key: str, timestamp: int) -> str:
timedValues = self.getTimedValues(key)
left, right = 0, len(timedValues)
while left < right:
mid = (left + right) // 2
if timedValues[mid][0] > timestamp:
right = mid
else:
left = mid + 1
if right == 0:
return ""
return timedValues[right - 1][1]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)
Written by S. Kumar on May 22nd, 2021
6. What is the maximum value at a given index in a bounded array?
This question concentrates on the developer's skills with Python 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 determine 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)
def apSum(a, b):
return (a + b) * (a - b + 1) // 2
def sumWithIndexedValue(indexedValue, index, n):
leftMin = max(indexedValue - index, 0)
leftSum = apSum(indexedValue, leftMin)
rightMin = max(indexedValue - (n - 1 - index), 0)
rightSum = apSum(indexedValue, rightMin)
return leftSum + rightSum - indexedValue
def findMaxValue(n, index, maxSum):
maxSum -= n
left, right = 0, maxSum
while left < right:
mid = (left + right + 1) // 2
if (sumWithIndexedValue(mid, index, n) > maxSum):
right = mid - 1
else:
left = mid
return left + 1Time complexity- O(log(maxSum))
Space complexity- O(1)
Written by S. Kumar on May 22nd, 2021
7. Compare strings by frequency of the smallest character.
This question concentrates on Python frequencies and sorting arrays.
Let f(string) frequency of the lexicographically smallest character in a non-empty string. 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(string), 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.
def findFreqSmallestChar(string):
freqSmallestChar = 0
smallestChar = string[0]
for char in string:
if char == smallestChar:
freqSmallestChar += 1
elif char < smallestChar:
smallestChar = char
freqSmallestChar = 1
return freqSmallestChar
def countWordsWithGreaterFreq(queryFreq, wordsFreqs):
left, right = 0, len(wordsFreqs)
while left < right:
mid = (left + right) // 2
if wordsFreqs[mid] > queryFreq:
right = mid
else:
left = mid + 1
queryAnswer = len(wordsFreqs) - left
return queryAnswer
def numSmallerByFrequency(queries, words):
‘’’
Input: queries -> List[str], words -> List[str]
Output: List[int]
‘’’
queryFreqs = [findFreqSmallestChar(query) for query in queries]
wordsFreqs = [findFreqSmallestChar(word) for word in words]
wordsFreqs.sort()
result = []
for query in queryFreqs:
result.append(countWordsWithGreaterFreq(query, wordsFreqs))
return result
n = length of queries array
m = length of words array
Time complexity- O((m + n) logm)
Space complexity- O(m + n)
Written by S. Kumar on May 22nd, 2021
8. Can you find the right interval indices for each interval?
This interview question shows the developer's ability to work with Python sorting and intervals.
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.
def findRightInterval(intervals: List[List[int]]) -> List[int]:
‘’’
Input: intervals -> List[List[int]]
Output: List[int]
‘’’
startIdxMap = {}
for i, interval in enumerate(intervals):
start = interval[0]
startIdxMap[start] = i
intervals.sort()
len_intervals = len(intervals)
answer = [0] * len_intervals
for i in range(len_intervals):
intervalEnd = intervals[i][1]
left, right = 0, len_intervals
while left < right:
mid = (left + right) // 2
if intervals[mid][0] < intervalEnd:
left = mid + 1
else:
right = mid
intervalOriginalIdx = startIdxMap[intervals[i][0]]
if left >= len_intervals:
answer[intervalOriginalIdx] = -1
else:
rightIntervalStart = intervals[left][0]
rightIntervalOriginalIdx = \
startIdxMap[rightIntervalStart]
answer[intervalOriginalIdx] = rightIntervalOriginalIdx
return answern = number of intervals
Time complexity- O(n logn)
Space complexity- O(n)
Written by S. Kumar on May 22nd, 2021
9. What is the magnetic force between two balls?
This question concentrates on Python sorting and binary search.
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.
def countBallsWithMinForce(minimumForce, baskets):
count = 1
currPosition = baskets[0]
for i in range(1, len(baskets)):
force = baskets[i] - currPosition
if force < minimumForce:
continue
count += 1
currPosition = baskets[i]
return count
def maxDistance(baskets, m):
‘’’
Input: baskets -> List[int], m -> int
Output: int
‘’’
n = len(baskets)
baskets.sort()
left, right = 1, baskets[n - 1] - baskets[0] + 1
while left < right:
mid = (left + right) // 2
ballsCountWithForceMid =
countBallsWithMinForce(mid, baskets)
if (ballsCountWithForceMid < m):
right = mid
else:
left = mid + 1
return left - 1n = number of baskets
Time complexity- O(n (logn + log(max position))
Space complexity- O(1)
Written by S. Kumar on May 22nd, 2021
10. How do you search in a rotated sorted array?
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: 4Solution:
NOTE:- float(‘inf’) is represented as Inf and float(‘-inf’) is represented as -Inf.
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 [-Inf, -Inf, -Inf, -Inf, -Inf, 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, Inf, Inf, Inf], 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 Inf or -Inf. If the target is on the left side, the num will be Inf, otherwise, it will be -Inf.
def search(rotatedNums: List[int], target: int) -> int:
‘’’
Input: rotatedNums -> List[int], target -> int
Output: int
‘’’
left, right = 0, len(rotatedNums) - 1
isTargetOnLeftSide = target >= rotatedNums[0]
while left < right:
mid = (left + right) // 2
num = rotatedNums[mid]
num = rotatedNums[mid]
isNumOnLeftSide = num >= rotatedNums[0]
if isTargetOnLeftSide != isNumOnLeftSide:
if isTargetOnLeftSide:
num = float('inf')
else:
num = float('-inf')
if num >= target:
right = mid
else:
left = mid + 1
if rotatedNums[left] == target:
return left
return -1n = number of baskets
Time complexity- O(logn)
Space complexity- O(1)
Written by S. Kumar on May 22nd, 2021
11. Find the minimum radius of the heaters where all houses can be warmed.
This question shows the developer's ability to work with Python binary search.
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.
def findRightHeaterPos(rightHeaterIdx, heaters):
if rightHeaterIdx == -1:
return float('inf')
return heaters[rightHeaterIdx]
def findLeftHeaterPos(rightHeaterIdx, heaters):
if rightHeaterIdx == 0:
return float('inf')
if rightHeaterIdx == -1:
return heaters[-1]
return heaters[rightHeaterIdx - 1]
def findRightHeater(housePos, heaters):
left, right = 0, len(heaters)
while left < right:
mid = (left + right) // 2
if heaters[mid] >= housePos:
right = mid
else:
left = mid + 1
if left == len(heaters):
return -1
return left
def findRadius(houses, heaters):
‘’’
Input: houses -> List[int], heaters -> List[int]
Output: int
‘’’
heaters.sort()
result = float('-inf')
for housePos in houses:
rightHeaterIdx = findRightHeater(
housePos,
heaters
)
rightHeaterPos = findRightHeaterPos(
rightHeaterIdx,
heaters
)
leftHeaterPos = findLeftHeaterPos(
rightHeaterIdx,
heaters
)
rightHeaterDist = abs(housePos - rightHeaterPos)
leftHeaterDist = abs(housePos - leftHeaterPos)
nearestHeaterDist = min(
rightHeaterDist,
leftHeaterDist
)
result = max(result, nearestHeaterDist)
return resultn = number of houses
m = number of heaters
Time complexity- O((m + n) logm)
Space complexity- O(1)
Written by S. Kumar on May 22nd, 2021
12. What is the minimum speed to arrive on time?
This question shows the developer's knowledge of Python binary search.
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 hour. So total 2 hours.
â— We are at integer hour. So the third train departs immediately. It takes 2/3 = 0.667 hours. The 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.
def ceil_divison(num, den):
return (num + den - 1) // den
def findTimeRequired(distances, speed):
lastDistIdx = len(distances) - 1
time = 0
for i in range(lastDistIdx):
time += ceil_divison(distances[i], speed)
time += distances[lastDistIdx] / speed
return time
def minSpeedOnTime(distances, hours):
‘’’
Input: distance -> List[int], hours -> float
Output: int
‘’’
left, right = 1, (10**7) + 1
ans = -1
while left < right:
mid = (left + right) // 2
time = findTimeRequired(distances, mid)
if time <= hours:
right = mid
ans = mid
else:
left = mid + 1
return ansn = number of trains
m = maximum speed of train i.e. 107
Time complexity- O(n logm)
Space complexity- O(1)
Written by S. Kumar on May 22nd, 2021
13. Find the minimum in a rotated sorted array.
This question shows the developer's ability to work with Python binary search and 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 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: 11Solution:
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.
def findMin(rotatedNums):
‘’’
Input: rotatedNums -> List[int]
Output: int
‘’’
lastNumIndex = len(rotatedNums) - 1
# original array without rotation
if rotatedNums[0] < rotatedNums[lastNumIndex]:
return rotatedNums[0]
left, right = 0, lastNumIndex
while left < right:
mid = (left + right) // 2
isSmallerThanFirst = rotatedNums[mid] < rotatedNums[0]
isSmallerThanLast = \
rotatedNums[mid] <= rotatedNums[lastNumIndex]
if isSmallerThanFirst and isSmallerThanLast:
right = mid
else:
left = mid + 1
return rotatedNums[left]Time complexity- O(logn)
Space complexity- O(1)
Written by S. Kumar on May 22nd, 2021
14. How do you find the K closest elements?
This question shows the developer's ability to work with Python binary search and index.
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 = 4 x = 3
Expected output: [1, 2, 3, 4]
Constraint
â— 1 <= k <= arr.lengthSolution:
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 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 list slicing techniques. This creates a new array from the array between the passed indices. This takes two arguments:
1. startIndex (optional, defaults to 0):- This specifies the index from where to start copying.
2. endIndex (optional, defaults to the length of the array):- This specifies the index at where to end copying exclusively.
def findClosestElements(arr, k, num):
‘’’
Input: arr -> List[int], k -> int, num -> int
Output: List[int]
‘’’
left, right = 0, len(arr) - k
while left < right:
mid = (left + right) // 2
if (2 * num <= arr[mid] + arr[mid + k]):
right = mid
else:
left = mid + 1
return arr[left : left + k]Time complexity- O(logn + k)
Space complexity- O(1)
Written by S. Kumar on May 22nd, 2021
15. What is the random pick with weight?
This question shows the developer's ability to work with Python binary search and weights.
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:
def __init__(self, w: List[int]):
pass
def pickIndex(self) -> int:
passSolution:
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 range [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 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 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.
from random import randint
class Solution:
def __init__(self, weights):
‘’’
Input: weights -> List[int]
Output: None
‘’’
n = len(weights)
accWeights = [0] * n
total = 0
for i in range(n):
total += weights[i]
accWeights[i] = total
self.accWeights = accWeights
def pickIndex(self):
‘’’
Input: None
Output: int
‘’’
left, right = 0, len(self.accWeights) - 1
maxAccWeight = self.accWeights[right]
# a random number in between 1 to maxAccWeight
randomAccWeight = randint(1, maxAccWeight)
while left < right:
mid = (left + right) // 2
if self.accWeights[mid] >= randomAccWeight:
right = mid
else:
left = mid + 1
return leftSpace 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)
Written by S. Kumar on May 22nd, 2021