一种“查找共同祖先”的变体

Question

最近我进行了一次电话面试，面试过程中需要编写代码解决问题。这个问题是树的最近公共祖先的变形，但有一些特别之处。这棵树更像一个图，即子节点可以连接在一起。例如：

     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]，其父节点是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;            
    }

我没有收到前进的电话。由于我是“自学”的，我很想了解我在这里出了什么问题。由于这是技术问题，我相信这不是主观问题，希望我能从有经验的人那里得到帮助。
作为同事程序员，你会如何处理这个问题，以及如何评估我的解决方案？我需要做什么来提高我的技能？
您可以尽可能直接地表达。只要我能理解出了什么问题并且能够学习，我就满意。

- Cratylus

---

@Tudor：在我看来似乎是正确的。也许你应该将答案作为递归示例的参考。 - Cratylus

其实它并不是很好。它给出了所有向上的路径，但从那里找到共同点却很困难。我使用 BFS 开发了另一个解决方案，但最后我注意到它几乎与你的一样，只是可能更加结构化。所以干得好，我猜。 :) - Tudor

@Tudor：干得好？但我甚至没有得到个人面试……我猜这是黑色幽默 ;) - Cratylus

我注意到的一个区别是，我使用的是LinkedHashSet，它保留了节点的插入顺序，因此您可以从左到右查找第一个匹配项。无论如何，面试不成功可能有很多其他原因... - Tudor

Answer 1

我甚至不清楚这里的“most closest”是什么意思。请考虑以下图表：

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

这里有A和B的2个共同祖先，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更为复杂。除非告诉我如何做出选择，否则我无法确定正确的算法。

- Keith Randall

---

但是这里的根节点是哪个？因为问题不是关于图而是带有“扭曲”的连接子节点的树。根节点是1个节点。 - Cratylus

@Cratylus：只需将H和E添加一个共同的祖先即可。 - Keith Randall

从你的图纸上看，我认为A和B的最近公共祖先是X。你为什么说它是H和E？ - Cratylus

@Cratylus：抱歉，X只是一条交叉的线，不是节点。愚蠢的ASCII艺术... - Keith Randall

我建议您进行先序遍历，并在访问节点时保持存储，每当您遇到任何两个节点时，保存该字符串。因此，在您的示例中，我们将有2组字符串{IHGA，IHA}，{IHFB，IEDCB}。现在，对于集合中的每个字符串，在集合B中找到最长的公共前缀，最深的那个将是您的答案。 - Peter

Answer 2

很好的问题，你确实花了心思来写这篇文章。对于面试失败我感到很抱歉，我知道当这样的事情发生时会让人感到非常沮丧。现在让我们来看看这个问题。

一个想法是，你可以递归地向上移动，直到从两个目标节点到达根节点，并建立两个列表。最后，在这两个列表中找到第一个公共节点即可。

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

编辑: 仔细想想，这不是一个很好的想法，因为它基本上向上进行深度优先搜索，使得查找第一个共同祖先变得困难。更好的想法是为每个目标运行广度优先搜索（这可能与您的解决方案相似: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;
}

然后使用另一个映射表找到第一个共同祖先：

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

- Tudor

---

+1. 哦，将其分成两个单独的递归方法。不知何故，我的思维一直“黏”在如何对给定方法进行递归上，无法想出这个解决方案。 - Cratylus

@Cratylus：我稍微修改了代码，以相反的顺序返回节点（即从目标节点返回到根节点）。 - Tudor

@Cratylus：我找到了一个更好的解决方案。请查看编辑内容。它与您的解决方案非常相似，尽管我更喜欢使用两个BFS搜索，然后比较列表。这似乎更容易理解。 - Tudor

@Cratylus：最终我决定让它保留未删除，因为对我来说似乎更清楚正在发生什么，并且使用“LinkedHashSet”使得搜索共同祖先比我在您的代码中看到的更容易。 - Tudor

Answer 3

考虑以下您图表的变化...

              A
              |
          X---B---Y
           \ / \ /
            C   E  
            |   |
            D   F
             \ /
              G

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

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

我认为当程序遇到节点"C"时会遇到困难，因为它有两个父节点需要探索。您可以使用递归算法或使用迭代算法管理未探索节点的堆栈。

由于您似乎偏向于迭代，您可以尝试类似于以下内容：

创建一个数组（或类似的数据结构）。每个数组元素都保存三个信息：

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

创建堆栈。每个堆栈元素包含三个信息：

 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.

算法：

 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)

一旦从起始参考节点的所有路径都已经被评估完毕，栈便为空。如果给定节点名存在共同祖先，则其pathLength值皆不为无穷大。将这些值加在一起可以得到到达该共同祖先的总路径长度。报告拥有最小总和的节点名。此文与IT相关。

- NealB

---

你能举出两个节点的例子，说明在这张图上，OP算法会失败吗？ - Tudor

如果存在多个共同祖先，并且从目标节点1到祖先“X”是一条短路径，但从目标节点2到祖先“X”是一条非常长的路径，则可能会出现这样一种情况，即“X”可能会优先选择不同的共同祖先“Y”，其中从目标节点1到“Y”的路径比“X”稍微长一些，但从目标节点2到“Y”的路径比“X”要短得多。在这种情况下，我倾向于选择“Y”作为最近的共同祖先。OP的程序将基于从一个起始节点而不是两个起始节点的最短路径选择“X”。 - NealB

@NealB: 但是祖先们被放在一个“队列”中，所以如果一个节点有多个父节点，所有的父节点都将被放置在队列中，当我从“队列”中移除时，我会处理这个节点。应该是while(!path.isEmpty()){ String currentParent = path.remove();} 这部分做了这个操作。你是说在你的测试例子中这部分是错误的吗？ - Cratylus

@Cratylus 抱歉，我回答的第一部分有些“跑题”。你是正确的，使用队列（或堆栈）将使您通过给定起始节点的所有路径（这里唯一的区别是BFS vs DFS）。然而，“最近的共同祖先”仍然是一个问题，如果“最近”的意思是从两个起始节点到一个公共节点的组合路径长度。这就是为什么我添加了关于维护每个起始节点到公共节点的pathLength并寻找最小和的部分。如果“最近”的意思是仅从targetNode1的最短路径，则您最初的方法与任何方法一样好。 - NealB

Answer 4

我不能告诉你为什么公司没有回复你。但是，将代码提取到更小、有意义的方法中，而不是使用一个单一的大方法来处理所有详细的低级逻辑，会极大地改善你的代码。虽然我还没有尝试编译你的代码并在一些测试用例上运行它，但只是从快速阅读中，我并不完全相信这段代码是正确的。最接近的公共祖先可能是targetNode1或targetNode2（比如说如果targetNode2是targetNode1的父节点）。（我猜这取决于你如何定义“最近的公共祖先”——在这种情况下，你应该澄清它的含义。）

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

- Alex D

---

+1。是的，好观点！现在看来，你提到我会执行parentsSeen.add(targetNode1);以处理targetNode1是父节点的情况，但我没有为targetNode2这样做。 - Cratylus

@Cratylus，顺便说一下，如果你想找程序员的工作，可以通过像 oDesk 这样的在线招聘网站挑选一些工作。我已经为通过 oDesk 找到的客户自由职业了一年，效果非常不错。第一份工作是最难的，但之后就越来越容易（假设你成功完成了工作）。 - Alex D

我不知道这个。非常感谢你的提示！我会去看看的！ - Cratylus

Answer 5

更优的解决方案可能是使用布尔数组进行簿记。为每个节点设置一个布尔值数组，将它们全部初始化为false。当您访问一个节点时，将其设置为true。像今天一样交替向上移动“树”。一旦您到达已经访问过的节点（在数组中设置为true），那么您就找到了共同的祖先。

编辑：更好的方法是拥有一个整数数组，其中包含每个起始节点的唯一标识符。如果存在循环，我们需要知道谁已经访问了该节点，这可能是我们自己。

- Jens Agby

---

如何将节点与布尔数组的索引关联起来？ - Cratylus

他们已经从给定的数组中拥有了一个索引；使用它。但是，如果存在循环，这种方法就会失败。 - sshannin

是的，如果存在循环，您必须为每个起始节点设置唯一标识符。请使用整数代替。 - Jens Agby

Answer 6

我可能误解了一些东西，但我认为你算法的这一部分可能会浪费大量时间来研究节点：

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

这似乎是一棵树的宽度优先搜索，但由于某个子节点有多个父节点，您可能会多次搜索相同的节点。

通过添加对您的parentsSeen集的检查，您可以停止浪费时间：

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

- Peter de Rivaz

Answer 7

给定目标节点 x 和 y，执行以下操作：

- 将 x 及其所有祖先添加到集合 S 中。 - 检查 y 是否在集合 S 中，如果不在，则检查 y 的父节点是否在集合 S 中，如果不在，则继续检查它们的父节点，依此类推。

运行时间为 O(n)。

- Avi Cohen

---

这与我正在做的有何不同？ - Cratylus

如果你正在做的是这个问题，那么一个运行时间为O(n)且解决非常不平凡的问题的算法有什么问题呢？请注意，它实际上并不是一棵树，因为一个节点可以有多个父节点，而且所有解决类似问题的标准算法都不适用于这个问题。 - Avi Cohen