5 ms·
I'm just surprised nobody has mentioned calculating the solution directly using factorials or some builtin n choose k function.
by Bootvis 15y ago
I'm just surprised nobody has mentioned calculating the solution directly using factorials or some builtin n choose k function.
- dspeyer 15y agoFactorials risk integer overflow in the intermediate calculations, though something similar can work.
- Bootvis 15y agoYes, 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.
- derefr 15y agoOr the even-less-computationally-intensive algorithm: http://en.wikipedia.org/wiki/Pascals_triangle#Calculating_an_individual_row_or_diagonal_by_itself http://en.wikipedia.org/wiki/Pascals_triangle#Calculating_an...
- Bootvis 15y agoVery nice but expecting the candidate to know that much about Pascals triangle upfront seems a bit too much ;)
- lightcatcher 15y agoThats what dspeyer did here: http://news.ycombinator.com/item?id=3431687 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)