Interview Questions - Fibonacci

04.28.08

I found a interesting interview questions that is most likely a bit over done, but I still like it, it reminds me of my intro to programming classes from back in the day, which for me was only about 5 years ago. This one concerns the Fibonacci Numbers. The problem is write the Fibonacci Sequence without Recursion. With Recursion the fib sequence is relatively easy:

public static int GetFibValueRecursive(int place)
 {
     if (place <= 0) return 0;
     if (place == 1) return 1;
     return GetFibValueRecursive(place - 1) + GetFibValueRecursive(place - 2);
 }

First step to this problem I would write a test to make sure my code is correctly solving the problem.

public void GetFibValue_GivenPlace_ReturnCorrectValue()
{
     Assert.AreEqual(0, Fibonacci.GetFibValue(-1));
     Assert.AreEqual(0, Fibonacci.GetFibValue(0));
     Assert.AreEqual(1, Fibonacci.GetFibValue(1));
     Assert.AreEqual(1, Fibonacci.GetFibValue(2));
     Assert.AreEqual(34, Fibonacci.GetFibValue(9));
     Assert.AreEqual(144, Fibonacci.GetFibValue(12));           
}


Then the code.
public static int GetFibValue(int place)
{
     if (place <= 0) return 0;
     int previous = -1;
     int result = 1;
     for (int i = 0; i <= place; ++i)
     {
         int sum = result + previous;
         previous = result;
         result = sum;
     }
     return result;
}

Bam! The Fibonacci Sequence without recursion of course if you wanted more than just a value for given place I would write it a little different perhaps return a list of values instead of a single value.
FibSequence.zip (71.66 KB)