2 Javascript Beginner Level Bit Manipulation Interview Questions & Answers
Below is a list of our Javascript Beginner Level Bit Manipulation 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. Convert binary to decimal.
This interview question concentrates on the use of JavaScript binary and bit manipulations.
You are given a linked list. The list represents a binary number i.e. the value of each node is either 1 or 0. The head of the node is the most significant bit and the last node is the least significant bit of the binary number. Your task is to determine the decimal representation of the number.
/*Example*/
Given list:- 1 -> 1 -> 0 -> 1
Expected output:- 13Solution:
Approach I (using simple arithmetic):
We know if we have a binary number with n number of digits, its decimal equivalent can be found using-
decimal = sum of (bit_i * 2i) i from 0 to n - 1
where bit_i is the bit at the ith position, and 0th bit is least significant and (n - 1)th is the most significant bit.
We are given bits from most-significant to least-significant. When we encounter the next bit, we can multiply the previous number by 2 and add the bit. Take 1101, for example, let num be final number
=> initialize num be most significant bit i.e num = 1
=> next bit is 1, multiply num by 2 and add 1 to it
=> num = 2 * 1 + 1 = 3
=> next bit is 0, multiply num by 2 and add 0 to it
=> num = 2 * 3 + 0 = 6
=> next bit is 1, multiply num by 2 and add 1 to it
=> num = 2 * 6 + 1 = 13
=> all bits are traversed. So num is our final answer.
class ListNode {
constructor(val, next) {
this.val = val || 0
this.next = next || null
}
}
/**
* @param {ListNode} head
* @return {number}
*/
function listToDecimal(head) {
if (!head) return 0
let num = head.val
while(head.next !== null) {
head = head.next
num = 2 * num + head.val
}
return num
}Time complexity- O(n)
Space complexity- O(1)
Approach II (bit manipulations):
We know that when we left-shift a number 1 time, it is multiplied by 2. For example, if the number is 3, then-
=> 3 = 11 (in binary)
=> left shift by 1 => 110 which is 6 (in decimal) (3 * 2)
Thus we can replace multiply by 2 in the previous approach with the left shift operation.
Next, after every left shift, the least significant will always be 0. Also, head.val is a single bit. So instead of arithmetic add, we can use bitwise OR. In general, bitwise operations are much faster compared to normal arithmetic operations like addition or subtraction.
class ListNode {
constructor(val, next) {
this.val = val || 0
this.next = next || null
}
}
/**
* @param {ListNode} head
* @return {number}
*/
function listToDecimal(head) {
if (!head) return 0
let num = head.val
while(head.next !== null) {
head = head.next
num = (num << 1) | head.val
}
return num
}Time complexity- O(n)
Space complexity- O(1)
Written by S. Kumar on May 22nd, 2021
2. Can you answer each query and return in an array?
This interview question shows the developer's ability to work with JavaScript operators.
You are given an array arr of positive integers of length n. You are also given an array queries where queries[i] = [li, ri]. To answer queries[i], you XOR all the numbers arr from index li to ri (both inclusive), that is, arr[li] XOR arr[li + 1] XOR … XOR arr[ri]. Your task is to answer each query and return their result in an array.
/*Example*/
Given:
arr = [1, 3, 4, 8]
queries = [[0, 1], [1, 2], [0, 3] ,[3, 3]]
Expected:- [2, 7, 14, 8]Solution:
We will create an array prefixXors of length n. prefixXors[i] is the XOR of all numbers in arr from index 0 to i. Thus,
prefixXors[i] = prefixXors[i - 1] ^ arr[i]
Now finding the XOR of numbers between range li and ri is easy:
ans for ith query = XOR of numbers from index li to ri
= (XOR of numbers from index li to ri)
^ (XOR of numbers from index 0 to li - 1)
^ (XOR of numbers from index 0 to li - 1) // because a ^ a = 0
= (XOR of numbers from index 0 to ri)
^ (XOR of numbers from index 0 to li - 1)
= prefixXors[ri] ^ prefixXors[li - 1]
/**
* @param {number[]} arr
* @param {number[][]} queries
* @return {number[]}
*/
function xorQueries(arr, queries) {
const n = arr.length
const prefixXors = new Array(n)
prefixXors[0] = arr[0]
for (let i = 1; i < n; i++) {
prefixXors[i] = prefixXors[i - 1] ^ arr[i]
}
const result = []
for (const [l, r] of queries) {
let ans = prefixXors[r]
ans ^= l === 0 ? 0 : prefixXors[l - 1]
result.push(ans)
}
return result
}Time complexity- O(n + queries.length)
Space complexity- O(n)
Written by S. Kumar on May 22nd, 2021