fb onsite 这样“黑”的我真的很不舒服

dtccx 发表于 2016-11-1 13:38
楼主结果怎么样

没消息呢。准备明天Ping HR。应该是挂定了。

袁小喵 发表于 2016-11-1 16:49
哈哈哈哈楼主是处女座吗？脑补出一堆好好笑的画面~~实力那么牛一定offer多多！

害我伤心的前女友是处女座。你懂的。

感觉应该很有希望的吧。behavior如果拿来挂你真说不过去。。 fb算是很注重能力的

coldknight 发表于 2016-11-1 13:24
是的，他的证明没问题。我又回了他一个链接。我没权限在这里发链接。你再看看吧。

还有，我现在突然之 ...

不，Big-O并不是"upper bound of all cases"，而是"upper bound of XXX"。这个XXX根据不同的context可取“最差输入的执行时间” (worst time big O)，“所有case的平均执行时间期望” (average case big O)，甚至“最好输入的执行时间”(best case big O)。你甚至取任意特定输入的执行时间都可以。但是一般最常用的就是前两个。

之所以容易混淆，是因为多数常见算法的worst case O=average case O。比如常见排序算法中也只有Quicksort不满足这点。而对于不满足这点的实用算法，我们通常会强调average case，因为这个指标最实际。而且听上去好听一些。

证明worst case O，只需举出一个特例即可；而证明average case O，则需要经过一些数学分析了。对于需要列举所有quadruplet的4SUM来说，worst case O是O(N^3)，这点Stephan的证明没有问题，因为他举出了一个特例。但是average case究竟是什么，这点还需要进一步证明。

4sum的worst case最好就是O(n^3)了

stellari 发表于 2016-11-2 13:16
不，Big-O并不是"upper bound of all cases"，而是"upper bound of XXX"。这个XXX根据不同的context可取 ...

多谢详细解疑，现在明白了！ 我认为4sum Avg case 是 O(n^2*m) m是avg number of sum2 duplicates

心疼lz，请容我代表g给您砸一个大包裹

yjob2016 发表于 2016-11-6 07:19
心疼lz，请容我代表g给您砸一个大包裹

楼主，如果你下次怕被三黑，你一定要坚持把代码写完整，然后拍照留下证据，这样他就没有证据黑了