Goldman Sachs Interview Question
Applications DevelopersCountry: India
Interview Type: Written Test
Use arrays to store the numbers, then for multiplication you will need n no of arrays, where n is the no of digits of smaller number and one extra array to store carry ,
Then perform multiplication :)
C++ solution
Btw: The second example multiplication is wrong, it's 536282028 X 352321 (one less 8)
#include <algorithm>
#include <vector>
using namespace std;
vector<int> MultiplyVectors(const vector<int> &v1, const vector<int> &v2) {
vector<vector<int>> sums;
for (int i = v2.size()-1; i >= 0; --i) {
sums.push_back(vector<int>(v2.size()-1-i, 0));
int carry = 0;
for (int j = v1.size()-1; j >= 0; --j) {
int v = v1[j]*v2[i]+carry;
sums.back().push_back(v%10);
carry = v/10;
}
if (carry != 0)
sums.back().push_back(carry);
}
size_t max_idx = 0;
for (size_t i = 0; i < sums.size(); ++i)
max_idx = max(max_idx, sums[i].size());
vector<int> ret;
int v = 0;
for (size_t i = 0; i < max_idx; ++i) {
for (size_t j = 0; j < sums.size(); ++j) {
if (i < sums[j].size())
v += sums[j][i];
}
ret.push_back(v%10);
v /= 10;
}
if (v != 0)
ret.push_back(v);
reverse(ret.begin(), ret.end());
return ret;
}
#include<iostream>
using namespace std;
int main()
{
int a[]={1,4,7,5,2,3};
int n=sizeof(a)/sizeof(*a);
int b[]={5,4,5,7,8,9,2};
int m=sizeof(b)/sizeof(*b);
int res[10000]={0};
int carry=0;
int h=0;
for(int i=n-1; i>=0; i--)
{
int k=b[m-1]*a[i];
k+=carry;
res[h++]=k%10;
carry=k/10;
}
while(carry)
{
res[h++]=carry%10;
carry=carry/10;
}
int l=1;
int k;
for(int i=m-2; i>=0; i--)
{
int carry=0;
k=l;
int temp[1000]={0};
for(int j=n-1; j>=0; j--)
{
int x=b[i]*a[j];
x+=carry;
carry=x/10;
temp[k++]=x%10;
}
while(carry)
{
temp[k++]=carry%10;
carry=carry/10;
}
for(int i=0; i<k; i++)
{
int sum=res[i]+temp[i];
sum+=carry;
carry=sum/10;
res[i]=sum%10;
}
l++;
}
for(int i=k-1; i>=0; i--)
cout<<res[i]<<" ";
}
#include<iostream>
using namespace std;
int main()
{
int a[]={1,4,7,5,2,3};
int n=sizeof(a)/sizeof(*a);
int b[]={5,4,5,7,8,9,2};
int m=sizeof(b)/sizeof(*b);
int res[10000]={0};
int carry=0;
int h=0;
for(int i=n-1; i>=0; i--)
{
int k=b[m-1]*a[i];
k+=carry;
res[h++]=k%10;
carry=k/10;
}
while(carry)
{
res[h++]=carry%10;
carry=carry/10;
}
int l=1;
int k;
for(int i=m-2; i>=0; i--)
{
int carry=0;
k=l;
int temp[1000]={0};
for(int j=n-1; j>=0; j--)
{
int x=b[i]*a[j];
x+=carry;
carry=x/10;
temp[k++]=x%10;
}
while(carry)
{
temp[k++]=carry%10;
carry=carry/10;
}
for(int i=0; i<k; i++)
{
int sum=res[i]+temp[i];
sum+=carry;
carry=sum/10;
res[i]=sum%10;
}
l++;
}
for(int i=k-1; i>=0; i--)
cout<<res[i]<<" ";
}
public static void main(String[] args) {
int[] num1={1,2,3,4,5};
int[] num2={1,2,4,6};
System.out.println(multiply(breakNumbers(num1), breakNumbers(num2)));
int sum=0;
Map<Integer,Integer> multiplyMap = multiply(breakNumbers(num1), breakNumbers(num2));
for (Map.Entry<Integer,Integer> entry : multiplyMap.entrySet()) {
sum +=(entry.getKey()*(Math.pow(10,entry.getValue())));
}
System.out.println(sum);
}
static Map<Integer,Integer> multiply(Map<Integer,Integer> num1,Map<Integer,Integer> num2){
Map<Integer,Integer> multiplyMap=new LinkedHashMap<Integer,Integer>();
for (Map.Entry<Integer,Integer> entry1 : num1.entrySet()) {
for (Map.Entry<Integer,Integer> entry2 : num2.entrySet()) {
multiplyMap.put(entry1.getKey()*entry2.getKey(), entry1.getValue()+entry2.getValue());
}
}
return multiplyMap;
}
static Map<Integer,Integer> breakNumbers(int[] num1){
Map<Integer,Integer> numMap=new LinkedHashMap<Integer,Integer>();
String s="";
int count=0;
for(int i=0;i<num1.length;i++){
count++;
if(count==3 || i==num1.length-1){
s+=num1[i];
numMap.put(Integer.valueOf(s), num1.length-(i+1));
s="";
count=0;
}else{
s+=num1[i];
}
}
return numMap;
}
# Reverse an array to change endianness of numbers
def num_array_reverse(num_array):
left = 0
right = len(num_array) - 1;
while (left < right):
num_array[left], num_array[right] = num_array[right], num_array[left]
left += 1
right -= 1
# Multiply two numbers
# Input: Big-endian order
# Output: Big-endian order
def multiply(num_a_array, num_b_array):
# Convert big-endian to little-endian
num_array_reverse(num_a_array)
num_array_reverse(num_b_array)
# Initialize the result
num_result_arr = []
# Multiply
for i in range(0, len(num_a_array)):
carry = 0
j = 0
while (j < len(num_b_array)):
val = num_a_array[i] * num_b_array[j] + carry
if (len(num_result_arr) <= i + j):
num_result_arr.append(0)
val += num_result_arr[i + j]
carry = val / 10
val %= 10
num_result_arr[i + j] = val
j += 1
if (carry):
if (len(num_result_arr) <= i + j):
num_result_arr.append(carry)
else:
num_result_arr[i + j] = carry
# Convert little-endian to big-endian
num_array_reverse(num_a_array)
num_array_reverse(num_b_array)
num_array_reverse(num_result_arr)
return num_result_arr
def multiply_and_print(num_a_array, num_b_array):
num_result_array = multiply(num_a_array, num_b_array)
print("{0} x {1} = {2}".format(num_a_array, num_b_array, num_result_array))
def main():
multiply_and_print([1, 2], [1, 0])
multiply_and_print([5, 3, 6, 2, 8, 0, 2, 8], [3, 5, 2, 3, 2, 1])
main()
public class LargeMultiplication
- Pradeep kumar R S January 15, 2015{
public static void main( String[] args )
{
int[] Num1 = { 5,3,6,2,8,2,0,2,8 };
int[] Num2 = { 3,5,2,3,2,1,3,4 };
int sum = 0, carry;
int k = Num1.length + Num2.length;
int[] Num = new int[k];
for( int i = Num1.length - 1; i >= 0; i-- )
{
carry = 0;
for( int j = Num2.length - 1; j >= 0; j-- )
{
sum = Num2[j] * Num1[i] + carry + Num[k - 1];
carry = sum / 10;
Num[--k] = sum % 10;
}
Num[--k] = carry;
k += Num2.length;
}
for( int j = 0; j < Num.length; j++ )
{
System.out.println( j + "= " + Num[j] );
}
}
}