全新谷歌full time电面

给一堆(int, int)的input表示一个tree（不一定binary），前一个int表示parent，后一个表示child，对所有

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ld
     output：
10 10
15 15

我的想法是先遍历一遍这一对(parent,child)对，然后用一个set放leaf，一个map放(child,parent)对，然后set里面的leaf用dfs向上找
parent，找最大的ancestor的值，这过程中可以用一个hashmap记录每个node的最大的ancestor，来避免重复寻找

不建树：

1. class SolutionWithoutTreeConstruction:
   
2.     def getLeafMax(self, edges):
   
3.         if not edges: return
   
4.         leaves = set()
   
5.         allNodes = set()
   
6.         parentMap = {}
   
7. 
   
8.         # construct parentMap and leaf set
   
9.         # {10: 5, 15: 5, 5: 8, 6: 8, 7: 6}, set([10, 15, 7])
   
10.         for parent, child in edges:
    
11.             parentMap[child] = parent
    
12.             if parent in leaves:
    
13.                 leaves.remove(parent)
    
14.             if child not in allNodes:
    
15.                 leaves.add(child)
    
16.             allNodes.add(parent)
    
17.             allNodes.add(child)
    
18. 
    
19.         # Search for each leaf in the leaf set
    
20.         for leaf in leaves:
    
21.             curMax = leaf
    
22.             node = leaf
    
23.             while node in parentMap:
    
24.                 node = parentMap[node]
    
25.                 curMax = max(node, curMax)
    
26.             curMax = max(node, curMax)
    
27.             print leaf, curMax

复制代码

建树，然后DFS：

1. class TreeNode:
   
2.     def __init__(self, x):
   
3.         self.val = x
   
4.         self.children = []
   
5. 
   
6. class Tree:
   
7.     def __init__(self):
   
8.         self.root = None
   
9.         self.possibleRoots = set()
   
10.         self.nodes = {}
    
11. 
    
12.     def insertEdge(self, parent, child):
    
13.         if not self.root:
    
14.             parentNode = TreeNode(parent)
    
15.             childNode = TreeNode(child)
    
16.             self.possibleRoots.add(parentNode)
    
17.             parentNode.children.append(childNode)
    
18.             self.nodes[parent] = parentNode
    
19.             self.nodes[child] = childNode
    
20.         else:
    
21.             if parent in self.nodes and child in self.nodes:
    
22.                 self.nodes[parent].children.append(self.nodes[child])
    
23.                 if self.nodes[child] in self.possibleRoots:
    
24.                     self.possibleRoots.remove(self.nodes[child])
    
25.             elif parent in self.nodes and child not in self.nodes:
    
26.                 childNode = TreeNode(child)
    
27.                 self.nodes[child] = childNode
    
28.                 self.nodes[parent].children.append(childNode)
    
29.             elif parent not in self.nodes and child in self.nodes:
    
30.                 parentNode = TreeNode(parent)
    
31.                 self.nodes[parent] = parentNode
    
32.                 self.nodes[parent].children.apped(self.nodes[child])
    
33.                 if self.nodes[child] in self.possibleRoots:
    
34.                     self.possibleRoots.remove(self.nodes[child])
    
35.                 self.possibleRoots.add(self.nodes[parent])
    
36.             else:
    
37.                 parentNode = TreeNode(parent)
    
38.                 childNode = TreeNode(child)
    
39.                 self.possibleRoots.add(parentNode)
    
40.                 parentNode.children.append(childNode)
    
41.                 self.nodes[parent] = parentNode
    
42.                 self.nodes[child] = childNode
    
43.         if len(self.possibleRoots) == 1:
    
44.             self.root = list(self.possibleRoots)[0]
    
45. 
    
46.     def getLeafMax(self):
    
47.         node = self.root
    
48.         self.dfs(node, node.val)
    
49. 
    
50.     def dfs(self, node, curMax):
    
51.         if not node.children:
    
52.             print node.val, curMax
    
53.             return
    
54. 
    
55.         for child in node.children:
    
56.             self.dfs(child, max(curMax, child.val))

复制代码

额还没怎么刷LC，大神莫喷，但貌似不是Topological Sort，像是DP
我们给每个节点多包一层，储存: 自己的val, 目前为止从root到自己路径上最大的maxval, bool leaf 自己是否是叶子节点
然后，每一个新加的节点(parent, child)，做这些： parent.leaf = false, child.maxval = max(parent.maxval, child.val)，child.leaf = true
最后只要遍历leaf=true的即可
但我不知道这代码怎么写。。。。

补充内容 (2015-11-1 23:58):
噢存储的时候，不需要存父-子pair，用一个unordered_map<Node>存所有点即可，每次输入更新parent点和child点

深度优先遍历的同时 maintain 路径上的最大节点应该可以解决吧？

应该是首先建立二叉树，需要一个 HashMap 来记录 int -> node，然后 dfs

AndrewFish 发表于 2015-10-30 04:13
深度优先遍历的同时 maintain 路径上的最大节点应该可以解决吧？

啊我后来想得是直接用map<int, int>来存，child做key, parent做value，一个个往回search，然后用一个vector吧来记所有的leaf node，每插入一个node就看有没有leaf node变成了非leaf。

另:如果可能的话求其它公司内推。。

LeetCode course schedule 的变种吧？

这题应该正常方法解：就是建立一个树，然后DFS遍历。这题就是考你基本功。应该是warm up题。
其它方法复杂，要好好想想才行。而且复杂度一样。
你想复杂了。

补充内容 (2015-11-2 02:07):
比如：一个简单例子。1->2->3. 输入顺序是（2，3），（1，2）。
你要怎样建立这个child－》parent的tree？

maomaoxiong 发表于 2015-11-2 02:01
这题应该正常方法解：就是建立一个树，然后DFS遍历。这题就是考你基本功。应该是warm up题。
其它方法复杂 ...

这种建树只是warm up么。。我觉得要处理顺序关系就好复杂，不是几行就能解决的呀。。