"寻找共同祖先"的变种

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"}, null}
基本上nodes[i]为父(s)parentNodes[i].
说实话,我完全惊慌失措(已经非常紧张)并且花了很长时间才找到答案.
虽然我认为这是递归求解的,但我想出了一个迭代解决方案,据我所知可行:我在队列中推送节点,然后首先上升第一个目标节点然后是第二个节点.一旦我找到一个已经遇到的节点,我认为它是解决方案(已添加注释以清除事物).

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

我无法告诉你为什么公司没有给你回电话。但是，通过将代码提取到更小、更有意义的方法中，而不是使用具有所有详细的低级逻辑的单个大方法，您的代码将会受益匪浅。尽管我还没有尝试编译代码并在一些测试用例上运行它，但仅通过快速阅读，我根本不相信代码是正确的。最接近的注释祖先可能是targetNode1 or targetNode2（假设 iftargetNode2是 的父级targetNode1）。（我想这取决于你如何定义“最近的共同祖先”的细节——你应该澄清在这种情况下它的含义。）

• 使用从节点到父节点的映射是一个好主意。但是您可以将构建该映射的代码提取到一个小方法中，并使用有意义的名称。
• 您可以定义一个通过图形实现广度优先搜索的方法（这本质上就是您在这里所做的）。targetNode1在和上使用相同的方法targetNode2。