I was recently mentoring a junior dev who was sharing some stories with me regarding his interview experience for the current role he's in. He recalled that he was thrown some "curve balls" when it came time to the coding challenge portion of the interview. He was faced with three questions: the first was an inverting binary tree question - and the second was a binary search problem. Pretty common and typical questions. He aced the first two... but had a little trouble with the third one: adding two binary strings together.
This problem is generally regarded as "easy", but some of the easy problems require more planning and understanding the underlying mechanics more than others - and this is one of them. In retrospect, he realized that jumping right into coding prior to thinking about the edge cases and logic is what made this feel more like a medium or hard question.
The goal of the Add Binary Strings problem is to write a function that takes two binary strings a and b and returns a third binary string that contains the sum of a and b.
The problem has multiple variations depending on who's asking, but typically one of the commonalities is that the binary strings can be hundreds of digits long - which is pretty much to force you to get creative and not just convert the strings to integers, add them together, and then convert the integer sum back to a string of bits.
A sub-10 line solution
Many of the common programming languages supported by coding interview platforms all bundle their own variation of BigInteger - functionality that allows us to perform bitwise and mathematical operations on large numbers outside the bounds of the typical 32 or 64 bit data types that standard variables are capped at.
If we go down the BigInteger route, we can literally code a solution in just a few lines (code snippet examples in Java, Golang, Javascript, respectively):
This works, but we're kind of cheating because we didn't actually implement any of the logic ourselves - so let's see how we would roll our own algorithm to achieve the same result.
Implementing the algorithm ourselves
Take the example below - we are adding two numbers: 15 (1111 in binary) and 12 (1100 in binary):
At any given iteration, we have two things we need to do: figure out the current output bit, and the current carry bit that we pass over to the next iteration of the loop. The carry bit will be set to 1 if a column's sum is greater than or equal to 2 (meaning we have an overflow).
This is actually rather straightforward. In each column (starting from the far right) we add all three bits together (carryBit + bitA + bitB). The sum for each column is shown in an orange and blue 2-bit pair. The right bit (blue) is the output bit for that column. The left bit (orange) is the carry bit that overflows to the next column.
Translating over to code
Remember that the addBinary function accepts 2 strings - and the two strings may not be the same lengths as each other. Therefore, we'll create two variables - aLen and bLen, to hold the lengths of each string, and set a variable named maxLen to the value of whichever value is the largest.
We'll create a couple more variables - carryBit (which again, at the beginning is 0 since we don't have an overflow of anything yet), and sumStr, which will hold the entire resulting sum binary string.
Next we set up the loop - initializing a counter i starting at 1 and increasing that value until we reach maxLen OR while carryBit is not zero:
The offsets for which characters we want to look at each iteration are calculated like so:
You'll probably notice that since we're looping until at least the length of the longest string (OR while we still have a remaining carry bit), it's possible at some point aOffset or bOffset (whichever is the smaller of the two) or both, is going to become negative, which means we've scanned as far to the left as we can and now we're "outside" the bounds of one or both of the strings. The next following lines of code handles these cases:
If aOffset is greater than or equal to 0 and the character value at that position in string a is '1' then we set bitA to 1 - otherwise if either of those conditions is false we just keep bitA set to 0.
Same logic for bOffset: If bOffset is greater than or equal to 0 and the character value at that position in string b is '1' then we set bitB to 1 - otherwise we just keep bitB set to 0.
Now we sum carryBit, bitA, and bitB altogether, convert the first bit (rightmost bit) of the sum to a character, and concatenate to the beginning of sumStr.
Finally, we discard the first bit of sum but extract the carry bit to pass over to the next iteration of the loop, which can be done by simply bit shifting sum to the right by 1:
The full code for the addBinary function (Go implementation):
Java version can be found here: https://gist.github.com/edev90/9bc7010845daea8c7f13f260f274f1a3
JavaScript version can be found here: https://gist.github.com/edev90/93fb814b4de2d15129530f4e1e2cf412
As we can see, the answer shouldn't be complex. If you're working on this and come to a solution that has multiple loops, arrays, and nested conditionals all over the place and/or tons of bugs due to mishandled edge cases - it's likely a sign that you need to reevaluate your logic and see how it can be condensed further.
No comments:
Post a Comment