16 Java Intermediate Level Bit Manipulation Interview Questions & Answers

Below is a list of our Java Intermediate 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. Find one singlet number.

This interview question concentrates on using JavaScript maps and operations.

You are given an array of 32-bit integers. Every number in the array occurs twice except one number. For example, in array [1, 2, 1, 3, 2], 1 and 2 occurs twice but 3 occurs only one time. You have to implement a function that finds and returns the single number in the given array.

/*Example*/

Given- [1, 2, 1, 3, 2]
Expected output 3

Given- [100, 48, 73, 48, 73, 41, 100]
Expected output- 41

Solution:

Approach I (using maps):

We can iterate over all the numbers and find their number of occurrences. We will store all the counts in a map. The numbers will be the keys in the map and their number of occurrences will be the values. After iterating over the array, we will find elements in the map with occurrence equal to 1.

For example, if the given array is [1, 2, 1, 3, 2], the resultant map will be-
{
1 -> 2 // 1 occurs two times
2 -> 2 // 2 occurs two times
3 -> 1 // 3 occurs one time
}

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> occurrences
            = new HashMap<Integer, Integer>();
        
        for (int num : nums) {
            int prevCount = occurrences.containsKey(num) ?
occurrences.get(num) : 0;
            occurrences.put(num, prevCount + 1);
        }
 
        int result = -1;
        for (int key : occurrences.keySet()) {
            if (occurrences.get(key) == 1) {
                result = key;
            }
        }
        
        return result;
    }

}

Time complexity - O(n)
Space complexity - O(n)

Approach II (using bit operations):

Since, all the elements occur twice except, we can xor all the elements together. We know that the bitwise xor of a number with itself is 0.
More formally,
a ^ a = 0, for every integer a
It is evident byâ€”
Lets say, a = 23 = (10111)binary
now xor-ing the a with itself,
10111
10111
00000

Thus, for example
1 ^ 2 ^ 1 ^ 3 ^ 2
= (1 ^ 1) ^ (2 ^ 2) ^ 3
= 0 ^ 0 ^ 3
= 3
(1 and 2 vanishes because they occur two times)

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
 
        for (int num : nums) {
            result = result ^ num;
        }
 
        return result;
    }
    
}

Time complexity - O(n)
Space complexity - O(1)

Along with decreasing space complexity, the solution is quite efficient, because it is using bitwise operations. Bitwise operations are faster than arithmetic operations like addition, multiplication, etc.

Written by S. Kumar on June 27th, 2021

2. How many 1's can you find?

This interview question concentrates on using Java strings and manipulation.

You are given a 32-bit integer. Your task is to calculate how many 1â€™s are there in the binary representation of the given number.

/*Example*/

Given: 23
expected output: 4
explanation: binary representation of 23 is 10111, which has 4 bits which are 1.

Given: 9
expected output: 2
explanation: binary representation of 9 is 1001, which has 2 bits which are 1.

Solution:

Approach I (using strings):

We will find the binary representation of the number in string form. This can easily be done using the Number.prototype.toString method. Number.prototype.toString takes one optional parameter- radix- an integer in the range 2 through 36 specifying the base to use for representing numeric values. n is a number here. So we will call the toString method on n passing 2 has argument because we want radix 2 (binary) representation.
Next, we will iterate over each character of the string and check if it is â€œ1â€. If it is â€œ1â€ we increase the count and then return the count after the loop.

public class Solution {
    // you need to treat n as an unsigned value
    public int count1Bits(int n) {
        int count = 0;
        String num = Integer.toBinaryString(n);
 
        for (char character : num.toCharArray()) {
            if (character == '1') count++;
        }
    
        return count;
    }
}

Time complexity- O(32) = O(1)
Space complexity- O(32) = O(1)

Approach II (using bit-manipulation):

We can make use of bitmasks to check if the binary representation has 1 at a particular position (0-indexed from right to left).

Letâ€™s say we have a binary number as n = 101100.

â— We want to check position 2. To check, we will bitwise-and the number with 000100 (1 is only at position 2). We will bitwise-and it with the number n. The result will be 000100
101100
000100 (bitwise and)
000100
The result is non-zero. We will say the number n has bit 1 at position 2.
â— Now, we want to check position 4. To check, we will bitwise-and the number with 010000 (1 is only at position 4). We will bitwise-and it with the number n. The result will be 000000
101100
010000 (bitwise and)
000000
The result is zero. We will say the number n does not have bit 1 at position 2.

We will do bitwise and with all the positions one by one from 0 to 31. If the result is non-zero, we will increase the counter by 1.
NOTE- the numbers 000100 and 010000 to check the position if they are 1 or 0 are known as bitmasks.

To generate the mask for a specific position, we will use the left-shift operator. The left shift operator shifts all the bits to left by a specified number.
So if we want to shift 1, we will do 1 << i.
â— if i = 0 then 1 << 0 = 1 i.e. no shift at all
â— if i = 1 then 1 << 1 = 10 i.e. shift 1 times
â— if i = 2 then 1 << 2 = 100 i.e. shift 2 times
â— if i = 3 then 1 << 3 = 1000 i.e. shift 3 times
â— if i = 6 then 1 << 6 = 1000000 i.e. shift 6 times

public class Solution {
    // you need to treat n as an unsigned value
    public int count1Bits(int n) {
        int count = 0;
    
        for (int i = 0; i < 32; i++) {
            int mask = 1 << i;
        
            if ((n & mask) != 0) {
                count++;
            }
        }
    
        return count;
    }
    
}

Time complexity- O(32) = O(1)
Space complexity- O(1)

Written by S. Kumar on June 27th, 2021

3. Is the number a power of 2 or not?

This interview question concentrates on using Java iteration and manipulation.

You are given a number num. Your task is to check if the number is a power of 2 or not.

/*Example*/

Given num = 32
Expected output = true

Given num = 40
Expected output = false

Solution:

Approach I (iterative):

We will divide the given number by 2 iteratively using a while loop. If it is not divisible by 2, we will break the loop. If the result after the loop is 1, we will say that the given number is divisible by 2; if not, we will say itâ€™s not divisible by 2.

Suppose num = 32
â— num = num / 2 = 16 (divisible by 2)
â— num = num / 2 = 8 (divisible by 2)
â— num = num / 2 = 4 (divisible by 2)
â— num = num / 2 = 2 (divisible by 2)
â— num = num / 2 = 1 (not divisible by 2, so break the loop)
â— the result after the loop is 1, so we say the given number 32 is a power of 2.

Now, suppose num = 40
â— num = num / 2 = 20 (divisible by 2)
â— num = num / 2 = 10 (divisible by 2)
â— num = num / 2 = 5 (not divisible by 2, so break the loop)
â— the result after the loop is 5, so we say the given number 40 is not a power of 2.

class Solution {
    public boolean isPowerOfTwo(int num) {
        if (num <= 0) return false;
 
        while (num % 2 == 0) num /= 2;
 
        return num == 1;
    }
    
}

Time complexity- O(log n)
Space complexity- O(1)

Approach II (using bit-manipulation):

We can use the fact is that, if a number is a power of 2, then its binary representation have only one bit which 1.
â— The binary representation of 32 = 100000. It has only one 1.
â— The binary representation of 40 = 101000. It has two 1â€™s. So itâ€™s not a power of two.
The other fact is that if we subtract 1 a number, then the bits to right the least significant set bit in the original number will all set to 1, and the bits to left will be unchanged. For example-
â— num = 00101000
after subtracting 1 => 00100111. The bit at position 3 ( the least significant set bit) was originally 1. After subtracting 1
â— it is changed to 0,
â— the bits to the right of this bit are all changed to 1,
â— the bits to the left of this bit are unchanged.
So if we take bitwise and of num and num - 1, we get the number with unchanged bits only. If that number is 0, it means there was only one bit with the value 1 (i.e. the power of 2).
â— 32 = 100000, 32 - 1 = 31 = 011111
100000
011111 (bitwise and)
000000 (result is zero so power of 2)
â— 40 = 101000, 30 - 1 = 39 = 100111
101000
100111 (bitwise and)
100000 (result is not zero so not a power of 2)

class Solution {
    public boolean isPowerOfTwo(int num) {
        if (num <= 0) return false;
 
        int numMinus1 = num - 1;
    
        return (num & numMinus1) == 0;
    }
    
}

Time complexity- O(1)
Space complexity- O(1)

Written by S. Kumar on June 27th, 2021

4. Generate an XOR array.

This interview question concentrates on using Java operators and iterative functions.

You are given an integer length. Your task is to generate a new array of size length that has the element at an index i equal to xor of all non-negative numbers less than equal to i.

/*Example*/

Given length = 5
expected array = [0, 1, 3, 0, 4]
at index 0 => array[0] = 0
at index 1 => array[1] = 0 ^ 1 = 1
at index 2 => array[2] = 0 ^ 1 ^ 2 = 3
at index 3 => array[3] = 0 ^ 1 ^ 2 ^ 3 = 0
at index 4 => array[4] = 0 ^ 1 ^ 2 ^ 3 ^ 4 = 4

Solution:

The solution is iterative. We will create a new array of size lengths. The first element (at index 0) will be 0. After that the element at index i will be xor i and the element at index i - 1.
More formally,
array[i] = 0, if i = 0
array[i] = array[i - 1] ^ i, if i > 0

class Solution {
    public int[] generatedArray(int length) {
        int array[] = new int[length];
        array[0] = 0;
 
        for (int i = 1; i < length; i++) {
            array[i] = array[i - 1] ^ i;
        }
 
        return array;
    }
    
}

Time complexity- O(length)
Space complexity- O(1)

Written by S. Kumar on June 27th, 2021

5. What is the maximum XOR for each query?

This question tests the developer's knowledge of Java operators and arrays.

You are given a sorted array nums of length n consisting of non-negative integers. You are also given an integer maximumBit. Your task is to perform n queries and store the result of each query in an array and return it.

In each query, you find an integer k, such that nums[0] XOR nums[1] XOR â€¦ XOR nums[nums.length - 1] XOR k is maximized. k must be less than 2maximumBit. This integer k is the answer to that query. After every query, you remove the last element nums.

/*Example*/

Given:	nums = [0, 1, 1, 3]		maximumBit = 2

Constraint
â—	1 <= maximumBit <= 20
â—	0 <= nums[i] < 2maximumBit

Solution:

From the constraints, we can see that the maximum value of nums[i] is 2maximumBit - 1. Letâ€™s call this maxNumber, that is, maxNumber = 2maximumBit - 1. The maximum value XOR of such numbers will also be maxNumber. Letâ€™s say maximumBit = 4. So maxNumber = 15 and nums[i] is in range [0, 15].

maxNumber = 01111
Letâ€™s say XOR of such numbers is 01101. It can be made equal to maxNumber by XORING it with 00010 which will be the required value of k.
01101
00010 (take bitwise xor) this will be our required k
01111 = maxNumber

We also know, if a XOR b = c, then a XOR c = b and b XOR c = a. Thus if, we have XOR of such numbers (01101 in the above example) and maxNumber, we can find k using k = xorOfNumbers XOR maxNumber
01101 = xorOfNumbers
01111 = maxNumber (take bitwise xor)
00010 = k

Now, let ans be an array of answers to the queries. ans[i] will be the answer to the ith query. It can be observed that
=> ans[0] will contain all numbers from nums while calculating XOR
=> ans[1] will contain all numbers from nums but last one while calculating the XOR
=> ans[2] will contain all numbers from nums but the last two while calculating the XOR
=> ans[i] will contain all numbers from nums but last i while calculating the XOR
=> ans[n - 2] will contain only the first two number from nums
=> ans[n - 1] will contain only the first number from nums

Thus if we have all numbers, the answer of the ith query is independent of any other query. So we can start from the last query (n - 1)st query. The XOR is in reverse order. In each step, we will XOR the numbers up to the current query and XOR it with maxNumber to get the required value of k.

class Solution {
    public int[] getMaximumXor(int[] nums, int maximumBit) {
        int n = nums.length;
        int maxNumber = (1 << maximumBit) - 1;
        int ans[] = new int[n];
        int xorOfNumbers = 0;
    
        for (int i = n - 1; i >= 0; i--) {
            xorOfNumbers ^= nums[n - i - 1];
            ans[i] = maxNumber ^ xorOfNumbers;
        }
    
        return ans;
    }
    
}

Time complexity- O(n)
Space complexity- O(1)

Written by S. Kumar on June 27th, 2021

6. Find the subsets.

This interview question shows the developer's ability to work with Java cascades and bitmasks.

You are given array nums of unique integers. Your task is to find all the subsets of nums in any order.
A subset of nums is a new collection of the integers with some, all, or none of the integers that are present in nums. So if nums = [1, 2], then possible subsets are:- [], [1], [2], [1, 2].

/*Example*/

Given nums = [1, 2, 3]
Expected output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Constraints
â—	1 <= nums.length <= 10

Solution:

Approach I (cascading):

Letâ€™s start with an empty set: []. The subset of this set is the empty subset itself. Now, take the integers one by one. At each step, we will take a new integer and create new subsets by adding this integer to already generated subsets.

Step 1: set = []
powerSet = [[]]
Step 2: set = [1]
previous powerSet = [[]]
powerSet = [[], [1]]
Step 3: set = [1, 2]
previous powerSet = [[], [1]]
powerSet = [[], [1], [2], [1, 2]]
Step 4: set = [1, 2]
previous powerSet = [[], [1], [2], [1, 2]]
powerSet = [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

The underlined subsets are the subsets from the previous step. The new subsets are created by adding the new integer to each of the previous subsets.

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> powerSet = new ArrayList<>();
        powerSet.add(new ArrayList<Integer>());
    
        for (int num : nums) {
            List<List<Integer>> newSubsets = new ArrayList<>();
        
            for (List<Integer> subset : powerSet) {
                List<Integer> newSubset = new ArrayList<>(subset);
                newSubset.add(num);
                newSubsets.add(newSubset);
            }
            
            powerSet.addAll(newSubsets);
        }
        
        return powerSet;
    }
}

Time complexity- O(n * 2n)
Total Space complexity- O(n * 2n)

Approach II (using bitmask):

Let len be the length of the array nums. The number of subsets for this array will be equal to 2len which can be calculated using (1 << len). We will take the bitmasks of length len each. There will be a total of 2len bitmasks. One particular bitmask represents a possible subset of the nums array. If the ith bit of the bitmask is 1, the ith integer is present in the corresponding subset, otherwise, it is absent.

Let nums = [1, 2, 3]
len = 3
number of subsets = 23 = 8
length of each bitmasks = len = 3
The subsets corresponding to each bitmask:
000 => [] // the empty set
001 => [3]
010 => [2]
011 => [2, 3]
100 => [1]
101 => [1, 3]
110 => [1, 2]
111 => [1, 2, 3]

Thus, we will generate all bitmasks between [0, 2len). To do this, we will run a loop from i = 0 to i = 2len - 1. These are decimal numbers. We convert them into binary strings using Integer.toBinaryString() method. One problem is that, if the bit mask is equal 2 or 3, the method will return a binary string of length 2 only. But we want all the bitmasks to be of equal length len.

For this, we will pad the binary string with leading zeros until their length is equal to len. To do this we will use the String.format() method to first add spaces in the starting and then use String.replace() add to replace the spaces with leading zeros.

After we get the bitmask in binary string format of length len, we will iterate over it, and if the ith bit is zero, we push the ith integer to the subset array, otherwise, we donâ€™t push it. After we get the subset for a particular bitmask, we push it to our powerSet.

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> powerSet = new ArrayList<>();
        int len = nums.length;
        int subsetCount = (1 << len);
    
        for (int mask = 0; mask < subsetCount; mask++) {
            String binary = Integer.toBinaryString(mask);
            binary = String.format("%1$" + len + "s", binary)
                .replace(' ', '0');
            
            List<Integer> subset = new ArrayList<>();
            
            for (int i = 0; i < len; i++) {
                if (binary.charAt(i) == '1') {
                    subset.add(nums[i]);
                }
            }
            
            powerSet.add(subset);
        }        
        return powerSet;
    }

}

Time complexity- O(n * 2n)
Total Space complexity- O(n * 2n)

Written by S. Kumar on June 27th, 2021

7. What are the minimum number of operations to reduce the integer to 1?

This question focuses on Java binary searches.

You are given a positive integer n. You perform a series of operations on the integer. In each operation, you do the following:

â— if n is even, you half the integer n, that is n = n / 2;
â— if n is odd, either increase or decrease n by 1.
Your task is to count the minimum number of operations required to reduce n to 1.

/*Example*/

Given: n = 8
Expected output: 3
Explanation: 8 -> 4 -> 2 -> 1

Given: n = 7
Expected output: 4
Explanation: 7 -> 8 -> 4 -> 2 -> 1

Constraints
â—	1 <= n < 231 - 1

Solution:

NOTE: (1010)2 represents the binary representations of a number.
The one well-established point is that if the number is even, we will half it. The problem comes when the number is odd. We have two choices either to increase it or decrease it. One of them will give us the minimum operations required.

If n = 1 = (001)2 we can reduce it further.
If n = 2 = (010)2 we can reduce it in the following way:-
2 -> 1
or in binary:- (010)2 -> (001)2 (1 operations)
If n = 3 = (011)2 we can reduce it in following way:-
(011)2 -> (010)2 -> (001)2 (2 operations)
If n = 4 = (100)2 we can reduce it in following way:-
(100)2 -> (010)2 -> (001)2 (2 operations)
If n = 8 = (1000)2 we can reduce it in following way:-
(1000)2 -> (0100)2 -> (0010)2 -> (0001)2 (3 operations)

While reducing either 3 or 4, it takes the same number of operations. While reducing 4, the first 1 bit is shifted to the left 2 times (the number of 0â€™s after 1). Similarly while reducing 8, the first 1 bit is shifted to the left 3 times (the number of 0â€™s after 1).

Now consider a number of the form xxx100...00 (where x represents either bit 0 or 1), that is, a number with at least one set bit and remaining trailing 0â€™s. We can repeatedly divide it by 2 until the least significant bit is 1, that is until the number is reduced to xxx1. The number operations to do so will be equal to numbers of 0â€™s that were to the right side of 1.

Now consider a number of the form x5x4x3111 (where the xi represents the ith bit which is either 0 or 1), that is, a number greater than 4 and n % 4 = 3. Since this number is odd, there are two options:

â— Increase:- x5x4x3111 -> x5x41000 -> x5x4 (4 operations)
â— Decrease:- x5x4x3111 // decrease
-> x5x4x3110 // divide by 2
-> x5x4x311 // decrease
-> x5x4x310 // divide by 2
-> x5x4x31 // decrease
-> x5x4x30 // divide by 2
-> x5x4x3

It can be seen that, if we take the first step as â€œincreaseâ€, the number is reduced to x5x4 in 4 operations, but if we take the first step as â€decreaseâ€, the number is still not reduced to x5x4 and the number of operations is already above 4. So when a number greater than 4 and n % 4 = 3 increasing the number is the optimal choice.

Now consider a number of the form x5x4x3101 (where the xi represents the ith bit which is either 0 or 1), that is, a number greater than 4 and n % 4 = 1. Since this number is odd, there are two options:

â— Decrease:- x5x4x3101 -> x5x4x3100 -> x5x4x3 (3 operations)
â— Increase:- x5x4x3101 // increase
-> x5x4x3110 // divide by 2
-> x5x4x311 // increase
-> x5x4100 // divide by 2
-> x5x410 // divide by 2
-> x5x41

It can be seen that, if we take the first step as â€œdecreaseâ€, the number is reduced to x5x4x3 in 3 operations, but if we take the first step as â€increaseâ€, the number is reduced to x5x41 and the number of operations is already above 3. So when a number greater than 4 and n % 4 = 1 decreasing the number is the optimal choice.

In nutshell, the following conditions hold:
If n = 1, operationsCount = 0
If n is even, divide n by 2 and increase operationsCount by 1.
If n is either 3 or n % 4 = 1, then decrease n by 1 and increase operationsCount by 1.
If n % 4 = 3, then increase n by 1 and increase operationsCount by 1.

All even numbers have their least significant bit equal to 0. So the bitwise AND of an even number with 1 will be equal to 0, that is, if (n & 1) is 0, then n is even.
We will use Long datatype to store n as in certain cases the left shift operator will cause the number to overflow an integer datatype.

To divide a number by 2, we will use the left shift operator. i number of left shifts divides the number by 2i. Since we want to divide by 2, we will left-shift one time only.
To decrease an odd number, we XOR the number with 1. This will make the least significant bit to 0, thus decreasing the number by 1.

NOTE: In the above discussion, while increasing a number we set x3 to 1 directly. Actually, if x3 were 1, then it would have 0, and carry would have been propagated. But this does not disturb our proof. So x3 is chosen to be 0 implicitly.

class Solution {
    public int integerReplacement(int n) {
        int operationsCount = 0;
        
        long num = n;
        
        while (num > 1) {
            operationsCount++;
            
            if ((num & 1) == 0) {
                num = num >> 1;
            } else if (num == 3 || (num & 0b11) == 1) {
                num = num ^ 1;
            } else {
                num++;
            }
        }
        
        return operationsCount;
    }

}

Time complexity- O(logn)
Space complexity- O(1)

Written by S. Kumar on June 27th, 2021

8. Check if a string contains all binary codes of size K.

This interview question shows the developer's ability to work with Java binary codes.

You are given binary string str. You are also given an integer k. Your task is to check whether str contains all the binary codes of length k.

/*Example*/

Given:		str = "00110110"		k = 2
Expected output: true
Explanation: The binary codes of length 2 are "00", "01", "10" and "11". These all present in the given string "00110110".

Given:		str = "0110"		k = 2
Expected output: false
Explanation: The binary code "00"  is not present in the given string.

Constraints
â—	1 <= k <= 20

Solution:

The length of the required binary codes is k. So there will be total of 2k codes from 0 to 2k - 1. We will check all these codes in the string. We will maintain array seenCodes to track which binary codes occur in the string.

We will have a sliding window of size k. First, we take the substring of str starting from index 0 of length k. We find the corresponding binary code using the parseInt method with radix = 2. We set seenCodes for this binary code to true. For str = "00110110", we take "00110110" (the substring shown in underlined).

Then we iterate over str starting from index k. For every index i, we find the new binary code of length k which ends at index i. This can be found by using the binary code from the previous binary code. In the previous binary code, remove the one bit from the left side and add the one bit str[i] to the right side. As illustrated below:

i = 2 => "00110110"
i = 3 => "00110110"
i = 4 => "00110110"
i = 5 => "00110110"
i = 6 => "00110110"
i = 7 => "00110110"

To remove and add a bit to a binary code, we will make use of bit operations. Let the previous binary code is â€œ10111â€ with k = 5 (the length of the binary codes). We want to remove one bit from the left and add one bit 1 to right. First, we will do a left shift operation. Now binaryCode = â€œ101110â€. To remove the bit from the left, we do bitwise AND with â€œ11111â€ (all bits ones of length k). Now binaryCode = â€œ01110â€. Now we add the bit to the right side using bitwise OR operation. Now binaryCode = â€œ01111â€.

After we have checked all the substrings of str, we will check if we have seen all the binary codes. To do this, we will iterate over seenCodes[] and perform AND operation over all the values. If all the elements are true, the value after iteration will be true, otherwise, it will be false.

class Solution {
    public boolean hasAllCodes(String str, int k) {
        if(str.length() < k) return false;
        
        int requiredCount = 1 << k;
        boolean seenCodes[] = new boolean[requiredCount];
        int allOne = requiredCount - 1;
        
        String binaryString = str.substring(0, k);
        int binaryCode = Integer.parseInt(binaryString, 2);
        seenCodes[binaryCode] = true;
        int codeCount = 1;
    
        for (int i = k; i < str.length(); i++) {
            int bit = str.charAt(i) - '0';
            binaryCode = binaryCode << 1;
            binaryCode = binaryCode & allOne;
            binaryCode = binaryCode | bit;
            
            if(!seenCodes[binaryCode]) {
                seenCodes[binaryCode] = true;
                codeCount++;
            }
        }
        
        return codeCount == requiredCount;
    }

}

Time complexity- O(n + 2k)
Space complexity- O(2k)

Written by S. Kumar on June 27th, 2021

9. What is the total hamming distance?

This question shows the developer's skills working with Java integers and iterations.

The hamming distance between two integers is the number of bit positions at which the corresponding bits differ.

You are given array nums of positive integers. Your task is to find the sum of the Hamming distances between all the pairs of integers in nums.

/*Example*/

Given nums = [4, 14, 2]
Expected output: 6
Explanation :
4 	= (0100)2
14 	= (1110)2
2 	= (0010)2
hammingDistance(4, 14) = 2
hammingDistance(4, 2) = 2
hammingDistance(14, 2) = 2

Constraints
â—	0 <= nums[i] <= 231 - 1

Solution:

All the integers have 32 bits. We will check all 32 bits of all the integers one by one. For ith bit, we will count the integers which have ith bit equal to 1 (variable setBitCount). If n is the number of integers in nums, then the ith bit contributes setBitCount * (n - setBitCount) to the total hamming distance.

class Solution {
    public int totalHammingDistance(int[] nums) {
        int total = 0;
        
        for (int bitPos = 0; bitPos < 32; bitPos++) {
            int setBitCount = 0;
            for (int num : nums) {
                setBitCount += (num >> bitPos) & 1;
            }
            
            total += setBitCount * (nums.length - setBitCount);
        }
        
        return total;
    }

}

Time complexity- O(32 * n)
Space complexity- O(1)

Written by S. Kumar on June 27th, 2021

10. Reduce the binary string to 1.

This question shows the developer's ability to work with Java binary strings and modifications.

You are given binary string str. You perform a series of operations on the number representations of the string. In each operation, you do the following:

â— if the number is even, you divide it by 2;
â— if the number is odd, you increase it by 1;
Your task is to count the number of operations required to reduce the number to 1.

/*Example*/

Given str = â€œ1101â€
Expected output: 6
Explanation: â€œ1101â€ is the binary representation of 13.
13 is odd. So increase by 1 to obtain 14.
14 is even. So divide it by 2 to obtain 7.
7 is odd. So increase by 1 to obtain 8.
8 is even. So divide it by 2 to obtain 4.
4 is even. So divide it by 2 to obtain 2.
2 is even. So divide it by 2 to obtain 1.
So a total of 6 operations.

Solution:

For division by 2, we right shift the binary string once.
If the least significant bit is â€œ0â€, we do the shift so one operation.
If the least significant bit is â€œ1â€, we add â€œ1â€, the bit becomes â€œ0â€, and then we do the right shift. So total 2 operations. During this addition, the carry is propagated to the left side.

Doing the right shift or adding 1 will modify the string. We can do it without modifying the string. We will iterate from the right side of the string.

1. If we have not encountered any â€œ1â€ yet, we increase the count by 1 for every â€œ0â€ bit.
2. When we encounter the first â€œ1â€, we set carry equal to 1, and increase count by 2.
3. Now the carry is 1.
a. When we encounter â€œ1â€, the carry from the previous bit will make it â€œ0â€. Thus one
operation will be needed for dividing by 2, and the carry is propagated further, that is,
carry will remain equal to 1.
b. When we encounter â€œ0â€, the carry from the previous bit will make it â€œ1â€. Thus we will add
â€œ1â€, which will make it â€œ0â€, then divide by 2, thus 2 operations. And the carrier is also
propagated further.

class Solution {
    public int numSteps(String s) {
        int result = 0;
        int carry = 0;
        
        for (int i = s.length() - 1; i > 0; i--) {
            int bit = s.charAt(i) - '0';
            
            // 0 + 1 = 1 odd, need  two steps
            // (add 1 and divided by 2), (carry = 1)
            // 1 + 0 = 1 odd, need  two steps
            // (add 1 and divided by 2), (carry = 0)
            if (bit + carry == 1) {
                result += 2;
                carry = 1;
            } else {
                // 0 + 0 = 0 even, need one step
                // (divided by 2), (carry = 0)
                // 1 + 1 = 0 even, need one step
                // (divided by 2), (carry = 1, 
                // and is propagated further)
                result++;
            }
        }
        
        return result + carry;
    }

}

Time complexity- O(n)
Space complexity- O(1)

Written by S. Kumar on June 27th, 2021

11. How do you compute the bitwise AND within the numbers range?

This interview question shows the developer's skills with Java binary searches.

You are given two non-negative integers left and right. Your task is to compute the bitwise AND of all the numbers between the range [left, right].

Constraint
â—	1 <= left, right <= 231 - 1
â—	left <= right

Solution:

First of all, let's focus on these two points:

1. For an ith bit, if there is at least one integer in the given range that has ith bit equal to zero, then the result will have the ith bit equal to 0.
2. If the integers left and right are equal, then the range has only one number which will also be the result. If they are not equal, then there is at least one odd and one even number which will make the 0th bit equal to 0 in the final result.

Now consider the given number is binary form left = 11010110 and right = 11011011.
For the 0th bit, there will be at least one number with the 0th bit equal to 0.
For the 1st bit, there will be at least one number with the 1st bit equal to 0.
For the 2nd bit, there will be at least one number with the 2nd bit equal to 0.
For the 3rd bit, there will be at least one number with the 3rd bit equal to 0.
For the 4th bit, all the numbers in the range have the 4th bit equal to 1.
For the 5th bit, all the numbers in the range have the 5th bit equal to 0.
For the 6th bit, all the numbers in the range have the 6th bit equal to 1.
For the 7th bit, all the numbers in the range have the 7th bit equal to 1.

Thus the result = 1101000. That is, the result will have bits 0-3 all equal to 0, but the bits 4-7 will be equal to the left common part of left and right. So we will count the number of bits where left and right differ and they are not equal yet (in variable countZeroBits). During counting, we left-shift left and right until they are equal. When left and right are equal, they will be equal to their left common part and the answer will be equal to left << countZeroBits.

 class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        if (left == 0) return 0;
        int countZeroBits = 0;
        
        while (left != right) {
            countZeroBits++;
            
            left = left >> 1;
            right = right >> 1;
        }
        
        return left << countZeroBits;
    }

}

Time complexity- O(32)
Space complexity- O(1)

Written by S. Kumar on June 27th, 2021

12. What is maximum product of word lengths?

This question focuses on the developer's skills working with Java iterations.

You are given an array of string words. Your task is to find the maximum value of words[i].length * words[j].length where words[i] and words[j] donâ€™t have any common letters. If no two such words exist, return 0.

/*Example*/

Given words = ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Expected output: 4
Explanation: The pairs of words with no common letters are:

Pairs				Product of lengths
"a" and "d". 			1 * 1 = 1
"a" and "cd". 		1 * 2 = 2
"a" and "bcd". 		1 * 3 = 3
"ab" and "d". 		2 * 1 = 2
"ab" and "cd". 		2 * 2 = 4
"abc" and "d". 		3 * 1 = 3
The maximum product is 4.

Solution:

We consider two words â€œequalâ€ if they have the same letters (irrespective of the frequency and order of the letters). So the words "ab", "abb", "ba", "aab", "ababaa" are all equal. So we will define the hash codes for equal words. The hash code is a 26-bit long integer. The 0th bit represents the letter "a", the 1st bit represents the letter "b", and so on up to the 25th bit which represents the letter "z". We set the ith bit to 1 in the hash code if the letter corresponding to that bit is present in the word at least once. Thus the hash codes for the following words are:

Word Hash code
"a" 00_0000_0000_0000_0000_0000_0001
"ab" 00_0000_0000_0000_0000_0000_0011
"abacty" 01_0000_1000_0000_0000_0000_0111
"pwelsutllupwwponnm" 00_0001_1100_1111_1000_0001_0000

In this way, we will find the hash code for each word and store it in the array hashCodes. Then we will iterate over each pair of the words array. If the two words have at least one letter which is common, we continue to the next pair. Otherwise, we find the product of their lengths and compare it with maxProduct.

The two words will have no letter common if the bitwise AND for their hash codes are equal to zero. If the bitwise AND is not equal to zero, they will have at least one letter common between them.

class Solution {
    public int maxProduct(String[] words) {
        List<Integer> hashCodes = new ArrayList<>();
        for(String word : words) {
            hashCodes.add(findHashCode(word));
        }
        
        int maxProduct = 0;
        
        for (int i = 0; i < words.length; i++) {
            String word1 = words[i];
            int code1 = hashCodes.get(i);
            
            for (int j = i + 1; j < words.length; j++) {
                boolean hasLettersCommon = 
                    (code1 & hashCodes.get(j)) != 0;
                if (hasLettersCommon) continue;
                
                int product = word1.length() * words[j].length();
                maxProduct = Math.max(maxProduct, product);
            }
        }
        
        return maxProduct;
    }
 
    private int findHashCode(String word) {
        int hashCode = 0;
        int charCodeOfA = 'a';
    
        for (int i = 0; i < word.length(); i++) {
            int charCode = word.charAt(i);
            int charIdx = charCode - charCodeOfA;
            hashCode = hashCode | (1 << charIdx);
        }
        
        return hashCode;
    }
    
}

Time complexity- O(n2)
Space complexity- O(n)

Written by S. Kumar on June 27th, 2021

13. Find the repeated DNA sequences.

This shows the interviewer the developer's ability to locate Java frequencies.

A DNA sequence consists of a sequence of series of nucleotides abbreviated as "A", "C", "G", and "T". You are given a DNA sequence. Your task is to find all the 10-letters long sequences (substrings) that occur more than once in the given DNA sequence.

/*Example*/

Given str = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Expected output: ["AAAAACCCCC", "CCCCCAAAAA"]

Constraints
â—	1 <= str.length <= 105

Solution:

We will count the frequency of each 10-letter long substring. We will store these frequencies in map frequencies. Then we will find those substrings which have a frequency greater than 1 and push them to the result array.

Now, let's do the space complexity analysis. Each substring is 10 letters long. In JavaScript, each character is 2-byte long (UTF-16 encoding). Thus each substring is 20 bytes. Now 4 bytes for storing the frequency. Thus a total of 24 bytes for one entry in the map.

We can improve the space required. One thing to know is that we have only four letters. And their representation in binary is:

"A" 0100_0001
"C" 0100_0011
"G" 0100_0111
"T" 0101_0100

It can be seen that the last three bits of each letter are different for each letter. We can use these three bits to store the specific letter. In a substring, there are 10 letters. So a total of 3 * 10 = 30 bits = 4 bytes (approx) will be used to store the substring which is 5x times less than the previous size of 20 bytes.

We will iterate over each letter in the given string. Let hashCode be the hash code for the current 10-letter long substring. We use this hashCode to store the corresponding frequencies. For the next substring, we need to remove one letter from the left side and the new letter to the right side.

1. To remove the one letter from the left side, we left-shift the hashCode by 3 bits (3 bits for one letter).
2. We need only the 30 bits (0th-29th bits). So we make the 30th and 31st bit to 0 by using bitwise AND with the bitmask 0x3FFF_FFFF.
3. Now we add the new letter to the right side. We find the last three bits of the letter and do bitwise OR to add the letter to hashCode.

class Solution {
    public List<String> findRepeatedDnaSequences(String str) {
        Map<Integer, Integer> frequencies = new HashMap<>();
        List<String> result = new ArrayList<>();
        
        int hashCode = 0;
    
        for (int i = 0; i < str.length(); i++) {
            int charCode = str.charAt(i);
            
            hashCode <<= 3;
            hashCode &= 0x3FFF_FFFF;
            hashCode |= charCode & 7;
            
            int prevFreq = frequencies.getOrDefault(hashCode, 0);
            frequencies.put(hashCode, prevFreq + 1);
            
            if (prevFreq == 1) {
                result.add(str.substring(i - 9, i + 1));
            }
        }
        
        return result;
    }
    
}

Time complexity- O(10 * n) = O(n)
Total Space complexity- O(10 * n)

Written by S. Kumar on June 27th, 2021

14. Does the data form a valid UTF-8 string?

This question focuses on Java iterations.

You are given an integer array of data containing bytes. Your task is determined if data form a valid UTF-8 string or not. The UTF-8 encoding has a variable number of bytes for different characters. They are encoded as follows:

â— For 1-byte characters, the first bit of the byte is 0.
â— For n-byte characters (2, 3, 4 bytes), the first n bits of the first byte is all oneâ€™s, the n + 1 bit is 0, followed by n - 1 byte with their most significant 2 bits equal to 10.

/*Example*/

Given data = [197, 130, 1]
Expected output: true
Explanation: The data represents the following octet sequence 1100_0101, 1000_0010, 0000_0001.
The first character is 2-byte characters and the next character is 1-byte long.

Given data = [235, 140, 4]
Expected output: false
Explanation: The data represents the following octet sequence 1110_1011, 1000_1100, 0000_0100.
It is not valid UTF-8. The first byte tells that the current character is 3-byte long. So we expect 2 more bytes which start with 10. But one of them starts with 00. So invalid UTF-8.

Constraint
â—	0 <= data[i] <= 255

Solution:

According the UTF-8, following will be the valid characters:
1-byte 0xxxxxxx
2-byte 110xxxxx 10xxxxxx
3-byte 1110xxxx 10xxxxxx 10xxxxxx
4-byte 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

We will iterate over each byte. We keep the count for continuation bytes in variable continuationBytesCount. If the continuationBytesCount is not zero, it means we expect a byte starting with 10. If the byte does not start with 10, the data does not represent a valid UTF-8. Thus we return false. If the byte starts with 10, we decrease continuationBytesCount and check the next byte.

If continuationBytesCount is zero, it means we are expecting the first byte of a character. We check the byte if it corresponds with a 4-byte or 3-byte or 2-byte character. We set the continuationBytesCount accordingly. If it is neither 4-byte nor 3-byte nor 2-byte and starts with 1, it means it is an illegal byte. So we return false. Otherwise, we check the next byte.

To check starting bits of the byte, we use the bit operation.
â— To check the first 2 bits, we right-shift 6 times
â— To check the first 3 bits, we right-shift 5 times
â— To check the first 4 bits, we right-shift 4 times
â— To check the first 5 bits, we right-shift 2 times

class Solution {
    public boolean validUtf8(int[] data) {
        int continuationBytesCount = 0;
        
        for (int currByte : data) {
            if (continuationBytesCount != 0) {
                if ((currByte >> 6) != 0b10) return false;
                continuationBytesCount--;
                continue;
            }
            
            if ((currByte >> 5) == 0b110) {
                // 2-byte character, so 1 continuation byte
                continuationBytesCount = 1;
            } else if ((currByte >> 4) == 0b1110) {
                // 3-byte character, so 2 continuation byte
                continuationBytesCount = 2;
            } else if ((currByte >> 3) == 0b11110) {
                // 4-byte character, so 3 continuation byte
                continuationBytesCount = 3;
            } else if ((currByte >> 7) == 1) {
                return false;
            }
        }
        
        return continuationBytesCount == 0;
    }

}

Time complexity- O(n)
Space complexity- O(1)

Written by S. Kumar on June 27th, 2021

15. Find bitwise OR subarrays.

This interview question concentrates on the developer's skills working with Java arrays and analysis.

You are given array nums of non-negative integers. We perform an operation on a subarray sub = [nums[i], nums[i + 1], ..., nums[j]], we take bitwise OR of all integers in sub and note its result. We perform this operation on all the possible subarrays of nums one by one. Your task is to calculate the number of possible results of these operations. The results that occur more than once are counted once only.

/*Example*/

Given nums = [1, 1, 2]
Expected output: 3
Explanation: The possible subarrays are- [1], [1], [2], [1, 1], [1, 2], [1, 1, 2]. The bitwise ORs of their elements are 1, 1, 2, 1, 3, 3. There are three unique values. So our answer is 3.

Solution:

Let result be a 2-D array with:

result[i][j] = nums[i] | nums[i + 1] | ... | nums[j]
Let curri be a set of values which stores result[0][i], result[1][i], ..., result[i][i], that is, the curri stores the result of operations applied on those subarrays that end at index i.

Now we process the integer nums[i + 1]. We need to find curri + 1 so that it contains the result of subarrays ending at the index i + 1. For this, we will iterate over all the values in curri and take bitwise OR with nums[i + 1] and store the result in curri + 1. We also add nums[i + 1] to curri + 1.

After finding all the values of curri + 1 we add its value to the final set res.
In the end, we return the size of res, that is, the number of possible results of the operations.

class Solution {
    public int subarrayBitwiseORs(int[] nums) {
        Set<Integer> res = new HashSet<>();
        Set<Integer> curr = new HashSet<>();
    
        for (int num : nums) {
            Set<Integer> curr2 = new HashSet<>();
            curr2.add(num);
        
            for (int or : curr) curr2.add(or | num);
            for (int or : curr2) res.add(or);
            
            curr = curr2;
        }
        
        return res.size();
    }

}

Time complexity- O(32 * n)
Space complexity- O(32 * n)

Complexity analysis:

Let us consider values in the set curri.
curri = result[0][i], result[1][i], ..., result[i][i]
It can be observed that
result[0][i] >= result[1][i] >= ... >= result[i][i]
and,
result[0][i] has all bits set that are set in result[1][i]
result[1][i] has all bits set that are set in result[2][i]
...

It means that when we know result[k][i], result[k - 1][i] will have all 1 bits from result[k][i], and it MAY have other additional bits equal to 1. For example:-
let result[k][i] = 0000_0010_0100_10111_0101_1010_1010_1110
then the result[k - 1][i] can either be equal to result[k][i] or it MAY have more bits that are equal to 1 depending on the value of nums[k - 1].

Thus the possible values of result[k - 1][i] are:
0000_0010_0100_10111_0101_1010_1010_1110 (same as result[k][i])
0000_0010_0100_10111_0101_1010_1010_1111 (0th bit is 1)
0000_0010_0100_10111_0101_1010_1111_1110 (4th and 6th bit is 1)
...

Since there are at most 32 bits (31 actually because we have non-negative integers only), there are at most 32 possible values in curri. That is,
curri <= 32

The worst case occurs when nums = [1, 2, 4, 8, ..., 230]. In this case all result[i][j] will be distinct. So res.size <= 32 * nums.length.

Written by S. Kumar on June 27th, 2021

16. What is the gray code sequence?

This question focuses on the developer's ability to work with Java iterations.

An n-bit gray code sequence is a sequence of 2n integers where:
â— All the integers are in the inclusive range of [0, 2n - 1].
â— The first integer is 0.
â— An integer appears exactly once in the sequence.
â— The binary representation of every pair of adjacent integers differs by exactly one bit.
â— The binary representation of the first and last integers differs by exactly one bit.
You are given the integer. Your task is to find the n-bit gray code sequence.

/*Example*/

Given n = 3
Expected output: [0, 1, 3, 2, 6, 7, 5, 4]
Explanation: The binary representations are:
0 ->	000
1 ->	001
3 ->	011
2 ->	010
6 ->	110
7 ->	111
5 ->	101
4 ->	100
The sequence follows all the rules of the n-bit gray code sequence.

Solution:

We will generate the sequence iteratively.
Let Si represent the sequence with n = i. Si + 1 can easily be generated from Si.
S1 = 0, 1
S2 = 00, 01, 11, 10
S3 will include all the integers from S2. It will have additional integers. Those integers can be generated from integers in S2 by doing their OR with 23 - 1 in reverse order.
S3 = 000, 001, 011, 010, 100, 101, 111, 110

The first four integers are the same as S2. The next four integers are generated from previous integers by adding 1 at the most significant bit. The underlined bits show the integers from the previous sequence S2 . Note that the last four integers are generated in reverse order in order to satisfy the conditions for the gray code sequence.

This can be extended to Si and Si + 1. We can generate Si + 1 from Si in the same way.

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(0);
    
        for (int i = 0; i < n; i++) {
            int oldCount = res.size();
            int powerOf2 = 1 << i;
            
            for (int j = oldCount - 1; j >= 0; j--) {
                res.add(res.get(j) | powerOf2);
            }
        }
        
        return res;
    }
}

Time complexity- O(2n)
Total Space complexity- O(2n)

Written by S. Kumar on June 27th, 2021