Scene 20 of Dynamic Programming in Core Technical Interview Questions for Software Engineers
By Amin Ariana — November 2001
Return the Nth element of the Fibonacci series (1, 1, 2, 3, 5, 8, 13, 21, ...) efficiently without using any FOR or WHILE loops.
Problem Statement
You are NOT allowed to use loops of any kind (e.g. FOR loop or WHILE loop). Write a method in C# or pseudo-code to return the Nth element of the Fibonacci series (1, 1, 2, 3, 5, 8, 13, 21, ...) efficiently.
Evaluation
- The idea to use recursion, and the completeness of the C# or pseudo-code (25%)
- Correctness of the algorithm, demonstrated by quick manual unit tests (25%)
- What is the time and space complexity of your algorithm? (25%)
- Can you do it in O(n) time and space? (if you originally didn't do it recursively, you did it correctly.) (25%)
Solution
My one line Ruby solution:
Testing:
Paul Hounshell 's pseudo-Java solution:
This two code samples are essentially doing an identical thing. Gotta love functional programming :)
References
University of Waterloo 2nd year assignment