FB 电话面经

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

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

rsm 发表于 2020-5-5 20:19
没明白。
请问如何对presum array进行binary search得到range值的上下边界？这个上下边界应该是在所有元 ...

不好意思说掉了，需要一个inorder array 和presum array。inorder array 搜index，presum直接擦sum

好像都是利口 easy 题哦 赞楼主

aprilcooper 发表于 2020-5-7 00:01
请注意看，是达到log(n)

算presum 不要O(n)?

wengjn 发表于 2020-5-5 11:12
好像都是利口 easy 题哦 赞楼主

我觉得linkedlist那题要做到O(1) space O(n) time 还挺难的了啊。
range sum 那题也稍微改了点，要求做preprocess，达到 log(n)的复杂度

楼主， 请问第一题是什么思路呢？  我能想到的o(n)时间， in-place只能是先reverse list, 再打印。
第二题能具体说下要求吗？  谢谢！

Thank you for sharing!

好人卡顺子 发表于 2020-5-5 16:14
楼主， 请问第一题是什么思路呢？  我能想到的o(n)时间， in-place只能是先reverse list, 再打印。
第二题 ...

第一题我也是这样答的，第二题先preprocess出一个presum array，然后binary search 那个range的lower & higher boundaries，然后通过presum array直接得出sum

aprilcooper 发表于 2020-5-6 11:13
第一题我也是这样答的，第二题先preprocess出一个presum array，然后binary search 那个range的lower & h ...

没明白。
请问如何对presum array进行binary search得到range值的上下边界？这个上下边界应该是在所有元素的array进行binary search才能得到吧？

第二题没太明白为什么必须要preprocess才能得到O(n)
如果是LC那道原题的话dfs也是O(n)啊

aprilcooper 发表于 2020/05/06 11:13:40
第一题我也是这样答的，第二题先preprocess出一个presum array，然后binary search 那个r...

请问lz第一题先reverse在print面试官说这样做可以吗？

徐小桃 发表于 2020-5-5 23:12
第二题没太明白为什么必须要preprocess才能得到O(n)
如果是LC那道原题的话dfs也是O(n)啊

请注意看，是达到log(n)