Solution for kth row of Pascal's triangle for a job interview

Question

Question:

Given an index \$k\$, return the \$k^{th}\$ row of the Pascal's triangle.

For example, given \$k = 3\$, return \$[1,3,3,1]\$. Bonus points for using \$O(k)\$ space.

Can it be further optimized using this way or another?

class Solution {
   public:
    long long C(int n, int r) {
       if(r > n / 2) r = n - r; // because C(n, r) == C(n, n - r)
       long long ans = 1;
       int i;

       for(i = 1; i <= r; i++) {
           ans *= n - r + i;
           ans /= i;
       }

       return ans;
   }

       vector<int> getRow(int rowIndex) {
           vector<int> v;
           long long sol;
           for(int i=0;i<=rowIndex;i++)
           {sol=C(rowIndex,i);
           v.push_back(sol);}

          return v; 
       }
   };

Answer 1

There are at least two optimizations you could make.

First of all, you are performing r multiplications and r divisions for each value of C(k,r) you compute for r < k/2. You should only need at most one multiplication and one division per value of C(k,r) that you compute, because at the time you want to compute C(k,r) you have already computed and stored the value of C(k, r-1). Use the fact that C(k,r) == C(k, r-1) * (k-r+1) / r:

$$\begin{align*} \frac{C(k, r)}{C(k, r - 1)} &= \frac{\frac{k!}{r! (k-r)!}}{\frac{k!}{(r-1)!(k-r+1)!}} = \frac{(r - 1)! (k - r + 1)!}{r! (k - r)!} = \frac{k - r + 1}{r} \\ \\ C(k, r) &= \frac{k - r + 1}{r} C(k, r - 1) \end{align*}$$

This reduces the number of arithmetic operations required from O(k²) to O(k), which I think is a pretty good optimization.

The second optimization is due to the fact that C(k, r) == C(k, k - r). You used this formula to reduce the number of operations required to compute C(k,r) for r > k/2, but in fact you shouldn't have to perform any operations for any of those entries in Pascal's triangle, because you have already computed and stored the answer. Just copy those results to fill the rest of the vector. (But of course don't copy C(k, k/2) when n is even.)

The second optimization reduces the number of operations by nearly half.

A consequence of applying these optimizations is that it no longer makes sense to implement a function like C(int n, int r). But implementation of that function was not part of your requirements as far as I can see.

Answer 2

For one thing, the inconsistency with whitespace use and curly brace placing may demonstrate a lack of attention to detail. Before you attack the actual problem, make sure your code is written cleanly.

This:

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

should use some whitespace:

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

You already do this in other places, and it should be done everywhere.

Also, this:

for(int i=0;i<=rowIndex;i++)
{sol=C(rowIndex,i);
v.push_back(sol);}

looks a bit sloppy and is harder to read. Again, use more whitespace, but also separate the loop body from the curly braces.

for (int i = 0; i <= rowIndex; i++) {
    sol = C(rowIndex, i);
    v.push_back(sol);
}

Answer 3

Types are very important in C++.

You are being sloppy with your types.

 long long sol;      // big int object.

While you are putting it into an object that only holds int

 vector<int> v;       // Only takes int
 v.push_back(sol);    // push long long and thus truncate

Answer 4

I am kind of curious why you separated the Int variable out of the for loop?

    int i;

    for(i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
    }

I would think that you would only do this if you want the variable outside of the loop, but it is the variable makes the loop function, you don't want it's scope to be that public, something may come along and break your loop (or make it infinite)

it should look like this

    for(int i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
    } 

Answer 5

As an interviewer, I'd see a big red flag in the implementation. Calculating each coefficient from scratch results in a lot of unnecessary recalculations.

Use recurrence: you already know \$\binom{n}{r}\$, so \$\binom{n}{r+1}\$ is just one multiplication and one division away.

Answer 6

I would advise you to use the same notation in the code as was presented to you in the challenge. Switching from k to rowIndex to n just causes confusion.

Answer 7

That's an interesting interview question, since it raises some issues you should point to.

The main drawback of your solution isn't lack of optimization. It's the fact it gives wrong results, even for early rows, due to overflow. Falling factorial is not the way to go! David's answer allows you to overcome this issue, but there is a simpler solution: \$\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}\$. No division, no multiplication, sir. Sometimes \$O(k^2)\$ additions is preferable to \$O(k)\$ multiplications and divisions. You don't have to choose: proposing several approaches is appreciated.

Also, since the \$O(k)\$ space was emphasized, you should reserve(k). With native types, no more allocation, madam. And better locality if traversing the same vector again and again with the additive generation method.

We may furthermore imagine 2 vectors - it's still \$O(k)\$ - one for odd rows, one for even rows, allowing a safe parallelization. You don't have to program this solution, but you may earn extra bonus points by simply evoking it.

Finally, you may list some ways to test your implementation (e.g., comparing some rows against reference, or testing some properties of the Pascal's triangle).