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

jfree811 发表于 2016-10-29 09:56
面google的时候也是最后一轮，遇到个零时叫来的中国人。一脸的不高兴，说话也懒得说的样子，轻的我听也听不 ...

哎，国人还要坑自己人

能问一下各位大神4sum如果要n方logn怎么做啊，谢谢谢谢！

4sum是输出一个解还是所有解？如果是所有解，那么下届是o(n^3)，不可能o(n^2 log_n)

whitney94 发表于 2016-10-30 02:52
能问一下各位大神4sum如果要n方logn怎么做啊，谢谢谢谢！

http://www.geeksforgeeks.org/fin ... -given-value-set-2/ FYI.

说有n方logn的可以看这个post
https://discuss.leetcode.com/topic/27445/lower-bound-%CF%89-n-3/3

pawprinter 发表于 2016-10-31 08:42
说有n方logn的可以看这个post
https://discuss.leetcode.com/topic/27445/lower-bound-%CF%89-n-3/3

不认同那个帖子，我已经回复了

coldknight 发表于 2016-10-31 12:35
不认同那个帖子，我已经回复了

Stefan也回复了，你可以看下，他的证明应该是对的

pawprinter 发表于 2016-10-31 22:29
Stefan也回复了，你可以看下，他的证明应该是对的

三哥要我输出所有解。艹

我也觉得lz应该能拿到offer

pawprinter 发表于 2016-10-31 22:29
Stefan也回复了，你可以看下，他的证明应该是对的

是的，他的证明没问题。我又回了他一个链接。我没权限在这里发链接。你再看看吧。

还有，我现在突然之间全糊涂了。Big O是upper bound of all cases啊，我一直以为是
average case呢。

比如我们为什么说quick sort是 O(nlogn)? 如果是worst case不是O(n^2)吗？是因为
优化partition可以避免吗？