java - "Find common ancestor"的变体

Question

我最近接受了一次电话采访。它涉及将问题编码作为过程的一部分。
问题是 Find the most closest common ancestor of a tree 的变体，但有一个扭曲。这棵树很像图，即可以连接子节点。示例:

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

在这种情况下，给定这棵树和节点 F 和 D，得到的最接近的共同答案将是 B。第二个转折点是树以数组的形式呈现。实现方法具有以下输入:
public String getCA(String[] nodes, String[][] parentNodes, String targetNode1, String targetNode2)
在这个例子中 nodes = {"G", "F", "E", "D", "C", "B", "A"} 和 parentNodes = {{"F","D"},{"E"}, {"B"}, {"C"}, {"B"}, {"A"}, 空
本质上，对于 nodes[i]，parent(s) 是 parentNodes[i]。
老实说，我完全 panic (已经很紧张了)，花了我真的很长时间才找到答案。
虽然我认为这是递归解决的，但我以某种方式提出了一个迭代解决方案，据我所知，它是有效的:我将节点插入队列并首先沿着路径向上移动到第一个目标节点，然后是第二个节点。一旦我找到一个已经遇到的节点，我就将其视为解决方案(已添加注释以清除问题)。

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

我没有接到前进电话。现在由于我是“自学成才”的事实，我很想了解我是如何搞砸这里的。由于这是技术问题，我认为这不是主观问题，希望我能在这里得到有经验的人的帮助。
那么，作为同事的程序员，您将如何处理这个问题以及您如何评估我的解决方案？我需要做什么来提高我的技能？
你可以尽可能直截了当。只要我能明白哪里出了问题并学习我就满足了

Answer 1

我什至不清楚这里的“最接近”是什么意思。考虑下图:

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

这里有 2 个 A 和 B 的共同祖先，H 和 E。H 与 A 和 B 的距离为 2。E 与 A 的距离为 1，但与 B 的距离为 3。我应该选择哪个？

此外，无论您对该问题的回答是什么，从一个祖先中找到一组祖先然后从另一个中进行 BFS 是行不通的。找到 A 的所有祖先然后从 B 做 BFS 首先找到 H，找到 B 的所有祖先然后从 A 做 BFS 首先找到 E。作为对手，我可以切换 A 和 B 以使您的算法在您做出的任何选择(选择 2/2 或 1/3 更好)方面失败。

所以正确的算法一定比仅祖先集计算加上 BFS 更复杂。除非你告诉我如何做出选择，否则我不确定我能否确定正确的算法。