I agree. "adding the two numbers to the right and left of it on the row above it" makes no sense to me whatsoever. I could interpret that in about many different ways, and during an interview I'd probably crack. To put this in perspective, I got a 1450 on the SATs.

My thought process: I take a number, add the right and left on the same row, then put the result on the upper row. Or, add the left and right and current and put it on the row above. After a while I guess you mean any position is the sum of the numbers to the 1 position upper left and upper right.

> I could interpret that in about many different ways

If you look at the graphic that always comes with this question, there's only one way you could possibly interpret it. If you somehow misinterpret the text, you would know immediately when you test your mental model against the graphic.

To be fair, the screwed up formatting in the OP makes it a little harder to understand; in an interview it would be laid out correctly.

> My thought process:

Would you still think all of those with the diagram?

          1

         1 1

        1 2 1

       1 3 3 1

      1 4 6 4 1

    1 5 10 10 5 1

This phrase:

"...adding the two numbers to the right and left of it on the row above it..."

Doesn't make a whole lot of sense. What is the "it"?

row 1: is obviously easy. row 2: I think you are adding 0 to 1 and 1 to 0 to get 1 and 1 row 3: You are adding 0 + 1 for the first item, 1 + 1 for the second, and 1 + 0 for the third. row 4: You are adding 0 + 1 for the first number, 1 + 2 for the second...but the directions say "to the left AND right of it" which makes me think that the answer should be 4, not 3. 1 + 2 + 1. Really, you are only adding the number to the left of "it" (which still isn't clear). And actually, for the first half of the line you are adding the number to the left and for the second half of the line you are adding the number to the right.

What you want:

row 1: 0 + 1 row 2: 0 + 1, 1 + 0 row 3: 0 + 1, 1 + 1, 1 + 0 row 4: 0 + 1, 1 + 2, 2 + 1, 1 + 0 row 5: 0 + 1, 1 + 3, 3 + 3, 3 + 1, 1 + 0 row 6: 0 + 1, 1 + 4, 4 + 6, 6 + 4, 1 + 0

So I think your directions are probably confusing people.

Of course, you still probably aren't going to increase your percentages much, but you could be clearer in what the problem actually is.

Smart people suffer from analysis paralysis - that's why they suck at simple multiple choice questions. "But it could mean [...]"

No, just take the obvious.

> Each element in Pascal’s Triangle is found by adding the two numbers to the right and left of it on the row above it; where these don’t exist, they are assumed to be zero.

Subject of the sentence: 'Each element'

So, "adding two numbers to the right and left of it on the row above it" means "adding the two numbers to the above right and above left of an element."

> So I think your directions are probably confusing people

Not my directions!

Still, this thread should be useful to OP. There are people who get the problem, and there are people who don't get the problem, and smartness isn't the deciding factor.

(I'm stupid, and not a programmer, but I understood what the problem was and what the desired result would be. Other people are smarter than I am, and are programmers, but didn't seem to grok the question.)

Oops, didn't mean your directions but the OP's, of course. Just thought this thread was a good place for the answer and you had a nicely formatted pyramid.

And, for the record, I'm a programmer, think I'm reasonably intelligent, and still not entirely sure I get the question based on the description. Language is tough sometimes.

I don't understand why are people having troubles interpreting the text.

P(i,j) = the number at i-th row and j-th column, could be defined as:

P(i, j) = P(i-1, j-1) + P(i-1, j+1) - for the indented pyramid diagram

or

P(i, j) = P(i-1, j-1) + P(i-1, j) - for the non indented triangle (the way it would appear in a basic 2D data structure, eg: int P[][]).

Also, you will have to check if P(i-1,j-1) exists.

     def cal(n):
         if n == 1:
            return [1]
         else:
            x = cal(n-1)
            return [1] + [x[i]+x[i-1] for i in range(1,len(x))] + [1]

    I didnt know "Pascal’s Triangle" , nor did I google, maybe I just got lucky.
    (No CS degree, self-taught)

----------------------------------------------------------------------------------------------------------------------------

I'm not yet a great programmer, but no doubt I'm becoming one

Wanna hire me, for free :)

Location: SF,CA

----------------------------------------------------------------------------------------------------------------------------

my site: codefella.herokuapp.com

I remember seeing Pascal's triangle in high school algebra as a way to obtain the coefficients of a polynomial in the form (a+b)^n, i don't see how can one forget the concept, this is far from obscure maths knowledge.

There's nothing obscure about this. This is basic secondary school math.

I never studied it or even heard of it. So from my perspective it is obscure.

I've never needed this in my programming career up until now. Have you?

> That gibberish

No, it's a fairly straight forward and simple algorithm.

The only ambiguity is due to the fact that it references relative spatial positions...but this question always provides a graphic that makes everything completely clear:

       1
      1 1
     1 2 1
    1 3 3 1

If someone couldn't understand the question with that description and graphic, they are either having a "brain fart"/interview jitters or have some deficiency in their reading comprehension, spatial reasoning, etc that they need to work on. The former is perfectly understandable and will happen no matter what you do in the interview; the latter tells you that the interviewee needs work in some area which is useful information.

> You aren't testing programming, you're testing obscure maths knowledge

Not at all, to answer this question requires absolutely no previous knowledge. All you need to answer is in the question.

You can pretty much just translate the question directly into code:

    function getRow(n) {
        if (n == 1) return [1];
        if (n == 2) return [1, 1];
        var previous_row = getRow(n - 1);
        var current_row = []
        for (var i = 0; i < n; i++) {
            current_row.push(
            	(previous_row[i - 1] || 0) +
                (previous_row[i] || 0)
            );
        }
        return current_row;
    }

Took me maybe a couple minutes to translate the question into a fairly straightforward recursive function and type it out. From there it would be easy to improve in a lot of ways: caching, making it iterative, etc...all of which are relatively obvious and easy.

I doubt there are any interviewers who wouldn't be basically satisfied with the most brain dead implementation. That demonstrates basic competence. The question has ample room to demonstrate a variety of skills beyond that. I'd expect the better interviewees (even with little math skill/background knowledge) to at least be able to make some observations about the properties of the triangle. I'd also expect the better ones to be able to talk about different approaches and their benefits/drawbacks.

For candidates with better math skills or background knowledge, they might know offhand/be able to write a better algorithm for computing the nth row. If the interviewer is expecting that as a baseline, sure I agree that's a bit unreasonable...but I don't think that ever happens.

I think this is a perfectly fine interview question with the caveats that it's very well known (and hence there will be some with a solution memorized) and one shouldn't rely on it too much.

It helps to have a good interviewer who will be able to explain the purpose of the question, and guide the interviewee if they get stuck. This is holds true for any interview question though.

I think this is something you've studied and have entirely lost perspective. The way it is explained on the test actually does not make sense.

For example, does the triangle already exist or are we generating it/calculating it? Are we to iterate over the table? And if so then how? What data format is it in?

Let's also discuss this line:

> Each element in Pascal’s Triangle is found by adding the two numbers to the right and left of it on the row above it; where these don’t exist, they are assumed to be zero.

The way it is worded is just horrible. Try this one:

"At the tip of Pascal's Triangle is the number 1, which makes up the zeroth row. The first row (1 & 1) contains two 1's, both formed by adding the two numbers above them to the left and the right, in this case 1 and 0 (all numbers outside the Triangle are 0's). Do the same to create the 2nd row: 0+1=1; 1+1=2; 1+0=1. And the third: 0+1=1; 1+2=3; 2+1=3; 1+0=1. In this way, the rows of the triangle go on infinitly. A number in the triangle can also be found by nCr (n Choose r) where n is the number of the row and r is the element in that row. For example, in row 3, 1 is the zeroth element, 3 is element number 1, the next three is the 2nd element, and the last 1 is the 3rd element. "

With this diagram: http://www.mathsisfun.com/images/pascals-triangle-1.gif

> I think this is something you've studied and have entirely lost perspective.

I've studied programming sure; anyone who's studied programming should have no problem with this. In terms of this particular problem, not really. I've come across it before, and understood it immediately then as well.

I think you are fundamentally misunderstanding the process/reason behind such a question.

> For example, does the triangle already exist or are we generating it/calculating it? Are we to iterate over the table? And if so then how? What data format is it in?

These aren't reasonable/good questions. That is, only a person who hasn't paid attention, misunderstood the question, etc would ask these. They represent a flaw in the reader, not the problem as it was phrased.

I think the issue here is you just don't understand the process and reasoning behind this question. You seem to think it's some sort of "gotcha" when that's not the case at all. There's absolutely no reason you can't ask questions like you pose. Everyone sometimes has issues with the way things are worded...and being able to ask for clarification is important.

I don't see how your explanation improves anything; it doesn't add any information it's just more explicit and convoluted. Many (I'd say most) programmers can solve the problem easily the first time they encounter it with no background knowledge whatsoever. I did it, as have many others. There will be many people who need a little help, that's fine...this is not a test to weed them out. It's to weed out the people who don't ask for a little help, or just can't do it at all.

Most of the times and interviewer would intentionally omit some specifics about the problem the candidate must resolve, thus leaving room for questions. The questions the candidate asks in order to complete a certain task are as important as the task itself.

Regarding the above problem, in my opinion it has everything you need for a good understanding. The only thing it's missing would be some limits for n.

If you have trouble understanding this task, it means you have trouble understanding basic algorithmic problems as most of them are defined in a similar manner.

To also, answer jlangenauer's question: this would be a perfect interview task for a junior. If you find many candidates that fail this kind of problems, you should seriously consider a way of better screening your candidates. (phone interview, online tasks, etc).