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.