Fibonacci numbers are a sequence of numbers defined by following formula:
ωn=ωn-1+ωn-2
The first number of the sequence is 0, the second number is 1, and each subsequent number is equal to the sum of the previous two numbers of the sequence itself, yielding the sequence 0, 1, 1, 2, 3, 5, 8, etc. ().
Being very simple from the one side and quite sophisticated from the other Fibonacci numbers are the perfect candidate for the technical coding interview. During my last year job hunt, I actually end up answering questions about Fibonacci numbers on every other interview I had.
So, let’s start with the most common question and possible solutions:
Problem 1. Write a function which return Nth number of Fibonacci sequence
The most simple and the most popular solution you would see during the interview employ recursive nature of the sequence.
Possible solution #1 – Recursion
static int Fibonacci (int n)
{
if(n < 0)
throw new ArgumentException("Input parameter invalid");
int N;
if (n == 0) N = 0;
else
if (n == 1 || n == 2) N = 1;
else
N = Fibonacci(n - 1) + Fibonacci(n - 2);
return N;
}
While totally valid, this is probably the worst solution you can give during the interview. Recursion in this case is total overkill as it requires keeping all sequence in the memory.
Possible solution #2 – Iteration
static int Fibonacci (int n)
{
int index1 = 1, index2 = 1;
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
int current;
for (int i = 2; i <= n; i++)
{
current = index1+index2;
index1=index2;
index2= current;
}
return current;
}
This is way better solution which is still not the optimal one in term of performance but the one interviewer is looking for. Hmm... not optimal, so what would be the optimal one?
Possible solution #3 – Computational (Closed form expression)
This is simple calculation of closed form expression for Fibonacci numbers:
static double Fibonachi(int n)
{double gr = ((double)1 + Math.Sqrt(5)) / 2;
double grN = Math.Pow(gr, n);
double gr_1 = Math.Pow(((double)1 - gr), n);
return (grN-gr_1)/Math.Sqrt(5);
}Problem 2. Write a function which would print Fibonacci numbers up to given maximum
While, all solutions above are very easy to modify to fit this scenario it is good if you can through something extra in your answer to stand out of the crowd. So in order to do so, I would use enumerator. Certainly be prepare to discuss how yield operator works and what might resulting code look like then compiled into MSIL.
Possible solution:
static IEnumerable Fibonacci(double maxPosition)
{
double current = 1;
double previous = 0;
for (double i = 0; i < maxPosition; i++)
{
if (i > 1)
{
var oldCurrent = current;
current = current + previous;
previous = oldCurrent;
yield return current;
}
else
{
yield return i == 0 ? previous : current;
}}}
Problem 3. Write a function which would check if a given number belongs to Fibonacci sequence
The easiest way is to generate Fibonacci numbers till this number and see if this number is one of them and again it probably the answer interviewer is looking for. However there is couple over ways which might impress interviewer.
Possible solution:
It turns out that a positive integer ω is a Fibonacci number if and only if one of 5ω2 + 4 and 5ω2 - 4 is a perfect square [The (Fabulous) FIBONACCI Numbers by Alfred Posamentier and Ingmar Lehmann]
bool isFibonacci(int w){
double X1 = 5 * Math.Pow(w, 2) + 4;
double X2 = 5 * Math.Pow(w, 2) - 4;
long X1_sqrt = (long)Math.Sqrt(X1);
long X2_sqrt = (long)Math.Sqrt(X2);
return (X1_sqrt*X1_sqrt == X1) || (X2_sqrt*X2_sqrt == X2) ? true : false;
}
As I always iterate, try to direct interview into area you know well. As I already mentioned, one approach for this particular question is to provide iterator solution and demonstarte your advance knowledge. Another is to talk about strategy pattern as this is a really good demonstration for different strategies you might want to use in different curcumstances.
If you want to learn more Mathworld provides very nice overview:
