Tuesday, January 10, 2012

Interview Question: Pascal's Triangle

William Shields published a blog post about using Pascal's Triangle as an interview question.

http://goo.gl/nGvye

I found it interesting since I had been presented with this same problem during a technical interview.  At the time, I solved it but not in a efficient way.  Afterwards, I worked through it for myself and came up with a version similar to the dynamic approach on his blog.

On the blog, the code for the dynamic solution is incorrect.  (N.B. I've changed the range from 20 to 300.)


prev = []
for row in xrange(300): 
    curr = [1] 
    for index in xrange(1, row):
        curr.append(prev[index-1] + prev[index]) 
    curr.append(1) 
    print curr 
    prev = curr


The code should read:

prev = [1]
print prev
for row in xrange(300): 
    curr = [1] 
    for index in xrange(1, row):
        curr.append(prev[index-1] + prev[index])
    curr.append(1) 
    print curr 
    prev = curr

Since the right half of the row is the reverse of the left half, you can make it just a little faster by:
prev = [1]
print(prev)
for row in xrange(1, 300):
    curr = [1]
    if row > 5:
        mid = (row / 2) + 1
        if row % 2 != 0:
            right = mid + 1
        else:
            right = mid - 1

        for index in xrange(1, mid):
            curr.append(prev[index-1] + prev[index])
        
        r = curr[0:right]
        r.reverse()
        curr.extend(r)
    else:
        for index in xrange(1, row):
            curr.append(prev[index-1] + prev[index])
        curr.append(1)
    print curr
    prev = curr

I ran each version 10 times and this saves, on average, 0.049 seconds over 300 rows.

5 comments:

  1. What a cool idea! Thanks for the heads up. I will be thinking....Interview Questions

    ReplyDelete
  2. A better way is to construct the dictionary taking into account pythons d.get function, which allows you to set a default value (in this case, 1).


    def pascal(final_row):
    """Returns the row from Pascal's triangle"""
    tri = {}
    assert(final_row > 1)
    for row in range(final_row):
    for col in range(1, row):
    tri[(row, col)] = tri.get((row-1, col), 1) + tri.get((row-1, col-1), 1)
    l = []
    row = final_row -1 # obwan from the row
    for col in range(final_row):
    l.append(tri.get((row, col), 1))
    return l

    pascal(300)

    ReplyDelete
  3. This works for very small values like the 300 in the example. It will, however, not scale because it is so memory intensive. Look at the later entry on profiling where the sample is 10,000 rows.

    I tried running your code on a machine with 8GB of memory with a value of 10,000 and in less than 1 minute all of the memory was committed. The swap space was quickly used up and the machine started thrashing to try to accommodate the size of the dictionary. I let it run for two hours and since it had not finished, I killed the process.

    So, an interesting approach but not scalable.

    ReplyDelete
  4. An even simpler redundant way to calculate the nth row of pascals triangle that is probably just as fast as the one you posted:

    from operator import add
    def pascalsTriangle(n):
    row = [1]
    if n<=1: return row
    for i in xrange(n-1):
    row=map(add, [0]+row, row+[0])
    return row


    ReplyDelete
  5. Ya the way have been give the code is good.Nice presentation!

    Questions

    ReplyDelete