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

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;
}
};

• If this is for an interview I would make it understandable at a glance. This means writing in such a way that the code is very nicely formatted and there are comments explaining the methodology and a description of the complexity you achieved. – Martin York May 29 '14 at 18:32
• I'm sorta confused by all these people trying to guess what challenges might be thrown at them in an interview. Interviewers who ask this sort of question aren't expecting you to write perfect code on the spot or to show off your complete mastery of the language; what they're looking for is insight into how you think about problems and approach solving them. Micro-optimization happens AFTER you've written the code, which happens AFTER you've solved the problem. What would be more beneficial would be to be able to discuss why you've chosen a particular approach or algorithm. – keshlam May 30 '14 at 1:05
• I would have used Boost or other lib, or at least asked that first. Not only shows that you are aware of existing solutions, but also that you would not try to reinvent the wheel... but well, this is code review. – Jorge Leitão May 30 '14 at 8:19
• @TorbjornDiderholm: O(k) space is trivial. You just maintain two rows in the triangle. This is O(2k) => O(k). Writing the algorithm only using two rows is trivial as you use one for the current row and one for the next row you can then iterate towards the solution. – Martin York May 30 '14 at 16:53
• Consider getting rid of that horrible brace style in that last for loop. – Paul Draper Jun 1 '14 at 5:03

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(k2) 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.

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);
}

• This may seem trivial, but you can teach skills. Laziness is much harder to knock out of someone. Sloppy formatting is a bigger red flag to me than a suboptimal algorithm from a junior developer. – David Harkness May 30 '14 at 3:26
• @DavidHarkness: Interesting. Is this suggesting that my answer may not be too helpful if the OP doesn't bother to adopt them, or quite the opposite? – Jamal May 30 '14 at 3:39
• Your answer is supremely helpful whether or not the OP follows your advice. If they don't, hopefully others reading it will and I can waste less time every day cleaning up poorly-formatted code. – David Harkness May 30 '14 at 4:11
• @DavidHarkness: Thanks for the clarification. This was actually inspired by Winston Ewert's top answer, which heavily criticized the OP's interview code along the same lines. I suppose this is something more expected from, say, an applicant fresh out of college who should at least be able to pay attention to detail. – Jamal May 30 '14 at 4:14
• I put adhering to some consistent format on par with spell checking a term paper. If you can't be bothered to take this basic step, it indicates to me that you don't really care about your peers. You may care, of course, just as leaving dirty dishes doesn't prove your lack of care for your housemates, but it's a good leading indicator. Why not take 2 mins to properly format your code to remove a red flag? CR isn't an interview where "every minute counts" (BTW, that doesn't even apply during the interview), so there's no excuse to leave code unformatted. – David Harkness May 30 '14 at 4:27

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

• oj.leetcode.com/problems/pascals-triangle-ii I didn't use it intentionally ,the structure is as it is,but on putting data type as int for int sol, I thought integer overflow may occur . – swapedoc May 29 '14 at 18:52
• If there is a possibility of overflowing then the vector should also use long long. You may preserve the value in sol but as soon as you put it into the vector the value is truncated (so you loose the information). – Martin York May 29 '14 at 19:57

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;
}

• Ah, I've missed that. As this is C++, and not pre-C99, there's no reason to have it outside of the loop. – Jamal May 29 '14 at 18:47
• Was there ever a reason to declare it outside the loop? What changed in C99 to make it okay? I honestly don't know enough C/C++ internals to guess at a reason, but I'm definitely curious. – David Harkness May 30 '14 at 3:23
• @DavidHarkness Prior to C99 (e.g. ANSI C) it is illegal to declare the loop variable inside the for construct. You have to declare it outside and then use it. It is also illegal to declare variables anywhere else than at the beginning of a scope block. – Thomas May 30 '14 at 6:24

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.

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.

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).

• Actually C(n, r) = C(n-1, r) + C(n-1, r-1) gave me a "time limit exceeded" . – swapedoc May 30 '14 at 19:18