Option "Find a common ancestor"

Question

I recently gave a telephone interview. It included problem coding as part of the process.
The problem was changing Find the most closest common ancestor of a tree , but with a twist. The tree was a lot graphically, that is, child nodes could be connected. Example:

  A / B | \ CE | | DF \ / G 

In this case, given this tree and the nodes F and D , the resulting closest common anestor will be B The second twist was that the tree was represented as an array. The implementation method had the following input:
public String getCA(String[] nodes, String[][] parentNodes, String targetNode1, String targetNode2)
In this example, nodes = {"G", "F", "E", "D", "C", "B", "A"} and parentNodes = {{"F","D"},{"E"}, {"B"}, {"C"}, {"B"}, {"A"}, null}
Essentially for nodes[i] parent element (s) is equal to parentNodes[i] .
Honestly, I completely panicked (I was already quite nervous), and I really really wanted to find the answer.
Although I think this is recursively resolved, I somehow came up with an iterative solution that, as far as I can tell, works: I click the nodes in the queue and start the path first for the first target node and then the second node. As soon as I find a node I have already met, I consider it as a solution (added comments to sort them out).

 public String getCA(String[] nodes, String[][] parentNodes, String targetNode1, String targetNode2) { if(nodes == null || parentNodes == null){ throw new IllegalArgumentException(); } Map<String, String[]> map = new HashMap<String, String[]>(); for(int i = 0; i < nodes.length; i++){ map.put(nodes[i], parentNodes[i]); } //These are the parents visited as we go up Set<String> parentsSeen = new HashSet<String>(); parentsSeen.add(targetNode1); Queue<String> path = new LinkedList<String>(); 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; } 

I did not have a call forwarding. Now, due to the fact that I am "self-taught", I would be interested to understand how I got messed up here. Due to the fact that this is a technical issue, I believe that this is not a subjective issue, and I hope I could get help from experienced people.
So, as college programmers, how would you deal with this problem and how would you rate my decision? What do I need to do to improve my skills?
You can be as simple as possible. So far I can understand what went wrong and find out that I am satisfied.

Answer 1

It’s not even clear to me what “closest” means here. Consider the following graph:

  I /\ / \ / \ HE |\ /| | \ / | G \/ D | /\ | | / FC |/ \| AB 

There are 2 common ancestors A and B, H and E. H - distance 2 from A and B. E - distance 1 from A, but distance 3 from B. What do I choose?

Also, regardless of your answer to this question, finding a set of ancestors from one and then executing BFS from another does not work. Searching all the ancestors of A, and then executing BFS from B first finds H, and searching for all the ancestors of B, and then executing BFS from A first finds E. As an adversary, I can switch A and B so that your algorithm fails with respect to any choice which you do (choosing whether 2/2 or 1/3 is better).

Thus, the correct algorithm should be more complex than just calculating the plurality of ancestors plus BFS. And if you don’t tell me how to make this choice, I’m not sure that I can install the correct algorithm.

Answer 2

Very nice question, are you really making an effort to write this. I apologize for the interview, I know that it should be very unpleasant when such things happen. Let's look at the problem.

The idea that comes to mind is this: you can go recursively up until you reach the root of both target nodes and create two lists. In the end, just find the first common node in both lists.

 public static List<String> visitUpwards(Map<String, String[]> mapping, String current) { List<String> list = new ArrayList<String>(); list.add(current); if(mapping.get(current) == null) return list; else { for(String s: mapping.get(current)) { list.addAll(visitUpwards(mapping, s)); } return list; } } 

Change On the other hand, it was not a good idea, since it basically leads the search for DFS up, which makes it difficult to find the first common ancestor. It is best to run BFS for each goal (this may seem similar to your solution: D):

 public static Set<String> BFS(Map<String, String[]> mapping, String node) { Queue<String> queue = new LinkedList<String>(); Set<String> result = new LinkedHashSet<String>(); queue.add(node); while(!queue.isEmpty()) { String current = queue.remove(); result.add(current); if(mapping.get(current) != null) for(String s: mapping.get(current)) { queue.add(s); } } return result; } 

Then use another map to find the first common ancestor:

 Set<String> list1 = BFS(mapping, "D"); Set<String> list2 = BFS(mapping, "G"); System.out.println(list1); System.out.println(list2); Map<String, Boolean> src = new HashMap<String, Boolean>(); for(String s: list1) { src.put(s, true); } for(String s: list2) { if(src.get(s) != null && src.get(s)) { System.out.println(s); break; } } 

Answer 3

I can’t say why the company did not call you back. But your code will be of great benefit by extracting the code into smaller, more meaningful methods, rather than using one large method with all this detailed, low-level logic. And although I have not gone so far as to try to compile your code and run it on some test cases, just because of the quick read I am not at all sure that the code is correct. It is possible that the closest ancestors of the comments could be targetNode1 or targetNode2 (say if targetNode2 was the parent of targetNode1 ). (I think it depends on how you define the "closest common ancestor" - you should have clarified what that means in this case.)

• Using a map from node for parents is a good idea. But you can extract the code that builds this map into a small method with a meaningful name.
• You can define a method that implements a breadth-first search using a graph (which is essentially what you are doing here). Use the same method for targetNode1 and targetNode2 .

Answer 4

A more optimal solution would be to use an array of Boolean computing for accounting. One for each node. Direct them all to false. Set them to true when visiting node. Change your path up the tree just like you do today. As soon as you navigate to the already visited node (set to true in the array), you find a common ancestor.

EDIT: A better approach would be to have an array of integers with a unique identifier for each source node. If there are loops, we need to know who has already visited the node, it can be ourselves.

Answer 5

Consider the following version of your schedule ...

  A | X---B---Y \ / \ / CE | | DF \ / G 

nodes = {"G", "F", "E", "D", "C", "B", "A", "X", "Y"}

parentNodes = {{"F","D"},{"E"}, {"Y","B"}, {"C"}, {"X","B"}, {"A"}, null, {"B"}, {"B"}}

I think that your program encountered difficulty when it gets to node "C" , because it has two parents nodes for study. You need to either resort to a recursive algorithm or manage some kind of stack for unexplored nodes using an iterative algorithm.

Since you have a bias for the iterator, you can try something like this:

Create an array (or similar data structure). Each element of the array contains three pieces of information:

  nodeName: string - name of a node from your `nodes` string pathLength[2]: integer - array of minimum path length from refrence node (1 or 2). 

Create a stack. Each stack element contains three pieces of information:

  nodeName: string - name of a node to "explore" lengthToHere: integer - length of path from reference node to `nodeName` pathNumber: integer - 1 for first reference node, 2 for second. 

Algorithm:

  Initialize array with nodeName from nodes and set each pathLength to "infinity" Push both starting reference nodes onto the stack: push("F", 0, 1) push "D", 0, 2) Repeat until stack is empty: - pop(nodeName, lengthToHere, pathNumber) - update pathLength[pathNumber] of element having nodeName in array with minimum of its current value and lengthToHere - for each parent of nodeName push(parent, lengthToHere + 1, pathNumber) 

The stack is empty when all paths from the initial reference nodes have been evaluated. If there is a common ancestor and pathLength values ​​for this nodeName will be less than infinity. Add these values ​​together to give the total path length to this common ancestor. Provide the node name with the smallest amount.

Answer 6

For the given target nodes x and y do the following:

• Add x and all its ancestors to set S
• Check if y in S , if not, then check if parents are y in S , if not, then check if their parents are in S , etc.

Operating time O (n).

Answer 7

Maybe I didn’t understand something, but I think that this part of your algorithm can spend a lot of time studying nodes:

  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); } } 

It looks like the first tree search in width, but you can end up looking for the same nodes several times because the child has several parents.

You can stop the time spent by adding a check to your parents. Serial set:

  while(!path.isEmpty()){ String currentParent = path.remove(); if (parentsSeen.contains(currentParent)) { continue; } parentsSeen.add(currentParent); parents = map.get(currentParent); if(parents == null){ continue; } for(String parent:parents){ path.add(parent); } }