Interview Question for Intern at Google:

I learned a lot from http://knol.google.com/k/efficient-recursive-computation-of-fibonacci-numbers#
This may be the ultimate answer you want.

But I guess talking about 2 common methods (inefficient straightforward recursive way(O(2^N)?) and dynamic programming recursive (O(N))) are a minimal interviewers expect? I personally like the matrix way to solve the Fibonacci problem in O(LogN) time. The ma thematic way to compute in O(1) time may not be the answer CS people look for.