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
What a cool idea! Thanks for the heads up. I will be thinking....Interview Questions
ReplyDeleteA 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).
ReplyDeletedef 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)
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.
ReplyDeleteI 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.
An even simpler redundant way to calculate the nth row of pascals triangle that is probably just as fast as the one you posted:
ReplyDeletefrom 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
Ya the way have been give the code is good.Nice presentation!
ReplyDeleteQuestions