Java – a variant of “looking for a common ancestor”

I recently had a telephone interview It encodes the problem as part of the whole process

A   
   /  
  B 
  | \ 
  C  E  
  |  |  
  D  F  
  \  /  
   G

In this case, given the tree and nodes F and D, the closest common ancestor will be B. the second twist is that the tree is presented as an array The implementation method has the following inputs: 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"}, {"a"}, null} basically for nodes [i], the parent node is parentnodes [i]. To tell you the truth, I am completely panicked (already very nervous) And it took a long time to find the answer Although I think this is a recursive solution, I have come up with an iterative solution. As far as I know, it is feasible: I push nodes in the queue, and then rise the first target node and then the second node Once I find a node i have encountered, I think it is the solution (annotated to clear things)

public String getCA(String[] nodes,String[][] parentNodes,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 didn't get a forward call Now that I'm "self-taught", I'm interested in understanding how I screwed up here As this is a technical problem, I don't think it is a subjective problem. I hope I can get help from experienced people So, as a colleague programmer, how would you handle this problem? How would you evaluate my solution? What do I need to do to improve my skills? You can be as straightforward as possible As long as I can understand what the problem is and learn it, I will be satisfied

Solution

I don't even know what "closest" means Consider the following chart:

I
   /\
  /  \
 /    \
H      E
|\    /|
| \  / |
G  \/  D
|  /\  |
| /  F C
|/    \|
A      B

There are two common ancestors a and B, h and E. h is the distance between a and B E is distance 1 from a, but distance b is 3 Which do I choose?

In addition, no matter what your answer to this question is, it doesn't work to find a group of ancestors from one person and then make a BFS from another person Find all ancestors of a, then BFS from B, find H first, find all ancestors of B, and then BFS from a, find e first. As an opponent, I can switch between a and B to make your algorithm fail, no matter what choice you make (2 / 2 or 1 / 3 is better)

Therefore, the correct algorithm must be more complex than ancestor set calculation plus BFS Unless you tell me how to make this choice, I'm not sure if I can determine the correct algorithm