3 Python Beginner Level Binary Search Interview Questions & Answers
Below is a list of our Python Beginner Level Binary Search interview questions. Click on any interview question to view our answer advice and answer examples. You may view 5 answer examples before our paywall loads. Afterwards, you'll be asked to upgrade to view the rest of our answers.
1. Find the square root of an integer.
This interview question shows the developer's ability to work with Python search and manipulation.
You are given an integer num, your task is to find the square root of num. You need to return only the integer part of the square root and truncate the decimal digits. You can not use the language-built in sqrt method.
/*Examples*/
num = 25
Expected output- 5
num = 40
Expected output- 6
Explanation- the decimal of 6.324.. has been truncated and only the integer part is kept.
Constraints:
0 <= num <= 231 - 1Solution:
Approach I (linear search):
The first approach that comes to mind is linear search. We can iterate over all numbers from 0 to num and find if its square is greater than num or not. As soon as we find a number (say n) whose square is strictly greater than num, then n - 1 will be our answer.
def findSquareRoot(n):
i = 0
while i * i <= n:
i += 1
return i - 1Time complexity- O(√n)
Space complexity- O(1)
Approach II - Binary search:
We can use binary search to solve the problem. We need to make some observations for this.
If there is a number (say a) and its square is less than num, then the square of all the numbers less than a will also be less than num.
More formally,
if a2 < num
then b2 < num, for all b < a (CASE I)
The same is true for a number whose square is greater than num. i.e.
if c2 > num
then d2 > num, for all d > c (CASE II)
In such a scenario we can use binary search. We will have two numbers (pointers) left and right corresponding to numbers a and c, and then take a mid and compare its square with num.
If its square of mid is greater than num, we discard all numbers greater than mid, that is we set right = mid;
and if the square of mid is less than or equal to num, we discard all numbers less than or equal to mid, that is we set left = mid + 1. Here we are discarding the square equal to num case too. The reason is that when the loop exits, left will be the smallest number whose square is greater than num (same as n in the linear search approach).
def findSquareRoot(n):
if n == 0: return 0
if n == 1: return 1
left, right = 0, int(n)
while left < right:
mid = (left + right) // 2
sq = mid * mid
if sq == n:
return mid
elif sq < n:
left = mid + 1
else:
right = mid
return left-1Time complexity- O(logn)
Space complexity- O(1)
Approach III - Bit manipulation:
The basic idea for bit manipulation is borrowed from the previous approach. Instead of taking any number a, we will see it in powers of 2 (thus bits).
Note- all bit positions are 0-indexed from least significant to most significant. Thus the least significant bit is 0 and the most significant bit is 31 (in 32-bit integer).
If the square of a certain power of 2 (say 2p × 2p) is greater than num, then the square of greater powers of 2 (for example 2p + 1 × 2p + 1) will also be greater than num.
More formally,
if (2a)2 > num
then (2a + n)2 > num, for all n >= 0
Let res be our answer. We will loop through all powers of 2 from 20 to 232, and find the first power whose square is greater than num (say 2x > num such that 2x - 1 <= num). Then res will have (x - 1)th bit equal to 1. In this way, we will get the most significant bit of our answer res (because other more significant bits are all zero).
When the most significant bit is found, finding other bits is easy. We will apply the same trick to other bits too. We will set other bits (from x - 1 to 0) to 1 separately in res, and check if its square is greater than num or not— if we are checking the ith bit, then will check if the square(res | 2i) > num. If it is greater, that bit will be 0 in the answer, and if it is lesser, that bit will be 1 in the answer.
Let's take an example for num = 42
Most significant bit will be at position 2 i.e. res = 4 (100 in binary)
because, (22)2 < num and (23)2 > num
Now we check other bits starting from position 1 (one less than the most significant bit)
Is 110 * 110 > num ? No, so the bit at position 1 will be set in res-
res = 110
Now check position 0
Is 111 * 111 > num ? Yes, so bit at position 0 will be unset in res
res = 110
So our final answer will be 110 in binary or 6 in decimal
def powOfTwo(i):
return 1 << i
def findSquareRoot(n):
if n == 0: return 0
if n == 1: return 1
# take most significant digit x and 2^x
mostSignBit = 0
mostSignBitPower = powOfTwo(mostSignBit)
# find least power of 2 whose square is greater then 'n'
while mostSignBitPower * mostSignBitPower <= n:
mostSignBit += 1
mostSignBitPower = powOfTwo(mostSignBit)
# decrease MSB by 1 to get highest power of 2 whose
# square is less than 'n'
mostSignBit -= 1
# do same for other bits if MSB at bit x then we start with bit x-1
otherBit = mostSignBit - 1
# current result is the least power of 2 whose square
# is less than 'n'
res = powOfTwo(mostSignBit)
while otherBit >= 0:
# bit wise OR
# keep getting the power of two's and bitwitse OR
# them with previous result
trialResult = res | powOfTwo(otherBit)
# and see if result is still less than n if yes
# then update the result
if trialResult * trialResult <= n:
res = trialResult
otherBit -= 1
return resTime complexity- O(32) = O(1)
Space complexity- O(1)
Written by Jennie Taylor on May 21st, 2021
2. Find the highest peak in the mountain array.
This interview question concentrates on the developer's ability to work with Python search.
You are given an array of a mountain of size at least 3. Each element in the array represents the altitude of peaks in the mountain. There exists one peak in the array at index i such that
â— the peaks from index 0 to index i are in ascending order:
arr[0] < arr[1] < … < arr[i - 1] < arr[i]
â— and, the peaks from index i to index size - 1 are in descending order:-
arr[i] > arr[i + 1] > … > arr[size - 2] < arr[size - 1]
Your task is to find the index i of highest peak.
Example
â— arr = [0, 1, 0]
expected output = 1
â— arr = [0, 4, 2, 1]
expected output = 1Solution:
Approach I (Linear search):
Traverse the array linearly and return the index of the element from where the array starts decreasing.
def findHighest(arr):
n = len(arr)
for i in range(n - 1):
if arr[i] > arr[i + 1]:
return iTime complexity- O(n)
Space complexity- O(1)
Approach II (Binary search):
Make a binary search and find whether at mid can we get the condition where the array starts decreasing. If yes then that is the index we are looking after.
def findHighest(arr):
start = 0
end = len(arr) - 1
while start < end:
mid = (start+end) // 2
if arr[mid] < arr[mid + 1]:
start = mid + 1
else:
end = mid
return startTime complexity- O(logn)
Space complexity- O(1)
Written by Jennie Taylor on May 21st, 2021
3. What is the smallest letter greater than the target?
This question focuses on Python arrays and binary trees.
You are given an array of English lowercase letters in sorted order. You are also given a target letter. Your task is to find the smallest element in the array that is larger than the given target.
NOTE:- Letters do wrap around. It means if we don’t have any element in the array larger than the target, we return the smallest letter as the answer. See examples.
/*Example*/
letters = [“câ€, “gâ€, “lâ€]
target = “aâ€
expected output = “câ€
letters = [“câ€, “gâ€, “lâ€]
target = “câ€
expected output = “gâ€
letters = [“câ€, “gâ€, “lâ€]
target = “dâ€
expected output = “gâ€
letters = [“câ€, “gâ€, “lâ€]
target = “jâ€
expected output = “c†(letters wrapped around)
letters = [“câ€, “gâ€, “lâ€]
target = “kâ€
expected output = “c†(letters wrapped around)Solution:
Approach I (linear search):
Array is already sorted thus keep iterating and look for elements just larger than the target if found return that element immediately else wrap to the first element in the array. That first element will be the smallest since the array is sorted.
def findSmallestLargerLetter(arr, target):
for ele in arr:
if ele > target:
return ele
return arr[0]Time complexity- O(n)
Space complexity- O(1)
Approach II (binary search):
This is a lot like a search for integers. So we can use binary search for this. We need to care about the “wrap around†case. For handling this, we increase our search space. Instead of using arr.length - 1 for right pointer, we will use arr.length. The left pointer after the loop will be the index of the letter satisfying the given condition. When we can not find any letter greater than the target, the value of left will be arr.length after the loop. Then we take modulo to return the first element of the array.
def findSmallestLargerLetter(arr, target):
'''
Use binary search to get the required element in
sorted array
'''
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] > target:
right = mid
else:
left = mid + 1
return arr[left % len(arr)]Time complexity- O(logn)
Space complexity- O(1)
Written by Jennie Taylor on May 21st, 2021