title: A variation of the "Find common ancestor"
body: <p>I recently gave an phone interview.It involved coding of a problem as part of the process.<br>
  The problem was a variation of the <code>Find the most closest common ancestor of a tree</code> but with a <em>twist</em>. The tree was much graph-like i.e. child nodes could be connected. Example:  </p>
  
  <pre><code>     A   
     /  
    B 
    | \ 
    C  E  
    |  |  
    D  F  
    \  /  
     G   
  </code></pre>
  
  <p>In this case given this tree and the nodes <code>F</code> and <code>D</code> the resulting closest common ansestor would be <code>B</code>. The second twist was that the tree was presented as an array. The method to implement had the following input:<br>
  <code>public String getCA(String[] nodes, String[][] parentNodes, String targetNode1, String targetNode2)</code><br>
  In this example <code>nodes</code> = <code>{"G", "F", "E", "D", "C", "B", "A"}</code> and <code>parentNodes</code> = <code>{{"F","D"},{"E"}, {"B"}, {"C"}, {"B"}, {"A"}, null}</code><br>
  Essentially for <code>nodes[i]</code> the parent(s) is <code>parentNodes[i]</code>.<br>
  To be honest I panicked completely (was already pretty nervous) and took me <em>really really</em> long time to figure out an answer.<br>
  Although I think this is solved recursively I somehow came up with an iterative solution which as far as I can tell works:I push nodes in queue and go up the path first for the first target node and then the second node. Once I find an already encountered node I consider it as the solution (have added comments to clear things up).      </p>
  
  <pre><code>public String getCA(String[] nodes, String[][] parentNodes, String targetNode1, String targetNode2) {  
          if(nodes == null || parentNodes == null){  
              throw new IllegalArgumentException();  
          }  
  
          Map&lt;String, String[]&gt; map = new HashMap&lt;String, String[]&gt;();  
          for(int i = 0; i &lt; nodes.length; i++){  
              map.put(nodes[i], parentNodes[i]);  
          }  
          //These are the parents visited as we go up  
          Set&lt;String&gt; parentsSeen = new HashSet&lt;String&gt;();  
          parentsSeen.add(targetNode1);  
  
          Queue&lt;String&gt; path = new LinkedList&lt;String&gt;();  
          String[] parents = map.get(targetNode1);  
          //The root is the common parent  
          if(parents == null){  
              return targetNode1;  
          }   
  
          //Build the path up  
          for(String parent:parents){  
              path.add(parent);  
          }  
          while(!path.isEmpty()){  
              String currentParent = path.remove();  
              parentsSeen.add(currentParent);  
              parents = map.get(currentParent);  
              if(parents == null){  
                  continue;   
              }  
              for(String parent:parents){  
                  path.add(parent);  
              }  
          }  
  
          parents = map.get(targetNode2);  
          //It is the root, so it is the common parent  
          if(parents == null){  
              return targetNode2;  
          }  
          //Start going up for the targetNode2. The first parent that we have already visited is the common parent  
          for(String parent:parents){  
              if(parentsSeen.contains(parent)){  
                  return parent;  
              }  
              path.add(parent);  
          }  
  
          while(!path.isEmpty()){  
              String currentParent = path.remove();  
              if(parentsSeen.contains(currentParent)){  
                  return currentParent;  
              }             
              parents = map.get(currentParent);  
              if(parents == null){  
                  continue;  
              }  
              for(String parent:parents){  
                  path.add(parent);  
              }  
          }  
          return null;            
      }
  </code></pre>
  
  <p>I did not get a move forward call. Now due to the fact that I am "self-taught" I would be interested to understand how I messed up here. Due to the fact that this is technical issue, I believe it is not subjective matter and hopefully I could get help here from experienced people.<br>
  So as collegue programmers how would you handle the problem and how do you evaluate my solution? What do I need to do to improve my skills?<br>
  You can be as straightforward as you possible. As long as I can understand what went wrong and learn I am satisfied</p>