Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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 optimised 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; 
        }
    };
share|improve this question
11  
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. –  Loki Astari May 29 at 18:32
10  
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 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. –  J. C. Leitão May 30 at 8:19
1  
@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. –  Loki Astari May 30 at 16:53
1  
Consider getting rid of that horrible brace style in that last for loop. –  Paul Draper Jun 1 at 5:03

7 Answers 7

up vote 19 down vote accepted

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.

share|improve this answer

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);
}
share|improve this answer
3  
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 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 at 3:39
2  
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 at 4:11
1  
@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 at 4:14
1  
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 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
share|improve this answer
    
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 at 18:52
4  
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). –  Loki Astari May 29 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;
    } 
share|improve this answer
3  
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 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 at 3:23
1  
@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 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 C(n, r), so C(n, r+1) is just one multiplication and one division away.

share|improve this answer
    
A very good point sir!! –  swapedoc May 29 at 19:40

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.

share|improve this answer

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 allow to overcome this issue, but there is simpler yet : C(n, r) = C(n-1, r) + C(n-1, r-1). No division, no multiplication, sir. Sometimes O(k²) 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 simply evoking it.

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

share|improve this answer
    
Actually C(n, r) = C(n-1, r) + C(n-1, r-1) gave me a "time limit exceeded" . –  swapedoc May 30 at 19:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.