Interview Question

Data Scientist, Analytics Interview

-

Meta

Given 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?

AnswerAdd Tags

Interview Answers

6 Answers

0

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

0

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 = length-1 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

0

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

0

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

0

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_len-1,-1,-1): temp_sum = int(min_str[i]) + int(max_str[i+(max_len-min_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_len-min_len-1,-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

0

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

Add Answers or Comments

To comment on this, Sign In or Sign Up.