Ace Your Coding Interview — Blind 75 Solved and Explained— Part 2 Binary

If you haven’t seen my previous post, I am working through solving the blind 75 to help students and others looking for jobs as software engineers. As before, below is the link to the original post of the Blind 75.

New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time

This week we will be focusing on the binary section. Before we approach any of these questions we must understand how binary operations take place. Everything from your AND, XOR, NOT OR, NAND operations, and bit shifting.

With these questions as you read the questions themselves, you may realize that they look like a simple string question. However, as ones and zeros get involved keep in mind that the interviewer may be looking for a binary solution as it provides much faster run times and shows a unique skill set all interviewees may not have.

Down below I’ve placed tables from tutorialspoint.com that can help explain some of the bitwise operations being used.

https://www.tutorialspoint.com/java/java_basic_operators.htm

https://www.tutorialspoint.com/java/java_basic_operators.htm

Understanding these tables are imperative to solving these questions. Please take time to familiarize yourself with them and approach the questions once you have understood the fundamentals.

Question 1 — Sum of Two Integers

Sum of Two Integers - LeetCode

The solution to Sum of Two Integers

The key to this question lies in the fact that you are not allowed to utilize addition or subtraction operators. This means we need to use bitwise operations to create an addition operation

Our Approach:

1. Check if either b or a is zero; this is because anything plus zero is just the original value. (a+0 = a; and b+0 = b)
2. Next, we are going to the two numbers using the bitwise & operator, this checks if the two values are equal and return the equal value. So in this case, if both the values are one it indicates to us that we have a carry operation that has to occur.
3. Next, we check if only either a or b is one using an XOR operator ‘^’ if so we assign this value to a. This is because the value of a is what we will be returning at the end of our function.
4. Next, we are going to shift our carry to the left one bit and assign it to our b variable. This will allow us to keep looping through our variables until we have no carrying left.

Question 2 — Number of One Bit

Number of 1 Bits - LeetCode

The solution to the Number of One Bit

This question is much easier than the first one we have approached. Our solution lies in the fact that we can slide bits and check if our whole value is equal to 0. If n is equal to 0 we know that this means we have no more than one bits left in our number.

Our Approach:

1. Check if the last bit of our current number is 1. If so add 1 to the result.
2. Right shift bits by one filling the shift with 0. Utilize the >>> = operator.

Visualization:

Before Bit Shift: 00000110 After Bit Shift: 00000011

3. Repeat the loop until n is 0 at which point we know there are no 1s left.

Question 3 — Counting Bits

Counting Bits - LeetCode

The solution to Counting Bits

This problem gives us our first introduction to dynamic programming. We aren’t gonna dive deep into dynamic programming right now but utilize its principles to best solve these questions.

We are going to create an array that stores the number of ones for each binary value. Then by referencing back to this array we cannot redo operations but just utilize the previous results as a way to speed up our operations.

Our Approach:

1. Create an array big enough to store the number of one bits in n. For this, we need an array of size n + 1 this way we account for 0 as well.
2. We are going to set the first element of the array to zero because we know there to be no 1 bits in the binary number of zero.
3. Next, we enter our loop and by checking our round number to determine the value in our DP table. So given an index, we are going to take the value of the element that is in half the index value, in addition to, checking if our number is odd or even to see what value we need to add to the half indexed value. — This statement is confusing let me explain with numbers

Num --> Binary
--------------------
0 --> 0
1 --> 1
2 --> 10 --Take this as the half index of 4 and 5. When coding 4/2=2 5/2=2
3 --> 11
4 --> 100 -- Because 4 is even there is only other zero because 2*2 = 4 which is just done by shifting bit.
5 --> 101 -- 5 is odd it needs another 1 at the begining to make it an odd number

Another way to think of this, the reason we refer to the index at half the value is because as a binary we use base value of two. A basic bit shift to the left just leads us to twice the value.

Question 4 — Missing Number

Missing Number - LeetCode

The solution to Missing Number

Since we are looking for a missing value it should be clear that we need to utilize an XOR operation to best solve this question.

Our Approach

1. We are going to start by setting our answer to the length of our array. This accounts for when all the elements in the array have no missing values in the middle of them which indicates our missing value is at the end of the array.
2. A number XOR itself will become 0, and any number XOR with 0 will stay unchanged. So if every number from 1…n XOR with itself except the missing number, the result will be the missing number. Link
3. As with the explanation above by the time we each reach the end of the loop the only thing that is left at the end of the XOR operations is our missing value.

Question 5 — Reverse Bits

Reverse Bits - LeetCode

The solution to Reverse Bits

The way we approach this problem is through filling up a result variable as we look through our integer and returning it. It’s important to note we are flipping the bit sequence here not the number itself. The reverse of the number does not equal the reverse of the bit sequence.

What we are going to do here is to grab the number from the end of the n variable and put it into our result variable and shift both of them to

Our Approach:

1. Create a loop to look through the 32 digits in our num.
2. Slide the number one bit shift left. For example

0001 Shifts to 00010 — We shifted the bits one left. This allows us to push our bits forward. As shown in the code its almost like multiplying by 2.

3. Next, we are going to add we are going to add the end of n to our result array.

4. Finally, we are going to slide n right one bit to get the new starting bit to n. For example:

0010 Shifts to 001 — We shifted the bits one right. This allows us to push our bits back. As shown in the code its almost like dividing by 2 to get the next digit.

Posts in the Series

Arrays: https://medium.com/@ulucozdenvar01/ace-your-coding-interview-blind-75-solved-and-explained-part-1-arrays-4692c04891e0

Interval: https://medium.com/@ulucozdenvar01/ace-your-coding-interview-blind-75-solved-and-explained-part-3-intervals-ef6adbcc93fe

LinkedList: https://medium.com/@ulucozdenvar/ace-your-coding-interview-blind-75-solved-and-explained-part-4-linked-list-6c05a9a92b75

String: https://medium.com/@ulucozdenvar/ace-your-coding-interview-blind-75-solved-and-explained-part-5-string-3cae5fd56f36

Tree: https://medium.com/@ulucozdenvar/ace-your-coding-interview-blind-75-solved-and-explained-part-6-1-trees-fe2576392f54

Trees Part 2: https://medium.com/@ulucozdenvar/ace-your-coding-interview-blind-75-solved-and-explained-part-6-2-trees-continued-64cf6f60350

Matrix: https://medium.com/@ulucozdenvar/ace-your-coding-interview-blind-75-solved-and-explained-part-7-matrix-244b4b308bfc

Heap: https://medium.com/@ulucozdenvar/ace-your-coding-interview-blind-75-solved-and-explained-part-8-heaps-560ab652094f

Dynamic Programming: Coming Soon

Graph: Coming Soon