google new grad电面面经

熊孩子

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

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

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

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

0_-

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

熊孩子

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

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

DylanZhang

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

wtcupup

先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，直接找最小的就好啦

ootsuka

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

pkk5488

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

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

420402033

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

wtcupup

贴个 python 代码

class TreeNode:
def __init__(self, x):
self.val = x
self.children = []
'''
a
b d c
c d a
find lexical smallest leaf to root path, in this case we have paths cba, dba, da, aca, smallest is aca
'''
root = TreeNode('a')
root.children.append(TreeNode('b'))
root.children.append(TreeNode('d'))
root.children.append(TreeNode('c'))
root.children[0].children.append(TreeNode('c'))
root.children[0].children.append(TreeNode('d'))
root.children[2].children.append(TreeNode('a'))
def findLexicanSmallestPath2(root):
def dfs(root):
if not root.children:
return root.val
return min(dfs(child)+root.val for child in root.children)
return dfs(root)
print('lexical smallest leaf to root path:')
print(findLexicanSmallestPath2(root))

复制代码

熊孩子

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

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