6

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

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

在这种情况下，给定这棵树和节点F以及D由此产生的最接近的公共 ansestor 将是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;            
    }

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

4

7 回答 7

4

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

    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 更复杂。除非你告诉我如何做出选择，否则我不确定我能否确定一个正确的算法。

于 2012-08-28T03:58:46.927 回答
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;
    }
}

编辑：再想一想，这不是一个好主意，因为它基本上是向上进行 DFS 搜索，因此很难找到第一个共同祖先。一个更好的主意是为每个目标运行 BFS（这可能看起来类似于您的解决方案：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;
    }
}
于 2012-08-27T20:21:59.483 回答
1

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

编辑：更好的方法是为每个原始节点设置一个具有唯一标识符的整数数组。如果有循环我们需要知道谁已经访问过该节点，那可能是我们自己。

于 2012-08-27T20:10:21.407 回答
1

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

  • 使用从节点到父节点的映射是一个好主意。但是您可以将构建该映射的代码提取到一个具有有意义名称的小方法中。
  • 您可以定义一个通过图形实现广度优先搜索的方法（这基本上就是您在这里所做的）。targetNode1在和上使用相同的方法targetNode2。
于 2012-08-27T19:59:32.540 回答
1

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

              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)

一旦评估了来自起始参考节点的所有路径，堆栈就为空。如果有一个共同的祖先，则给定 nodeName 的两个 pathLength 值都将小于无穷大。将这些值加在一起，给出到这个共同祖先的总路径长度。报告总和最小的 nodeName。

于 2012-08-28T01:42:04.960 回答
0

对于给定的目标节点x并y执行以下操作：

  • 将x其所有祖先添加到 set S。
  • 检查是否y在S，如果不是，则检查其父母y是否在S，如果不是，则检查其父母是否在S，依此类推。

运行时间为 O(n)。

于 2012-08-28T08:44:39.963 回答
0

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

   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);  
        }  
    }
于 2012-08-28T16:47:33.190 回答