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.

Ukemi

From the Aikido Wikipedia page:

“Aikido training is based primarily on two partners practicing pre-arranged forms (kata) rather than freestyle practice. The basic pattern is for the receiver of the technique (uke) to initiate an attack against the person who applies the technique—the 取り tori, or shite 仕手 (depending on aikido style), also referred to as 投げ nage (when applying a throwing technique), who neutralises this attack with an aikido technique.[23]

Both halves of the technique, that of uke and that of nage, are considered essential to aikido training.[23] Both are studying aikido principles of blending and adaptation. Nage learns to blend with and control attacking energy, while uke learns to become calm and flexible in the disadvantageous, off-balance positions in which nage places them. This “receiving” of the technique is called ukemi.[23] Uke continuously seeks to regain balance and cover vulnerabilities (e.g., an exposed side), while nage uses position and timing to keep uke off-balance and vulnerable. In more advanced training, uke will sometimes apply reversal techniques (返し技 kaeshi-waza?) to regain balance and pin or throw nage.

Ukemi (受身?) refers to the act of receiving a technique. Good ukemi involves attention to the technique, the partner and the immediate environment—it is an active rather than a passive receiving of aikido. The fall itself is part of aikido, and is a way for the practitioner to receive, safely, what would otherwise be a devastating strike or throw.”

Yesterday I applied for a job at Amazon. By that I actually mean that I applied for an opportunity to apply for a job at Amazon. I was contacted by one of their recruiters who informed me that they would be in my area in the next month and would be conducting interviews for Senior Software Developer and Project Manager positions. While I am nowhere near ready for either of those positions in my career as a Software Developer, I was very interested in the preliminary code interview. Based solely on my curiosity about the form and format of the code interview I proceeded with the preliminary code interview provided by the recruiter.

Interviews for Software Developer positions commonly contain a programming component. The interview for the position I currently, and happily, hold was contingent on the completion of a coding challenge. For my current position we were asked to solve FizzBuzz in C# using the Visual Studio Unit Testing Framework and Test Driven Development. The reason for my curiosity about the Amazon interview was two-fold. First, I am not accustomed to the coding portion of the interview coming so earlier in the interview, in this case before the interview has actually been offered. Secondly, the coding interview was timed. The timed component of the preliminary interview seemed like a challenge. Amazon had thrown down the gauntlet and I had to answer.

Here is the setup for the challenge:

“To begin your test:

Step 1:     Click here:  http://SomeCodeInterviewTool.Somewhere

Step 2:     Read instructions and review sample question

Step 3:     Fill in your full name (First name, Last name) and email address

Step 4:     Start your test

General Instructions:  The problems can be completed in a variety of OO languages (C++, C#, Java, etc.).  Feel free to use a language in which you are comfortable and fluent.  When solving this problem, consider performance, memory utilization, code clarity, elegance and of course correctness of your solution.  (There are many ways to solve this problem. Please write the most efficient method possible).  Our preference is you complete the problems in the SomeCodeInterviewTool text boxes.  If you choose to solve offline and cut and paste into the tool, please state that at the very top of your solution.

Friendly Reminder:  Your test is being recorded in real time.  You have up to 60 minutes to complete your test.  Plan accordingly, as you will be given each question one at a time and will not be given the opportunity to edit an answer after you have moved onto the next question. Submissions taking longer than 65 minutes will not be considered.    When you are finished – click Submit Solution and you’re done!  Once you are finished, you will be able to review your answers, but again, you WILL NOT be able to make any changes.”

The questions were fairly academic question and could easily be answered by anyone who had obtained a computer science degree. The difficulty came with the fact that the challenge was timed and that these types of questions do not have one correct answer.

The outcome of the challenge was something of a disappointment. I read the first question and went off to the races. My inner Software Developer kicked in immediately and I was analyzing requirements, designing features, and wallowing in creative bliss. After 45 minutes of feeding my ADD monster, I realized that I had forgotten about the YAGNI principle, implemented many more features than were required to answer the question, and most likely blown my chance at completing the “Amazon Challenge” in the allotted time. I quickly regrouped and attempted to answer the final two questions as quickly as I could with the most trivial answers I could manage. To me, this was already a failure, but when I submitted the final answer and fount that I had taken 85 minutes to complete a 60 minute challenge, it was a complete failure.

Through this long winded recount of my failure to meet the challenge presented by Amazon, we reach my purpose. The purpose of this blog is to take known coding interview questions, analyze them, formulate requirements, find a complete solution, and present one or more solutions for the question. The question will be the kata; the nameless interviewer will be the tori; and I will be the uke. Ukemi will come through actively participating in the exercise and practicing different techniques of solving the problems presented, thus expanding my problem solving toolset.

I am certain that had I managed my time with a clock and not succumb to my ADD monster that I would have completed the “Amazon Challenge” with time to spare.  This was the first lesson I learned.