google new grad电面面经

上周四面的狗家的电面，今天刚收到hr电话通知onsite，发个面经为onsite攒一波人品

美国小哥，上来什么都没

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

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

，楼主用dfs暴力解的，解完也没有follow up，分析了下复杂度就结束了。
看近期面经感觉狗家近期的难度有些下降，祝各位找工顺利哈~

发现大家都喜欢往高深里扯。 其实就是一个二叉树遍历， 扯啥BFS DFS的。

420402033 发表于 2018-9-29 07:26
请问下lz什么叫字母顺序。。？

就是比如比如a < b， aa < b， 两个string谁的第一个字符小谁就小，如果相等再比较第二个，这样字，java里面可以用String.compareTo直接比就好了

这题感觉可以用bfs， 每层只走字母序最小的。 可以看做简化的trie。时间复杂度是O(n), 最坏情况是第二层有n - 1个节点。最好情况是每层有两个节点，只需要O(log n).

先generate all root to leaf paths 然后path reverse 一下再sort 嘛？

wtcupup 发表于 2018-9-29 03:45
先generate all root to leaf paths 然后path reverse 一下再sort 嘛？

不用sort，直接找最小的就好啦

请问是 用DFS把从root经过所有的节点字母加起来，返回最小的path就好了是吧～

wtcupup 发表于 2018-9-29 03:45
先generate all root to leaf paths 然后path reverse 一下再sort 嘛？

每次找到一个答案和原有的比较一下，看看要不要更新就好啦

请问下lz什么叫字母顺序。。？

贴个 python 代码

1. class TreeNode:
   
2.     def __init__(self, x):
   
3.         self.val = x
   
4.         self.children = []
   
5. '''
   
6.               a
   
7.           b   d  c
   
8.         c  d         a
   
9.         
   
10. find lexical smallest leaf to root path, in this case we have paths cba, dba, da, aca, smallest is aca
    
11. '''
    
12. 
    
13. root = TreeNode('a')
    
14. root.children.append(TreeNode('b'))
    
15. root.children.append(TreeNode('d'))
    
16. root.children.append(TreeNode('c'))
    
17. root.children[0].children.append(TreeNode('c'))
    
18. root.children[0].children.append(TreeNode('d'))
    
19. root.children[2].children.append(TreeNode('a'))
    
20. 
    
21. 
    
22. def findLexicanSmallestPath2(root):
    
23.     def dfs(root):
    
24.         if not root.children:
    
25.             return root.val
    
26.         return min(dfs(child)+root.val for child in root.children)
    
27.     return dfs(root)
    
28. 
    
29. print('lexical smallest leaf to root path:')
    
30. print(findLexicanSmallestPath2(root))

复制代码

ootsuka 发表于 2018-9-29 06:30
请问是 用DFS把从root经过所有的节点字母加起来，返回最小的path就好了是吧～

是的，不过可以每个subtree都返回当前subtree的最小path，这样就不用全部放在root节点比较了