The Best Strategy

It is necessary to develop a strategy that utilizes all the physical conditions and elements that are directly at hand. The best strategy relies upon an unlimited set of responses.” – Morihei Ueshiba

Morihei Ueshiba, the founder of Aikido, understood that each attack would have multiple possible responses which could be applied to successfully defend against it, each defense would have multiple responses which could successfully break that defense, and that the best strategy in the fight was to use all the possible responses one had learned in order to successfully win the fight.

The questions in a coding interview are not made to have one right answer. Each has several answers all of which are appropriate in certain situations. The point of the question is to see how you think about the solution you provide. In this blog post I will present several solutions to the final question in the Amazon Challenge that I spoke about here. Each solution presented will use present a resolution to the weaknesses of the previous until an preferable solution is reached. The preferred solution is no better than the rest of the solutions in certain cases and is only preferred under general circumstances. All answer the question in an acceptable manner.

The last question in the amazon challenge was on that all Computer Science students will recall as it is used as the quintessential example of recursion. The question was stated in the code interview tool as follows:

Write an efficient function that returns the n’th Fibonacci number (There are many ways to solve this problem. Please write the most efficient method possible). Each Fibonacci number is the sum of the last two. The first 10 are: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.”

The easy answer is the one every Computer Science student is taught in whatever class where recursion is first discussed. The recursive solution is stated as follows:

 
public static int FibonacciRecursive(int n) 
{      
	if (n < 0)           
		throw new ArgumentOutOfRangeException("n");       
	
	if (n <= 1)           
		return n;       
	
	return FibonacciRecursive(n - 1) + FibonacciRecursive(n - 2); 
} 

This solution to the problem is beautiful and succinct. The naive Computer Science student likes it because it is tricky and easy to write. The recursive solution solves the problem and fulfills most of the requirements of the question. This is the solution I chose during the challenge because I was running out of time and it solved the problem. Unfortunately the recursive algorithm, while “efficient” in the sense that it is quick to write and beautiful in its simplicity, is not computationally efficient.

Analyzing the algorithm, the first thing to note is that the computational complexity of the solution is exponential. This is far from optimal and it certainly could be argued that this recursive solution is not efficient because computational efficiency is more important the efficiency in development of the solution. Because the time complexity is exponential, it begins to take a very long time to calculate fib(n) as n becomes trivially large (i.e. fib(40) takes 5.44 seconds and fib(50) takes longer than I am willing to wait). The reason for this is that the recursive solution duplicates a lot of the work that is does. This can be seen by looking at the call tree for fib(5):

                          fib(5)   
                     /             \     
               fib(4)                fib(3)   
             /      \                /     \
         fib(3)      fib(2)         fib(2)    fib(1)
        /     \        /    \       /    \  
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    \
fib(1) fib(0)

To resolve the time complexity issue, a solution that seems more trivial than the recursive solution can be used. Using dynamic programming, the repeated work done in the recursive calls to fib(n) can be avoided by storing all of the Fibonacci numbers, up to n, in an array they don’t have to be recomputed. The solution is coded as follows:

 
public static int FibonacciDynamic(int n) 
{      
	if (n < 0)            
		throw new ArgumentOutOfRangeException("n");

       int[] fibNumbers = new int[n + 1];
       fibNumbers[0] = 0;
       fibNumbers[1] = 1;

       for (var i = 2; i <= n; i++)
            fibNumbers[i] = fibNumbers[i - 1] + fibNumbers[i - 2];

       return fibNumbers[n];
}

This solution reduces the time complexity to linear time. That is a much better complexity than the recursive solution. This is more efficient, but still not most efficient. As n grows larger so do the space requirements of the dynamic programming solution. The resolution to the space issue is trivial. Since only the last two Fibonacci numbers are required to find the next one, the rest of the values can be forgotten as soon as they are not needed. The solution is written as follows:

 
public static int FibonacciDynamicOptimizedForSpace(int n) 
{      
	if (n < 0)           
		throw new ArgumentOutOfRangeException("n");       

	if (n <= 1)           
		return n;       

	int a, b, c;       
	
	a = 0;      
	b = 1;       
	
	for (var i = 2; i <= n; i++)      
	{           
		c = a + b;           
		a = b;           
		b = c;      
	}       

	return b; 
} 

Using only three variables instead of an array of n integers, the space requirements stay constant; however, the time complexity is still linear and not optimal. To get to the optimal solution, as far as time complexity is concerned, let’s look at another solution that has linear time complexity.

The next solution is based on the idea that the solution for each Fibonacci number is a system of equations (i.e. the solution for the ith Fibonacci number is f(i) = f(i-1) + f(i-2)). Because the solution is a system of equations, a matrix transform can be used to find the nth Fibonacci number. In order to get to the solution a method that can multiply matrices as well as a method to raise a matrix to a power are needed. Those methods are defined as follows:

private static void matrixMultiply(ref int[,] F, int[,] M)
{
     int a = F[0,0] * M[0,0] + F[0,1] * M[1,0];
     int b = F[0,0] * M[0,1] + F[0,1] * M[1,1];
     int c = F[1,0] * M[0,0] + F[1,1] * M[1,0];
     int d = F[1,0] * M[0,1] + F[1,1] * M[1,1];

     F[0,0] = a;
     F[0,1] = b;
     F[1,0] = c;
     F[1,1] = d;
}

private static void matrixPower(ref int[,] F, int n)
{
      int[,] M = new int[2, 2] { { 1, 1 }, { 1, 0 } };

      for (var i= 2; i<=n; i++)
		matrixMultiply(ref F, M);
}

With these tools written, the (n+1)th Fibonacci number can be found at the index [0,0] in the matrix computed by multiplying the transform matrix M={{1,1,{1,0}} by itself n times, or by calculating matrixPower(M,n). Since the nth Fibonacci is desired, the method will return the element at index [0,0] in the matrix computed by calculating matrixPower(M,n-1). This is done in the following code:

 
public static int FibonacciMatrixTransform(int n) 
{
     if (n < 0)
          throw new ArgumentOutOfRangeException("n");
      
     int[,] F = new int[2, 2] { { 1, 1 }, { 1, 0 } };

     if (n == 0)
           return 0;

     matrixPower(ref F, n - 1);
           return F[0, 0];
}

A full explanation of the thought process to reach this solution can be found here. While the above is a novel approach to solving the problem, it does not improve on the linear complexity already achieved by the dynamic programming solutions. The complexity can be reduced to logarithmic time by calculating the power of a matrix using recursive multiplication by doing the following:

 
private static void matrixPowerRecursive(ref int[,] F, int n) 
{
     if (n == 0 || n == 1)
           return;

     int[,] M = new int[2, 2] { { 1, 1 }, { 1, 0 } };

     matrixPowerRecursive(ref F, n / 2);

     matrixMultiply(ref F, F);
     
     if (n % 2 != 0)
          matrixMultiply(ref F, M); 
}  

and the final method which computes the nth Fibonacci number is as follows:

public static int FibonaccimatrixTransformOptimizedForSpeed(int n)  
{
       if (n < 0)
            throw new ArgumentOutOfRangeException("n");
     
       int[,] F = new int[2, 2] {{1,1},{1,0}};
 
       if (n == 0)
            return 0;

       matrixPowerRecursive(ref F, n - 1);
     
       return F[0, 0];
}

A few notes on my implementations:

  • I have chosen to use C# to code my examples because I feel that the syntax is standard enough among languages that those who don’t know the language can understand the intent of the code.
  • Since Fibonacci numbers are enumerable, n is in the set of natural numbers and cannot be less than 0, therefore if the value passed to any of the methods is less than 0 I throw an ArgumentOutOfRangeException so that the user can handle the exception. I prefer this to returning some invalid value because these are static methods and should work as designed without curious side effects such as returning a value that is not in the Fibonacci series.
  • For those who wish to test the code, the methods are all static members of a class named Fibonacci, and driven by a console application that reads as follows:
        class Program
        {
            static void Main(string[] args)
            {
                int n = 9;
    
                Console.WriteLine("Recursive: " + Fibonacci.Fibonacci.FibonacciRecursive(n));
                Console.WriteLine("Dynamic: " + Fibonacci.Fibonacci.FibonacciDynamic(n));
                Console.WriteLine("Dynamic Optimzed For Space: " +                 
                      Fibonacci.Fibonacci.FibonacciDynamicOptimizedForSpace(n));
                Console.WriteLine("Matrix Transform: " + Fibonacci.Fibonacci.FibonacciMatrixTransform(n));
                Console.WriteLine("Matrix Transform Optimzed for speed: " +   
                      Fibonacci.Fibonacci.FibonaccimatrixTransformOptimizedForSpeed(n));
                Console.ReadLine();
            }
        }
    
  • I would be very interested to hear other solutions readers may have that would optimize on the time complexity.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s