狗家实习店面11.15，两轮背靠背

qpalzm0827 发表于 2017-11-16 09:49
你的算法比较高端

求不黑...线性的题目被我做成三方，妥妥地挂了

570468837 发表于 2017-11-16 09:52
请问LZ，面试官会把follow up也复制到google doc里吗？
好担心听不懂烙印的话。。。

你可以让他/她给你写下来，就说信号不好听不清就行了233 我就是这么干的

第二题 感觉像是找max height of tree, 这个并购像是一rooted tree

把root找出来, 然后找max height.

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

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

楼主请问是都做出来了还跪了吗。。。

用O(n)的时间找root，这个树遍历一遍找最长路径也是O(n), 所以总体用时是O(n)级别

temp007 发表于 2017-11-16 12:53
用O(n)的时间找root，这个树遍历一遍找最长路径也是O(n), 所以总体用时是O(n)级别

对每个root都要遍历找最长路径，最后应该是O(n^2)吧。
或者是我没理解你的意思？

570468837 发表于 2017-11-16 13:05
对每个root都要遍历找最长路径，最后应该是O(n^2)吧。
或者是我没理解你的意思？

我认为应该还是O(n)

因为从每个root 开始traversal 只会将connected的node都走完
可以想成每个node只会走过一次.

我的理解
一个公司只能被一个公司收购，则是类似多叉树的问题，求这个树的最长路径，有n个节点，每个节点都只用访问一次，所以时间是O(n)
不清楚为什么是O(n^2)

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

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