0111facebook二面面筋

Augustus 发表于 2016-1-12 09:43
这个帖子看的让人心慌http://www.weiming.info/zhuti/JobHunting/32633765/

我的约谈邮件里没有cong啊

163 发表于 2016-1-12 15:28
多次调用是不是就是排成有序的？比如BST的结构？
这样一次插入就是 O(\log n)

其实面试官并没有要求那么深入，就是意思要我每次不仅仅返回总时间，顺带要返回merge后的intervals，就是返回pair<int, vector<Interval>> 。你说得很对，是可以实现log n的查找，但更新还是要O(n)的吧？

zjh08177 发表于 2016-1-12 15:42
其实面试官并没有要求那么深入，就是意思要我每次不仅仅返回总时间，顺带要返回merge后的intervals，就是 ...

不完全是。
虽然一次插入可能最坏要O(n)，但是一次插入的cost很大的话就说明你这一步扔掉了很多interval。
仔细分析一下就可以知道，这个cost 是 amortized O(\log n)的 （如果你从空的树开始插入）

就好比动态数组一样，如果你想加入一个新元素，那么load factor到了一定程度就会重新分配一个空间并做copy，虽然隔一阵就需要一次大的copy，但是平均来说，cost总是 O(1)的

163 发表于 2016-1-12 16:03
不完全是。
虽然一次插入可能最坏要O(n)，但是一次插入的cost很大的话就说明你这一步扔掉了很多interval ...

嗯，理解你意思了～～

大神啥时候归队？

163 发表于 2016-1-12 16:03
不完全是。
虽然一次插入可能最坏要O(n)，但是一次插入的cost很大的话就说明你这一步扔掉了很多interval ...

cost O(1)是指空间复杂度吧？

mchzh 发表于 2016-1-13 07:37
cost O(1)是指空间复杂度吧？

时间复杂度

求人品。。我二面拖到下周了。。感觉好悬。。

dummyshooter 发表于 2016-1-13 11:16
求人品。。我二面拖到下周了。。感觉好悬。。

不管怎样，现在只能好好准备！加油加油！！

Augustus 发表于 2016-1-13 06:03
大神啥时候归队？

你是在和我说嘛。。