No results found for the specified position. 2 JavaScript Advanced Level Binary Search Interview Questions

MockQuestions

JavaScript Advanced Level Binary Search Mock Interview

To help you prepare for your JavaScript Advanced Level Binary Search interview, here are 2 interview questions and answer examples.

Get More Information About Our JavaScript Advanced Level Binary Search Interview Questions

Question 1 of 2

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 on May 22nd, 2021

Next Question

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.

  • 2. Find the path with minimum effort.