Keeping Centered

The key to good technique is to keep your hands, feet, and hips straight and centered. If you are centered, you can move freely. The physical center is your belly; if your mind is set there as well, you are assured of victory in any endeavor.”

– Morihei Ueshiba

Keeping centered is as important in combat as it is in problem solving. Interview questions are sometimes meant to be trick questions or be worded so as to confuse the candidate. These are meant to discover how well the candidate can act under pressure and if they can quickly reduce a confusing problem to a more fundamental problem with a known answer.

The second question posed in the Amazon Challenge was one meant to confuse and derail thought. The question is stated as follows:

Assume primitive Facebook. FB has Members.

public class Member {
    public String name;
    public String email;
    public List<Member> friends;
}

Question:
Code printSocialGraph(Member m). Direct friends of m are Level 1 friends. Friends of friends are level 2 friends…..and so on. Print level 1 friends first. Then print level 2 friends….and so on.”

There is a lot of information to process in this question, but the problem becomes trivial as soon as the candidate takes time to re-center and dissect the question. The key discoveries to be made are:

  1. This is a problem relating to a graph.
  2. This is a breadth-first search of an undirected graph where each node is printed based on degree of separation from the starting node.

These two important pieces of information can be deduced easily from the question. The first is noticed through two facts; the name of the method that the candidate is expected to implement (printSocialGraph), and the fact that the list, of type Member, named “friends” that is part of the Member class is a list of adjacency relationships. The second is discovered through assumption based on the requirements of the method. The candidate must reverse engineer the tool to be used to solve the problem from the second part of the question. Since the question states the requirement of the method as, “Print level 1 friends first. Then print level 2 friends….and so on,” what algorithm will traverse a graph starting with one node, visiting all nodes adjacent to it, then visiting nodes adjacent to those, and repeating until all nodes have been visited? A breadth-first search.

With the solution apparent, the only thing left to do is implement a breadth-first search that prints each node as it is visited while keeping track of the degree of separation from the starting node. That is done as follows:

  1. Verify that the starting member is a valid member and throw an exception if it is not valid.
  2. Create a queue and Enqueue the beginning member on the queue.
  3. Create a hash to keep track of all the members that were already visited. (A hash is used for performance purposes since it is the fastest collection I know of to search in the C# language. If the social graph is very large this can save a few cycles.)
  4. Add the beginning member to the list of already visited members.
  5. Create a counter to keep track of the level (degree of separation).
  6. Print the value of the level counter.
  7. Dequeue the top member off of the queue.
  8. Create a temporary list and store the top member’s friend list in it.
  9. Loop over the temporary list of friends; if the friend has been printed, go to the next friend; otherwise, print the friend, add it to the printed hash, and Enqueue all of their friends onto the queue.
  10. Increment the level by one.
  11. Print the value of the level counter.
  12. If there are still members on the queue, go back to step 7.

The C# code is as follows:


public void printSocialGraph(Member member)
{
     if (member == null)
          throw new ArgumentOutOfRangeException("member");

     Queue<Member> QueueOfMemebers = new Queue<Member>();
     HashSet<Member> Printed = new HashSet<Member>();
     QueueOfMemebers.Enqueue(member);
     Printed.Add(member);

     int level = 1;

     Console.WriteLine("Level " + level + " friends");

     while (!(QueueOfMemebers.Count == 0))
     {
          Member tempMember = QueueOfMemebers.Dequeue();
          List<Member> TempMemberFriendList = tempMember.friends;

          foreach (var friend in TempMemberFriendList)
          {
               if (Printed.Contains(friend)) continue;

               Printed.Add(friend);
               Console.WriteLine("Name:" + friend.name + ", Email:" + friend.email);
               foreach (var friendOfFriend in friend.friends)
               QueueOfMemebers.Enqueue(friendOfFriend);
          }

          level++;
          Console.WriteLine("Level " + level + " friends");
      }
}

Keeping centered allows one to give a balanced response to even the most befuddling attacks. Re-centering and re-evaluating after being confused will help to solve any problem.

Advertisements

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.