Google MTV 电面+Onsite

请问lz
(2) 一个Binary Tree，每个Node都有value，在树中切掉一个edge，变成两个树，找出哪里切导致两个数的Value总和差值最小。

这个题你的解法是遍历每个节点，求（根节点的值 - 切断的节点的值）和（切断的节点的值）的差值的min吗

另外N-ary tree的解法能不能详细说下。谢谢

blactangeri 发表于 2015-10-16 08:49
请问lz
(2) 一个Binary Tree，每个Node都有value，在树中切掉一个edge，变成两个树，找出哪里切导致两个 ...

是这样的，当时没让写具体代码，只让写了写伪码~

blactangeri 发表于 2015-10-16 08:55
另外N-ary tree的解法能不能详细说下。谢谢

直接上代码吧，这样比较清楚！没有测试，可能有小bug，但是思路就是DFS + DP

1. class TreeNode {
   
2.     int val;
   
3.     List<TreeNode> children;
   
4.     public TreeNode() {
   
5.         val = 0;
   
6.         children = new ArrayList<TreeNode>();
   
7.     }
   
8. }
   
9. 
   
10. class Wapper {
    
11.     TreeNode node;
    
12.     int parentVal;
    
13.     public Wapper(TreeNode node, int parentVal) {
    
14.         this.node = node;
    
15.         this.parentVal = parentVal;
    
16.     }
    
17.     @Override
    
18.     public boolean equals(Wapper an) {
    
19.     return this.node == an.node && this.parentVal == an.parentVal;
    
20.     }
    
21. }
    
22. 
    
23. public int maxVal(TreeNode root) {
    
24.     if(root == null) return 0;
    
25.     HashMap<Wapper, Integer> map = new HashMap<Wapper, Integer>();
    
26.     return maxValRec(root, -1, map);
    
27. }
    
28. 
    
29. public int maxValRec(TreeNode node, int parentVal, HashMap<Wapper, Integer> map) {
    
30.     if(node == null) return 0;
    
31.     Wapper wa = new Wapper(node, parentVal);
    
32.     if(map.containsKey(wa)) return map.get(wa);
    
33. 
    
34.     int bestVal = 0;
    
35.     int max = 0;
    
36.     for(int i=1; i<=10; i++) {
    
37.         if(i == parentVal) continue;
    
38.         int sum = i;
    
39.         for(TreeNode child : node.children)
    
40.             sum += maxValRec(child, i, map);
    
41.         if(sum > max) {
    
42.         max = sum;
    
43.         bestVal = i;
    
44.         }
    
45.     }
    
46.     node.val = bestVal;
    
47.     map.put(wa, max);
    
48.     return max;
    
49. }

复制代码

所以有offer的都是第二天就联系么

storm_hair 发表于 2015-10-16 11:14
所以有offer的都是第二天就联系么

我是上周三面的，明天出结果，所以也等了10天左右。

还是被拒了，5555555555555555

oopghi 发表于 2015-10-17 10:29
还是被拒了，5555555555555555

lz加油。。。看来都答出来也没用啊。。

blactangeri 发表于 2015-10-17 11:05
lz加油。。。看来都答出来也没用啊。。

然后就立刻从了Tableau了，找工作到此为止~

oopghi 发表于 2015-10-17 11:09
然后就立刻从了Tableau了，找工作到此为止~

T非常不错了，我一直想去，可惜bar太高，直接悲剧了。恭喜lz找到好工作！