Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
You can always use the golden ratio for the equation Fib(n) = (Gr^n-(-Gr)^(-n))/sqrt(5)... if you take the floor of this function that will return the nth fibonacci... a different way is obviously using recursion to do the brute force method... but this can be time and memory costly
Problem with this is floating point will have precision issues because of sqrt(5) and you might get wrong results when n is large. If you try to avoid precision issues and try to compute sqrt(5) using only integer arithmetic, you will realize that a fast way to do that is to first compute Fibonacci numbers!
Matrix method can avoid those issues and only uses integer arithmetic.
Use the matrix method. Search the web for more details.
- Anonymous April 04, 2012