Facebook Interview Question
Data EngineersCountry: United States
Interview Type: In-Person
decimal multiplication on string does it, although converting the string to binary and doing a binary multiplication would obviously be more effective
in python 3
def string_multiplication(a, b):
result = []
result_start_idx = 0
for ai in map(lambda x: ord(x) - ord('0'), reversed(a)):
overflow = 0
result_idx = result_start_idx
for b_idx in range(len(b) - 1, -1, -1):
m = (ord(b[b_idx]) - ord('0')) * ai + overflow
if result_idx < len(result):
m += result[result_idx]
result[result_idx] = m % 10
else :
result.append(m % 10)
overflow = m // 10
result_idx += 1
if overflow > 0:
result.append(overflow)
result_start_idx += 1
return ''.join(map(lambda x: chr(ord('0') + x), reversed(result)))
number_one = 193283492420348904832902348908239048823480823
number_two = 3248234890238902348823940990234
print(number_one*number_two)
print(string_multiplication(str(number_one), str(number_two)))
#the product of ith index of A and jth index of B would be going to i+j and i+j+1 th position
def string_multiplication(a, b):
def string_multiplication(a, b):
result=[0]*(len(a)+len(b))
for i in range(len(a)-1,-1,-1):
for j in range(len(b)-1,-1,-1):
mul=int(a[i])*int(b[j])
pos1,pos2=i+j,i+j+1
sum_all=mul+result[pos2]
result[pos1]+=int(sum_all/10)
result[pos2]=int(sum_all%10)
return result
print(string_multiplication('8', '100'))
def string_multiplication(a, b):
result=[0]*(len(a)+len(b))
for i in range(len(a)-1,-1,-1):
for j in range(len(b)-1,-1,-1):
mul=int(a[i])*int(b[j])
pos1,pos2=i+j,i+j+1
sum_all=mul+result[pos2]
result[pos1]+=int(sum_all/10)
result[pos2]=int(sum_all%10)
return result
print(string_multiplication('8', '100'))
def string_multiplication(a, b):
result=[0]*(len(a)+len(b))
for i in range(len(a)-1,-1,-1):
for j in range(len(b)-1,-1,-1):
mul=int(a[i])*int(b[j])
pos1,pos2=i+j,i+j+1
sum_all=mul+result[pos2]
result[pos1]+=int(sum_all/10)
result[pos2]=int(sum_all%10)
return result
print(string_multiplication('8', '100'))
Same solution as given by Florent but in Java:
import java.util.*;
class Main {
public static void main(String[] args) {
String n1 = "3922445243";
String n2 = "3248234";
double result=0;
for(int i=0;i<n1.length();i++){
for(int j=0;j<n2.length();j++){
double num1 = (n2.charAt(j)-'0')*(Math.pow(10,n2.length()-j-1));
double num2 = (n1.charAt(i)-'0')*(Math.pow(10,n1.length()-i-1));
result +=(num1*num2);
}
}
System.out.println(result);
}
}
def string_multiplication(a, b):
result = [0] * (len(a) + len(b))
for i in reversed(range(len(a))):
for j in reversed(range(len(b))):
result[i+j+1] += (ord(a[i]) - ord('0')) * (ord(b[j]) - ord('0'))
result[i+j] += result[i+j+1] / 10
result[i+j+1] %= 10
return ''.join( map(str, result[ next( idx for idx, digit in enumerate(result) if digit != 0) : ]) )
number_one = 193283492420348904832902348908239048823480823
number_two = 3248234890238902348823940990234
print(number_one*number_two)
print(string_multiplication(str(number_one), str(number_two)))
def string_multiplication(a, b):
result = [0] * (len(a) + len(b))
for i in reversed(range(len(a))):
for j in reversed(range(len(b))):
result[i+j+1] += (ord(a[i]) - ord('0')) * (ord(b[j]) - ord('0'))
result[i+j] += result[i+j+1] / 10
result[i+j+1] %= 10
return ''.join( map(str, result[ next( idx for idx, digit in enumerate(result) if digit != 0) : ]) )
number_one = 193283492420348904832902348908239048823480823
number_two = 3248234890238902348823940990234
print(number_one*number_two)
print(string_multiplication(str(number_one), str(number_two)))
def string_multiplication(a, b):
result = [0] * (len(a) + len(b))
for i in reversed(range(len(a))):
for j in reversed(range(len(b))):
result[i+j+1] += (ord(a[i]) - ord('0')) * (ord(b[j]) - ord('0'))
result[i+j] += result[i+j+1] / 10
result[i+j+1] %= 10
return ''.join( map(str, result[ next( idx for idx, digit in enumerate(result) if digit != 0) : ]) )
number_one = 193283492420348904832902348908239048823480823
number_two = 3248234890238902348823940990234
print(number_one*number_two)
print(string_multiplication(str(number_one), str(number_two)))
def string_multiplication(a, b):
result = [0] * (len(a) + len(b))
for i in reversed(range(len(a))):
for j in reversed(range(len(b))):
result[i+j+1] += (ord(a[i]) - ord('0')) * (ord(b[j]) - ord('0'))
result[i+j] += result[i+j+1] / 10
result[i+j+1] %= 10
return ''.join( map(str, result[ next( idx for idx, digit in enumerate(result) if digit != 0) : ]) )
number_one = 193283492420348904832902348908239048823480823
number_two = 3248234890238902348823940990234
print(number_one*number_two)
print(string_multiplication(str(number_one), str(number_two)))
As an alternative solution, the code below uses recursion and dictionaries. It's more lines of code, but it also accounts for the negative edge case.
def multiplyStrings(str1, str2):
if(str1[0]=="-"):
initStr1 = str1[1:]
multStr1 = -1
else:
initStr1 = str1[0:]
multStr1 = 1
if(str2[0]=="-"):
initStr2 = str2[1:]
multStr2 = -1
else:
initStr2 = str2[0:]
multStr2 = 1
return multStr1*multiplyString1(initStr1)*multStr2*multiplyString2(initStr2)
def multiplyString1(str1):
if(len(str1)==1):
return findNumber(str1)
else:
return findNumber(str1[0])*(10**(len(str1)-1))+multiplyString1(str1[1:])
def multiplyString2(str2):
if(len(str2)==1):
return findNumber(str2)
else:
return findNumber(str2[0])*(10**(len(str2)-1))+multiplyString2(str2[1:])
def findNumber(string):
numbers = {
"0" : 0,
"1" : 1,
"2" : 2,
"3" : 3,
"4" : 4,
"5" : 5,
"6" : 6,
"7" : 7,
"8" : 8,
"9" : 9
}
return numbers[string]
num1 = 193283492420348904832902348908239048823480823
num2 = 3248234890238902348823940990234
print(num1*num2)
print(multiplyStrings(str(num1),str(num2)))
def multiplyStrings(str1, str2):
if(str1[0]=="-"):
initStr1 = str1[1:]
multStr1 = -1
else:
initStr1 = str1[0:]
multStr1 = 1
if(str2[0]=="-"):
initStr2 = str2[1:]
multStr2 = -1
else:
initStr2 = str2[0:]
multStr2 = 1
return multStr1*multiplyString1(initStr1)*multStr2*multiplyString2(initStr2)
def multiplyString1(str1):
if(len(str1)==1):
return findNumber(str1)
else:
return findNumber(str1[0])*(10**(len(str1)-1))+multiplyString1(str1[1:])
def multiplyString2(str2):
if(len(str2)==1):
return findNumber(str2)
else:
return findNumber(str2[0])*(10**(len(str2)-1))+multiplyString2(str2[1:])
def findNumber(string):
numbers = {
"0" : 0,
"1" : 1,
"2" : 2,
"3" : 3,
"4" : 4,
"5" : 5,
"6" : 6,
"7" : 7,
"8" : 8,
"9" : 9
}
return numbers[string]
num1 = 193283492420348904832902348908239048823480823
num2 = 3248234890238902348823940990234
print(num1*num2)
print(multiplyStrings(str(num1),str(num2)))
In Python 3
- Florent L July 06, 2017