Looking at technical interview questions on the Internet it appears that getting candidates to write some code that prints out the Fibonacci series is quite popular. I personally prefer giving candidates slightly more relevant practical questions, but I thought I'd present the various solutions that one may take. For those of you who are unfamiliar with the Fibonacci series you should take a look at the Wikipedia page on it. Each number in the series is the sum of the previous two values except for the first and second numbers which are zero and one respectively. So the interviewer is expecting to see the following series of numbers:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584...
The Fibonacci series is often used by computer science teachers to teach recursion, even though this it is a poor fit (see: How Not To Teach Recursion). However in all likelihood this is what the interviewer is after, so the expected standard solution should look like this:
internal static int GetFibonacciValue(int number)
{
if (number < 0)
throw new InvalidOperationException("Negative numbers are not supported by this implementation");
if (number <= 1)
return number;
return GetFibonacciValue(number - 1) + GetFibonacciValue(number - 2);
}
A lot of people forget to check for a negative number check, so including it may even earn you "bonus points". If you want to have a little fun you could always use a terse lambda expression to solve it like this:
Func<int, int> fibonacci = null;
fibonacci = n => n > 1 ? fibonacci(n - 1) + fibonacci(n - 2) : n;
The problem with the approaches above is that they perform really badly because of their recursive nature, so you could always show off and tell them that there is a closed form of the solution which allows you to solve it in the following manner:
private readonly static double rootOfFive = Math.Sqrt(5);
private readonly static double goldenRatio = (1 + rootOfFive) / 2;
internal static int GetFinbonacciValue(int number)
{
return Convert.ToInt32((Math.Pow(goldenRatio, number) - Math.Pow(-goldenRatio, -number)) / rootOfFive);
}
If you forget the closed form you could also tell the interviewer that using a simple for loop is far more efficient and ask him if he would be satisfied with that:
internal static int GetFinbonacciValue(int number)
{
if (number < 0)
throw new InvalidOperationException("Negative numbers are not supported by this implementation");
if (number <= 1)
return number;
int runningTotal = 1;
int twoValuesBack = 1;
for (int n = 2; n < number; n++)
{
int previousTotal = runningTotal;
runningTotal = twoValuesBack + runningTotal;
twoValuesBack = previousTotal;
}
return runningTotal;
}
That should be enough for you to ace that question during your technical interview. You may be curious as to how significant the performance differences between the approaches are, so I timed how long each took to generated numbers from 0 to 121393. The graph below shows the average number of ticks it took to complete the operations.
If you are busy doing interviews, I hope this helps you out. Good luck!