Interview Question
Data Scientist, Analytics Interview

MetaGiven two binary strings, write a function that adds them. You are not allowed to use any built in string to int conversions or parsing tools. E.g. Given "100" and "111" you should return "1011". What is the time and space complexity of your algorithm?
Interview Answers
6 Answers
In Python: def normalize_length(str1, str2): len1 = len(str1) len2 = len(str2) if (len1 = 0): if (input2[i] == "1") and (input1[i] == "1"): if(carry): result = "1" + result carry = 1 else: carry = 1 result = "0" + result i = 1 if (input2[i] == "1") and (input1[i] == "0"): if (carry): result = "0" + result else: result = "1" + result i = 1 if (input2[i] == "0") and (input1[i] == "1"): if (carry): result = "0" + result else: result = "1" + result i =1 if (input2[i] == "0") and (input1[i] == "0"): if (carry): result = "1" + result carry = 0 else: result = "0" + result i =1 if(carry): result = "1" + result carry = 0 return(result) str1 = "111" str2 = "1011" print(normalize_length(str1, str2)) print(add_binary(str1, str2)) Obviously there are better ways to do this, but hey: my solution is O(N).
Anonymous on
Ignore the answer above  didn't realize that Glassdoor would cut off parts of my answer for being too long. Assuming you already wrote the normalizing code to make the input lengths the same by adding zeros: def add_binary(input1, input2): normalized = normalize_length(input1, input2) input1 = normalized[0] input2 = normalized[1] length = len(input1) result = "" carry = 0 i = length1 while(i >= 0): if (input2[i] == "1") and (input1[i] == "1"): if(carry): result = "1" + result carry = 1 else: carry = 1 result = "0" + result i = 1 if (input2[i] == "1") and (input1[i] == "0"): if (carry): result = "0" + result else: result = "1" + result i = 1 if (input2[i] == "0") and (input1[i] == "1"): if (carry): result = "0" + result else: result = "1" + result i =1 if (input2[i] == "0") and (input1[i] == "0"): if (carry): result = "1" + result carry = 0 else: result = "0" + result i =1 if(carry): result = "1" + result carry = 0 return(result)
Anonymous on
def calc_bin_sum(bin1, bin2): ## bin1 conversion to a number based in 10 b1 = 0 for i in range(len(bin1)): b1 = b1 + int(bin1[i]) * (2**i) ## bin2 conversion to a number based in 10 b2 = 0 for j in range(len(bin2)): b2 = b2 + int(bin2[j]) * (2**i) ## Add two numbers corr_based_10 = b1 + b2 ## Change it back to binary def trans(x): binary = [] while x: binary.append(x % 2) x >>= 1 return binary return ''.join(map(str, trans(corr_based_10)))
prep on
A good perl programmer can write perl in any language reduce( lambda st_car, nxt : (st_car[0] + str((st_car[1] + nxt) % 2), int((st_car[1] + nxt)/2)), map(lambda a:sum(map(int, a)), zip_longest(reversed('11'),reversed('101010'), fillvalue='0')), ('', 0) )[0]
vish on
Using Python, def binaryAdd(str1, str2): len_str1 = len(str1) len_str2 = len(str2) if len_str1 > len_str2: max_len = len_str1 min_len = len_str2 max_str = str1 min_str = str2 else: max_len = len_str2 min_len = len_str1 max_str = str2 min_str = str1 # resulting str res = '' carry_over = 0 # 0 or 1 at all times for i in range(min_len1,1,1): temp_sum = int(min_str[i]) + int(max_str[i+(max_lenmin_len)]) + carry_over res = str(temp_sum % 2) + res # modulo 2; remainder is the digit carry_over = int(temp_sum/2) for i in range(max_lenmin_len1,1,1): temp_sum = int(max_str[i]) + carry_over res = str(temp_sum % 2) + res carry_over = int(temp_sum/2) if carry_over == 1: res = '1' + res print(res)
MKS on
Here's how I would've done it: def add_bin(str1, str2): len1 = len(str1) len2 = len(str2) diff = len2  len1 #padded zeros if diff 0: for zero in range(diff): str1 = '0'+str1 results = [] carry = 0 #binary algebra for bit1,bit2 in zip(reversed(str1), reversed(str2)): if bit1 == '1' and bit2 == '1': if carry == 1: results.append('1') carry = 1 else: results.append('0') carry = 1 elif (bit1 == '0' and bit2 == '1') or (bit1 == '1' and bit2 == '0'): # print('hi') if carry == 1: results.append('0') carry = 1 else: results.append('1') carry = 0 elif (bit1 == '0' and bit2 == '0'): if carry == 1: results.append('1') carry = 0 else: results.append('0') carry = 0 #last carry: if carry == 1: results.append('1') return ''.join(reversed(results)) str1 = "100" str2 = "111" print(add_bin(str1, str2))
Max on