4.5 of 5 676 reviews
www.facebook.com Menlo Park, CA 5000+ Employees

Facebook Front End Engineer, Infrastructure Interview Question

I interviewed in Menlo Park, CA and was asked:
"Given 2 very large numbers, each of which is so large it can only be represented as an array of integers, write a function to multiply them."
Add Tags [?]
Answer Flag Question

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

Answers & Comments

of 2
This is similar to implementing add, subtract or multiply functions.

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)
- Fayyaz on May 26, 2012 Flag Response
of 2
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;
- Fayyaz on May 26, 2012 Flag Response
of 0
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;
            cr = carry + r[cri];
            r[cri++] = cr % MULTIPLY_BASE;
            carry = cr / MULTIPLY_BASE;
    while((!r.empty()) && r.back() == 0) r.pop_back(); // trim result
- emk on Aug 30, 2012 Flag Response

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.

Glassdoor is your free inside look at Facebook interview questions and advice. All interview reviews posted anonymously by Facebook employees and interview candidates.