This employer has taken extra steps to respond to reviews and provide job seekers with accurate company information, photos, and reviews. Interested for your company? Learn More.

Part of a `Front End Engineer, Infrastructure` Interview Review - one of `1,062` `Facebook` Interview Reviews

Answers & Comments

▲

0

▼

of 2votes

I just coded this too out of curiosity since i only coded big integer + and - in university which was like 6 years ago. So thought of making sure i was right. Here is the function and sample main call.

One thing i only found while debugging that two possibilities of carry exist

1. When simply the result of multiplying two numbers

2. When adding a result into existing array.

I missed 2 in my implementation at first and only discovered this through testing. Now it's resolved and working.

void multiply(int a[], int b[], int sa, int sb)

{

int sr = sa+sb;

int *r = new int[sr];

int res_indx = sr-1;

memset(r,0, sr * sizeof(int));

//for(int i=0; i<sr; i++)

// r[i] = 0;

for(int mul=sa-1; mul>=0; mul--)

{

int c_indx = res_indx;

int carry = 0;

for(int mcnt=sb-1; mcnt>=0; mcnt--)

{

int m = b[mcnt] * a[mul] + carry;

int sum = r[c_indx] + (m%10);

r[c_indx--] = sum%10;

carry = sum/10 + m/10; // two possibilities of carry one in the m and the other in sum

if(mcnt == 0)

r[c_indx] += carry; // copy the carry digit for the last operand

}

res_indx--; // X.. moving starting index one column back in each iteration

}

for(int i=0; i<sr; i++)

cout << r[i];

cout << endl;

}

int main()

{

int a[] = {9,8,7,6,5,1,0};

int b[] = {4,3,2,4,5,6,7};

multiply(a, b, sizeof(a)/sizeof(int), sizeof(b)/sizeof(int));

return 0;

}

One thing i only found while debugging that two possibilities of carry exist

1. When simply the result of multiplying two numbers

2. When adding a result into existing array.

I missed 2 in my implementation at first and only discovered this through testing. Now it's resolved and working.

void multiply(int a[], int b[], int sa, int sb)

{

int sr = sa+sb;

int *r = new int[sr];

int res_indx = sr-1;

memset(r,0, sr * sizeof(int));

//for(int i=0; i<sr; i++)

// r[i] = 0;

for(int mul=sa-1; mul>=0; mul--)

{

int c_indx = res_indx;

int carry = 0;

for(int mcnt=sb-1; mcnt>=0; mcnt--)

{

int m = b[mcnt] * a[mul] + carry;

int sum = r[c_indx] + (m%10);

r[c_indx--] = sum%10;

carry = sum/10 + m/10; // two possibilities of carry one in the m and the other in sum

if(mcnt == 0)

r[c_indx] += carry; // copy the carry digit for the last operand

}

res_indx--; // X.. moving starting index one column back in each iteration

}

for(int i=0; i<sr; i++)

cout << r[i];

cout << endl;

}

int main()

{

int a[] = {9,8,7,6,5,1,0};

int b[] = {4,3,2,4,5,6,7};

multiply(a, b, sizeof(a)/sizeof(int), sizeof(b)/sizeof(int));

return 0;

}

▲

0

▼

of 0votes

const unsigned MULTIPLY_BASE = 10;

void multiplyLittleEndian(const vector<unsigned> &a, const vector<unsigned> &b, vector<unsigned> &r)

{

r.assign(a.size()+b.size(), 0);

unsigned ri=0;

for(unsigned ai=0; ai<a.size(); ++ai)

{

unsigned cri = ri++, carry = 0, am = a[ai], cr;

for(unsigned bi=0; bi<b.size(); ++bi, ++cri)

{

cr = carry + am*b[bi] + r[cri];

r[cri] = cr % MULTIPLY_BASE;

carry = cr / MULTIPLY_BASE;

}

while(carry)

{

cr = carry + r[cri];

r[cri++] = cr % MULTIPLY_BASE;

carry = cr / MULTIPLY_BASE;

}

}

while((!r.empty()) && r.back() == 0) r.pop_back(); // trim result

}

void multiplyLittleEndian(const vector<unsigned> &a, const vector<unsigned> &b, vector<unsigned> &r)

{

r.assign(a.size()+b.size(), 0);

unsigned ri=0;

for(unsigned ai=0; ai<a.size(); ++ai)

{

unsigned cri = ri++, carry = 0, am = a[ai], cr;

for(unsigned bi=0; bi<b.size(); ++bi, ++cri)

{

cr = carry + am*b[bi] + r[cri];

r[cri] = cr % MULTIPLY_BASE;

carry = cr / MULTIPLY_BASE;

}

while(carry)

{

cr = carry + r[cri];

r[cri++] = cr % MULTIPLY_BASE;

carry = cr / MULTIPLY_BASE;

}

}

while((!r.empty()) && r.back() == 0) r.pop_back(); // trim result

}

** To comment on this question, Sign In with Facebook or Sign Up **

Tags are like keywords that help categorize interview questions that have something in common.

Would you like us to review something? Please describe the problem with this {0} and we will look into it.

We're sorry but your feedback didn't make it to the team. Your input is valuable to us – would you mind trying again?

Browse:

Copyright © 2008–2014, Glassdoor. All Rights Reserved. Your use of this service is subject to our Terms of Use and Privacy & Cookies Policy. Safe Harbor Notice. Glassdoor ® is a registered trademark of Glassdoor, Inc.

Sign In with Google

Sign In with Facebook

Everything you view and do on Glassdoor is private

Or

votes

A good way to do this is use the same mechanism as we do in high school on paper i.e. you have two arrays. Put one as multiplier and the other as multiplicant.

Take the right most digit of multiplier, and multiply with last digit of multiplicant, assign the right into start of result (we either reverse result in the end or we assign it in the end of result ensuring result array's size can accommodate number of digits that result from the multiplication.

So we have two nested loops, outer one going through each digit of multiplier and inner one going through each of multiplicant.

There are special things to cater

1. Carry result of each multiplication to the next.

2. As in standard multiplication each next digit of multiplier results in as many digits of result for e.g. when multiplying 778 with 64 there is one row of results obtained when 4 is multiplied with each of 7,7 and 8 and another row when the same is done with 6. So either we store all these rows first and add corresponding indexes latter or we keep adding them into the final array as we go (without storing them separately)

FayyazonMay 26, 2012Flag Response