Pregunta de entrevista

Entrevista de Data Scientist, Analytics

-

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?

Respuesta

Respuestas de entrevistas

6 respuestas

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).

Anónimo en

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)

Anónimo en

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 en

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 en

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 en

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 en

Añadir respuestas o comentarios

Para publicar un comentario sobre esto, inicia sesión o regístrate.