2 ms·
Yes, when I say "factorial function" I mean the factorial function, taking an integer input n and returning the integer output n!. If cletus meant "factorial a
by cperciva 15y ago
Yes, when I say "factorial function" I mean the factorial function, taking an integer input n and returning the integer output n!.
If cletus meant "factorial as long as the result is a 32-bit integer", I don't know why he would accept an O(n) solution to that: I wouldn't hire anyone who didn't immediately produce the obvious O(1) algorithm using a 13-element lookup table. (If he meant "factorial modulo 2^32", a 34-element lookup table suffices.)
As for being snide... yes, but I'm tired of the myth that Google is full of (and only hires) algorithms gurus. I have yet to see any indication that Google requires any more than a minimal undergraduate level of algorithmic competency.
- ramchip 15y ago> I don't know why he would accept an O(n) solution to that Because it's a question used to weed out early stage candidates. It's a fizzbuzz test. The point is not to see if the candidate knows the algorithmic complexity of arbitrary-sized integer operations, and neither is it to see if he knows whether the factorial function grows quickly enough to make a look-up table worthwhile. It's just to take a very simple function and get him to write some code in a text editor. Or at least, that's what I read from the OP's post. Perhaps he meant otherwise.