Am I the only one who thinks that his "Example 2: Write function to compute Nth fibonacci number" is a terrible resource hog?
IMHO an iterative approach would be the way to go.
IMHO an iterative approach would be the way to go.
Firstly, in my direct, personal experience, just writing a candidate to write a program that compiles and runs gets rid of up to 90% of applicants. People here on HN are exceptional, but around 90% of recent applicants for a position I advertised couldn't write a FizzBuzz program that compiled and ran.
Secondly, these are the starting points. From here you can ask what problems the program has. Yes, it's exponential in stack and runtime. You can write an iterative version that runs in constant stack and linear time. More subtle, and more probing, is how do you write a recursive version that also runs in small stack and time.
These are the starting points, the initial cull. Don't assume they're the be all and end all.
Recursive Fibonacci numbers are also a good way to work Memoization into the picture.
I look for someone to sketch a correct algorithm using any notation they choose. Independently I look for someone to produce working code with an editor and compiler. The former is usually for something like linked lists or quicksort, the second for something like FizzBuzz and then recursive and iterative Fibonnaci.
Working code is essential for something, anything, at some point, although really what I want is someone who can then talk sensibly through the issues. Even so, working code for trivial problems is still only seen in about 10% of cases.
I helped interview someone who couldn't explain the trade-offs between a couple different designs for a simple class hierarchy, even an obviously wrong one included as a canary. Then we asked him to write one out, and, after stalling and getting several hints from us, he nervously scratched out a (naive) MySQL schema. Despite what his resume claimed, his only programming experience consisted of PHP and a fairly shallow understanding of SQL.
Are you returning a machine integer (long or otherwise)? Precompute them and use a freaking lookup table. The sequence grows so fast you'll never see more than maybe 60 or so terms.
Are you returning an arbitrary-size bignum? Use the closed-form solution based on powers of the golden ratio. It still runs in non-constant time (bignum math isn't free), but will run much faster than pointlessly enumerating the sequence up to that point.
Of course, I would be surprised if anyone asking about Fibonacci numbers in an interview has ever been looking for one of those answers. Usually it's a "FizzBuzz for recursion" question.
Incidentally, if you want arbitrary-sized bignum results as quickly as possible, you might do better with a "matrix-squaring" approach (equivalently: use the recurrences that give you F(2k) and F(2k-1) in terms of F(k) and F(k-1)) so that you stick with integer arithmetic.
If your bignum library isn't clever about multiplication, I suspect that the simple iterative solution is about as fast as anything else, but most bignum libraries have at least Karatsuba multiplication.
The closed form solution involves computing something raised to the power of n, so would be O(log n) assuming nonintegral multiplication is O(1), which is... not so much the case. Given that the (sqrt 5) factors will always be eliminated by the end you can manipulate things to work with only integers, at the expense of complicating the algorithm.
The matrix-based solution, which I had forgotten, is also of the form x^n, so is probably isomorphic to a sufficiently clever handling of Binet's formula that completely avoids the (sqrt 5) terms.
So, yes, good call, the matrix approach is better--you win this round.
[0] The naive un-memoized recursive algorithm, such as the recursive solution in the linked article, is not only not tail-recursive, but manages to have time complexity of precisely O(fib(n)). If that doesn't make you die a little inside, you're made of sterner stuff than I.
And yes, the naive recursive approach is a total disaster. Pretty code, though, and if you have language or library support for memoization you can just write the naive recursive function and demand that it be memoized.