2 JavaScript Advanced Level Binary Search Interview Questions & Answers
Below is a list of our JavaScript Advanced 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 JavaScript 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 - 1
Solution:
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.
For num = 25,n = 6 (62 > 25), so our answer will be 5
For num = 40, n = 7 (72 > 40), so our answer will be 6
/**
* @param {number} num
* @return {number}
*/
function findSquareRoot(num) {
let n = 0
while (n * n <= num) n++
return n - 1
};
Time complexity - O(num)
Space complexity - O(1)
As the number can be as large as 109, the linear search approach is inefficient.
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).
/**
* @param {number} num
* @return {number}
*/
function findSquareRoot(num) {
if (num === 0) return 0
if (num === 1) return 1
let left = 0
let right = num
while (left < right) {
const mid = Math.floor((left + right) / 2)
if (mid * mid > num) right = mid
else left = mid + 1
}
return left - 1
};
Time complexity - O(log num)
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 2^p × 2^p) is greater than num, then the square of greater powers of 2 (for example 2^p + ^1 × 2^p + ^1) will also be greater than num.
More formally,
if (2^a)^2 > num
then (2^a + ^n)^2 > num, for all n >= 0
Let res be our answer. We will loop through all powers of 2 from 2^0 to 2^32, and find the first power whose square is greater than num (say 2^x > num such that 2^x - ^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 i^th bit, then will check if the square(res | 2^i) > 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, (2^2)^2 < num and (2^3)^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
/**
* @param {number} num
* @return {number}
*/
function findSquareRoot(num) {
if (num === 0) return 0
if (num === 1) return 1
let mostSignificantBit = 0
let mostSignificantBitPower = powOfTwo(mostSignificantBit)
// find first the power of 2 which is greater than num
while(mostSignificantBitPower * mostSignificantBitPower <= num) {
mostSignificantBit++
mostSignificantBitPower = powOfTwo(mostSignificantBit)
}
mostSignificantBit -= 1
let otherBit = mostSignificantBit - 1
let res = powOfTwo(mostSignificantBit)
// check other bits one by one starting
// from `mostSignificantBit - 1`
while(otherBit >= 0) {
let trialResult = res | powOfTwo(otherBit)
if(trialResult * trialResult <= num) {
res = trialResult
}
otherBit--
}
return res
}
function powOfTwo(i) {
return Math.pow(2, i)
// using bit operation is more efficient than calling Math.pow
// return 1 << i
}
Time complexity - O(32) = O(1)
Space complexity - O(1)
Written by Jennie Taylor on May 22nd, 2021
2. Find the path with minimum effort.
This question focuses on the developer's knowledge of JavaScript binary search and loops.
You are given 2-D matrix heights for size n x m. A hiker is at the top-left cell (0, 0) (cells are 0-indexed). Her target is to reach the bottom-right of the cell (n - 1, m - 1). She can move either up, down, left or right from a cell. Your task is to find minimum effort to reach the destination cell. The effort of a path to the destination is the maximum absolute difference of their heights between two consecutive cells of the path.
/*Example*/
Given matrix-
[[1, 2, 2],
[3, 8, 2],
[5, 3, 5]]
expected output = 2
explanation:- The path 1 -> 2 -> 2 -> 2 -> 5 has an effort of 3.
The path 1 -> 3 -> 5 -> 3 -> 5 has an effort of 2.
Definitions:
â— maximum absolute difference for the path 3 -> 4 -> 2 is maxOf(4 - 3, 4 - 2) = maxOf(1, 2) = 2
â— maximum absolute difference for the path 1 -> 3 -> 5 -> 3 -> 5 is maxOf(2, 2, 2, 2) = 2
â— maximum absolute difference for the path 1 -> 2 -> 2 -> 2 -> 5 is maxOf(1, 0, 0, 3) = 3
Constraints:
â— 1 <= n, m <= 100
â— 1 <= heights[i][j] <= 106
Solution:
We can use binary search to solve this problem. If we carefully observe, below the minimum effort, there is no way to reach the destination. Let’s say the minimum effort required is min. If we are asked:
â— Can we reach our destination with an effort of less than min? The answer is definitely no.
â— Can we reach our destination with an effort 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 a binary search from 0 to max-possible. The value of max-possible will be the maximum height of a cell in the given matrix. We have a function that can reach answers the two questions above. It will return true if the effort passed is greater than or equal to min, false otherwise.
In the 'canReach' function, we will do DFS to at least one path using which we can reach the destination with given effort. We will maintain a 2-D array visited to check which nodes we have visited. We will start from the cell (0, 0). We will explore all the neighboring cells of the current cell viz. up, down, left, and right. While exploring a neighbouring cell, we will check if it is visited earlier. If it is not visited, we will check if the absolute height difference between the current cell and the neighboring cell is permitted using an impermissible function (i.e. check if less than given effort). If it is not permitted, we will not do DFS on this cell, because any path will not be possible through this cell. If it is permitted, we will do DFS on this cell and will explore its neighboring cells. If we have reached the destination cell, we simply return true, because there was at least one path using which we could reach the destination with given effort.
/**
* @param {number[][]} heights
* @return {number}
*/
function findMinimumEffort(heights) {
let left = 0
let right = 0
for (const row of heights) {
right = Math.max(right, Math.max(...row))
}
while(left < right) {
let mid = (left + right) / 2
mid = Math.floor(mid)
if (canReach(mid, heights)) {
right = mid
} else {
left = mid + 1
}
}
return left
}
function canReach(effort, heights) {
const n = heights.length
const m = heights[0].length
let isPossible = false
// initialize visited matrix of size n x m will all false
const visited = new Array(n)
for (let i = 0; i < n; i++) {
visited[i] = new Array(m).fill(false)
}
// check if the consecutive cells effort less than
// or equal to passed effort
function isPermissible(i1, j1, i2, j2) {
const h1 = heights[i1][j1]
const h2 = heights[i2][j2]
return Math.abs(h1 - h2) <= effort
}
function dfs(i, j) {
// we have reached the destination cell
// return true
if (i === n - 1 && j === m - 1) {
return true
}
visited[i][j] = true
const up = i - 1
const down = i + 1
const left = j - 1
const right = j + 1
// check if we can visit the up cell
if (
up >= 0 &&
!visited[up][j] &&
isPermissible(i, j, up, j)
) {
isPossible = isPossible || dfs(up, j)
}
// check if we can visit the down cell
if (
down < n &&
!visited[down][j] &&
isPermissible(i, j, down, j)
) {
isPossible = isPossible || dfs(down, j)
}
// check if we can visit the left cell
if (
left >= 0 &&
!visited[i][left] &&
isPermissible(i, j, i, left)
) {
isPossible = isPossible || dfs(i, left)
}
// check if we can visit the right cell
if (
right < m &&
!visited[i][right] &&
isPermissible(i, j, i, right)
) {
isPossible = isPossible || dfs(i, right)
}
return isPossible
}
return dfs(0, 0)
}
Time complexity- O(n * m * log(106))
Space complexity- O(n * m)
Written by Jennie Taylor on May 22nd, 2021