4 ms·
Extra bonus points if they reduce quadratic to linear time with something like def pascal_row(n): row = [1] for i in range(1,n+1): row.
by gjm11 15y ago
Extra bonus points if they reduce quadratic to linear time with something like
def pascal_row(n):
row = [1]
for i in range(1,n+1):
row.append(row[-1]*(n+1-i)/i)
print row
(and more if they can talk intelligently about additions versus multiplications and divisions, the cost of [].append(), when if ever linear-versus-quadratic actually matters, bignum arithmetic, etc., etc., etc.).
- WildUtah 15y agoYeah, I finished the article still wondering when he was going to get to one of the good solutions. A programmer with good math should be able to write a nice linear time solution right away. And that's one more reason why it's a terrible question. If you're looking for good programmers and not math whizzes then the solutions in the article tell you more. But they're all badly suboptimal if you know what you're doing. If you don't know what you're doing, the best answer is that you'd Google for it on Wikipedia.