google new grad电面面经

请问您oa完多久给的消息呢？

ootsuka 发表于 2018-10-6 02:46
请问您oa完多久给的消息呢？

差不多有一周的时间，hr发邮件让填写个背景调查和让上传成绩单，然后过了两三天发的电面通知。

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

DylanZhang 发表于 2018-9-29 13:18
这题感觉可以用bfs， 每层只走字母序最小的。 可以看做简化的trie。时间复杂度是O(n), 最坏情况是第二层有n ...

不行吧, 按楼主给的例子每层走最小的Bfs不就返回cba了吗？

xuantao427 发表于 2018-10-7 23:48
不行吧, 按楼主给的例子每层走最小的Bfs不就返回cba了吗？

对，我理解错了，我以为path是从root到leaf node， 如果是从leaf node到root，好像只能DFS，maintain 一个最优解. 复杂度应该是O(n^2)

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

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

DylanZhang 发表于 2018-10-8 01:34
对，我理解错了，我以为path是从root到leaf node， 如果是从leaf node到root，好像只能DFS，maintain 一 ...

时间复杂度应该是O(n)，对于每一个子节点，我们只需要visit一次吧。

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

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

DylanZhang 发表于 2018-11-11 02:09
额，的确每个节点只要visit一次，可是maintain最优解是需要O(hight)吧。如果这颗树前n/2是一条线，后n/2 ...

哦 了解，还考虑到了单词排序的时间复杂度～

感觉有点问题 如果只比较root到leaf的path的reverse大小的话，如果相同，不就还要比较后半段？这样的话，还要知道后半段的大小关系，且一条path的前后半段不能是同一条root -> leaf？求指点

补充内容 (2018-11-24 09:31):
啊抱歉 我的意思是如果要是leaf to leaf 的话 是不是要考虑我说的情况？