Fibonacci Interview Question

Assessing someone’s technical skill level is a quite difficult thing when one only has 30 minutes.  Let me start by saying I am no expert at how to do this, but I would like to share my favorite interview question for assessing a developer’s experience the question is targeted for C# developers. However, most of it the question is applicable to Java developers as well.  The question goes like this, “Let’s pretend you are developing a math library for me, my program makes use of elements in the Fibonacci sequence.  As part of this I need you to write a function for me which can calculate the millionth element in the Fibonacci sequence. Though, that is not to say that is the highest element I need.

Now at most developers will give a variant of one of the following implementations.

A simple recursive definition:

public static class FibonacciBinaryRecursion
{
    public static int Fibonacci(int e)
    {
        if(e == 1)
        return 0;
        if(e == 2)
            return 1;
        return Fibonacci(e -1)+ Fibonacci(e-2);
    }
}

An implementation which uses a loop:

public static class FibonacciLooping
{
    public static int Fibonacci(int e)
    {
        if(e == 1)
            return 0;
        if(e == 2)
            return 1;

        int x = 0;
        int y = 1;
        int z = 0;
        for(int i = 2; i<e; i++)
        {
            z = x+y;
            x = y;
            y = z;
        }
        return z;
}

A more advance use of recursion:

public static class FibonacciLinearRecursion
{
    public static int Fibonacci(int e)
    {
        return Fibonacci(0,1,e);
    }
    private static int Fibonacci(int x, int y, int e)
    {
        if(e ==1)
            return x;
        return Fibonacci(y, x+y, e-1);
    }
}

All three of these implementations are good, in that they kinda work.  However, they all share the same mistake.  One of the important parts of the problem is I said I needed to retrieve the millionth element.  Each of these implementations ceases to work when I ask for any element > 47.  From a performance perspective the simple recursive algorithm is O(n*n), and both the advanced recursion and looping implementations are O(n). Now one may try to solve this problem by using longs instead of integers.

A simple recursive definition:

public static class FibonacciBinaryRecursion
{
    public static long Fibonacci(long e)
    {
        if(e == 1)
        return 0;
        if(e == 2)
            return 1;
        return Fibonacci(e -1)+ Fibonacci(e-2);
    }
}

An implementation which uses a loop:

public static class FibonacciLooping
{
    public static long Fibonacci(long e)
    {
        if(e == 1)
            return 0;
        if(e == 2)
            return 1;

        long x = 0;
        long y = 1;
        long z = 0;
        for(int i = 2; i<e; i++)
        {
            z = y+x;
            x = y;
            y = z;
        }
        return z;
}

A more advance use of recursion:

public static class FibonacciLinearRecursion
{
    public static long Fibonacci(int e)
    {
        return Fibonacci(0,1,e);
    }
    private static long Fibonacci(long x, long y, int e)
    {
        if(e ==1)
            return x;
        return Fibonacci(y, x+y, e-1);
    }
}

This is a nice try, and it shows an understanding of how to handle values bigger than an integer. However, it is at the same time incorrect because stops working if I request any index > 94.  Another solution would have been to use a float or double.  However, both of these solutions will only calculate approximations, which makes them (VERY) incorrect.

So finally we  get to the correct implementations. Now since I don’t expect anyone to know all the .net framework the exact type name (BigInteger) is not important as long as one can describe the type they need, or how they would roll their own.

A simple recursive definition:

public static class FibonacciBinaryRecursion
{
    public static BigInteger Fibonacci(long e)
    {
        if(e == 1)
        return 0;
        if(e == 2)
            return 1;
        return Fibonacci(e -1)+ Fibonacci(e-2);
    }
}

An implementation which uses a loop:

public static class FibonacciLooping
{
    public static BigInteger Fibonacci(long e)
    {
        if(e == 1)
            return 0;
        if(e == 2)
            return 1;

        BigInteger x = 0;
        BigInteger y = 1;
        BigInteger z = 0;
        for(int i = 2; i<e; i++)
        {
            z = x+y;
            x = y;
            y = z;
        }
        return z;
}

A more advance use of recursion:

public static class FibonacciLinearRecursion
{
    public static BigInteger Fibonacci(int e)
    {
        return Fibonacci(0,1,e);
    }
    private static BigInteger Fibonacci(BigInteger x, BigInteger y, int e)
    {
        if(e ==1)
            return x;
        return Fibonacci(y, x+y, e-1);
    }
}

All of these work! None of them are what I consider the best answer. I argue the best answer to this problem is to properly model the Fibonacci sequence as what it is, an infinite list of number. Doing this allows for some very interesting speed ups (request the 1,000,000 element and then the 1,000,001 without having to recalculate, or having to invent a new type to thread state from one call another).

public static class FibonacciLinq
{
    public static IEnumerable Fibonacci()
    {
        BigInteger x = 0;
        BigInteger y = 1;
        BigInteger z = 0;

        yield return x;
        yield return y;

        while(true)
        {
            z = x+y;
            yield return z;
            x = y;
            y= z;
        }
    }
}

This implementation maybe a good topic for a future post, as the yield keyword in C# is a not to well-known or understood bit of awesomeness which every serious C# developer should learn about.