I'm just surprised nobody has mentioned calculating the solution directly using factorials or some builtin n choose k function.

Or the even-less-computationally-intensive algorithm: http://en.wikipedia.org/wiki/Pascals_triangle#Calculating_an...

Thats what dspeyer did here: http://news.ycombinator.com/item?id=3431687 .

For an algorithms heavy job, I would hope a candidate would be able to derive this equation with a little guidance (ie, reminding them about n choose k and how to write that with factorials)

Very nice but expecting the candidate to know that much about Pascals triangle upfront seems a bit too much ;)

Factorials risk integer overflow in the intermediate calculations, though something similar can work.

Yes, it seems a number of optimizations are possible. At least it is not necessary to calculate n!. Depending on the job discussing these strategies and whether they are worthwhile for some real world problem can be quite interesting.

True, but could just anyone write it as offensively as the below Python one-liner?

(Were one to ever write such code in production, he should be escorted from the building immediately!)

    from itertools import tee, izip, chain
    pascal = lambda rows: reduce(lambda acc,n: acc+[(lambda it: [sum(x) for x in (lambda it,n=2: izip(*((lambda it,n: ([next(it) for _ in xrange(n)],it)[-1])(it,pos) for pos,it in enumerate(tee(it,n)))))(chain((0,),it,(0,)))])(acc[-1])], xrange(rows), [[1]])

    num_rows = 10
    print '\n'.join( ' '.join(map(str,row)) for row in pascal(num_rows) )

PHP Version I came up with. Took more than 10 minutes tho... for ($i=0; $i<=10; $i++) { if ($i== 0) $row[$i] = array(0, 1, 0); else { $row[$i] = array(); array_push($row[$i], 0); for($j = 0; $j<count($row[$i-1]); $j++) { $someval = $row[$i-1][$j]+$row[$i-1][$j+1]; array_push($row[$i], $someval); } } for($k = 1; $k<count($row[$i])-1; $k++) { echo $row[$i][$k]; } echo "<br />"; }