pascals_triangle.py

"""
I'm the CTO at a startup in London, so I'm spending a lot of my time interviewing developers 
as we try to grow our team. As part of that, I ask each of them to do what I consider to 
be a very simple programming exercise (See below.)
Yet, the results of this are disappointing. About 10% of candidates will be able to produce 
a solution in 10 minutes or less, another 30% of candidates will eventually produce something 
close to a solution in 30 minutes (though often with errors), and 60% of candidates will 
simply be unable to produce anything close to a solution. These are not junior or graduate 
developers, but senior, experienced programmers asking for £50k or £60k.

I try to make the candidates as comfortable as possible while doing this, but even 
so, the inability of 90% of the people I interview to develop a solution to a simple 
question is astonishing.

Am I being too hard on the candidates in asking them to do this?

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

This is, verbatim, the problem sheet I show them:

Pascal’s Triangle

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.

         1

        1 1
 
       1 2 1

      1 3 3 1

     1 4 6 4 1

    1 5 10 10 5 1

Write a function that takes a single integer n as a parameter and returns the nth row 
of Pascal’s Triangle.

For example:

pascal(1) should return [1]

pascal(4) should return [1, 3, 3, 1]
"""

def pascal_row(n, prev_row):
    
    if n <= 1:
        return prev_row

    prev_row_len = len(prev_row)
    next_row_len = prev_row_len + 1

    next_row = []
    
    for i in range(0, next_row_len):
        left = 0 if (i - 1 < 0) else prev_row[i - 1]
        right = 0 if (i > prev_row_len - 1) else prev_row[i]

        next_row.append(left + right)

    if n == len(next_row):
        return next_row
    else: 
        return pascal_row(n, next_row)

def pascal(n):
    return pascal_row(n, [1])

if __name__ == "__main__":
    print pascal(4)