Facebook 脸书 莫名其妙跪经

第一题我稍微写一下，用priority queue时间复杂度最优是没有问题的，但反馈中提到了speed / efficiency那就是期望对性能有相当程度的理解。这里的性能并不是纸上谈兵的时间复杂度，而是真正执行时机器所花的时间。

比方说：
(1) 考虑一个"naive"的实现：将所有的array拼接起来先放在output数组中，然后调用std::sort直接in-place排序output数组，比起heap哪个方法快，底层的原理是什么？
----
这点可能出乎很多人的预料，其实只有在k比较小的时候（例如32以下）或者是元素总数量非常大的情况下（例如100个million以上），heap的实际执行时间才优于"naive"的sort方法。这点楼主可以自己写代码测试一下。

我这边提供一个参考代码，用g++ -std=c++14 -O3 MergeSortedArrays.cpp可以编译：
https://github.com/jqdocshare/docs/blob/master/MergeSortedArrays.cpp

比如说1024个row，每个row有65536个元素，那么执行结果基本上会显示naive sort比heap merge要快一倍。

当然面试的时候肯定还是写heap代码，但是关键在于，一边写代码，一边要告诉面试官“根据我的经验，这样使用heap的代码只是面试时用用，在实际项目的典型场景下面，性能还不如拼接数组后直接sort，原因在于：(1) heap本身的overhead，(2) 树状结构访问时cache locality方面的问题 (3) sift down/up操作对于CPU branch prediction不友好，等等

(2) 如果使用标准库提供的容器/算法，要分析其不足之处
----
比如楼主提到了用priority queue，不管是C++和Java，其标准接口只是top()/peek()、pop()/poll()、push()/offer()这三个方法。

然而对于Merge K Sorted Arrays这道题目来说，只使用标准库提供的方法并不是效率最高的，其存在冗余操作：每次从heap中pop一个元素出来，为了维护堆结构会进行一次siftDown；而每次push一个元素，都会进行一次siftUp —— 也就是每merge一个元素需要进行两次时间为log(k)的sift（滚动）操作。但是，如果我们自己去写一个针对这道题目的heap的话，是可以每merge一个元素只进行一次siftDown的。

参考代码也在(1)中所给的文件里，执行后会发现"customized heap"性能是要比标准库priority queue要好的，但是没有快很多 —— 原因在于标准库有很多edge case的优化而这边只是简单写一下 —— 但至少在面试时要提到使用标准库时的这一不足之处。

(3) 即使是简单的题目也有很多拓展知识可以impress面试官 —— 特别是如果你让面试官自己都能学到新的东西的话
----
还是merge k sorted array这个问题，其实在C++的标准库libstdc++中有多线程实现的代码：
https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/parallel/multiway_merge.h

这个代码相当复杂，主要难题在于要将所有k个数组均匀分割（parition）成多段，每一段的元素不相交，参考这篇文章：
https://github.com/jqdocshare/docs/blob/master/multiseq_partition.pdf

以及C++标准库中parallel部分作者讨论并行多路归并排序（Parallel Multiway Mergesort）的ppt，从第11页开始：
http://ls11-www.cs.tu-dortmund.de/people/gutweng/AD08/VO11_parallel_mode_overview.pdf

fangwei007 发表于 2018-11-2 02:02
另外啊, 其实不想说, 但是 你分析heap的时间复杂度是错的, log(k*n) 是什么 ?
heap初始化是k*logk
然 ...

我觉得你分析的也是错的。。（我如果说错了别喷。。说错了那就是我算法课白上了。）
heap是klogk 但是最多有kn个element，你应该是pop一次，加上一个element吧？我觉得这样的话时间复杂度总共是 （kn - k) *klogk， 所以是你的做法应该是 O(k^2 * n * logk)。。我觉得时间复杂度最优应该是 O(k^2 * n)，空间复杂度 O(k)，额外用一个长度为k的array用了记每个array的current index（从0开始），每次先找到当前所剩的element中最小的一个数放进result list （因为是sorted array，访问每个array中在current index的数字就行），这个element所在的array的current index加一。直到访问完所有的element。。总共需要找最小值 kn 次，所以最后的时间复杂度是 O(k^2 * n)。。

补充内容 (2018-11-10 15:50):
啊 （kn-k)*klogk那里写错了。。应该就是kn*klogk。。还有就是每次找最小的值需要O(k)，所以是O(k^2 * n)

lllyyting 发表于 2018-11-10 15:47
我觉得你分析的也是错的。。（我如果说错了别喷。。说错了那就是我算法课白上了。）
heap是klogk 但是最 ...

啊 （kn-k)*klogk那里写错了。。应该就是kn*klogk。。

magicsets 发表于 2018-11-10 07:46
第一题我稍微写一下，用priority queue时间复杂度最优是没有问题的，但反馈中提到了speed / efficiency那就 ...

思考很不错, 但是别把面试想得太复杂, 45 分钟, 有1-2个follow up还有5分钟问问题, 没有这么多东西的, 面试官要是想问, 也会问你的, 考的是算法, 就只看算法的复杂度, 所以不用overthink

lllyyting 发表于 2018-11-10 15:47
我觉得你分析的也是错的。。（我如果说错了别喷。。说错了那就是我算法课白上了。）
heap是klogk 但是最 ...

你的算法课真的是白上了...
你额外用一个array 记录index, 请问你找到当前array里最小的element的操作复杂度是多少??不用heap用array, 那你是不是得遍历一下求当前最小值?? 这个复杂度就这样被你吃了?? 你能O(1)找到, 然后current index + 1 ??

留了两条言, 结果最基本的都不会, 还是要多努力啊, 这样是肯定要挂的

fangwei007 发表于 2018-11-13 02:24
你的算法课真的是白上了...
你额外用一个array 记录index, 请问你找到当前array里最小的element的操作 ...

兄弟，你认真看了吗？找最小值的runtime是O(k)。。哪里写O(1)了？知道每个array是sorted，最多kn个element，每次查找用O(k)，总共O(k * kn)... 不是什么比大小题都要用heap。。
麻烦你动动脑子提高一下理解能力吧，怕是觉得世界你最强了。
说话火药味挺重，挂点可能不只这一个算法这一块

lllyyting 发表于 2018-11-13 16:41
兄弟，你认真看了吗？找最小值的runtime是O(k)。。哪里写O(1)了？知道每个array是sorted，最多kn个elemen ...

请问 O(k *kn) 和O(logk *kn) 那个更优?

另外, 这个题做一下吧 https://www.lintcode.com/problem ... -arrays/description

我脾气可不好了, 应该是因为我打了面试官才挂的, 祝你成功! 2333

看了这个贴深刻感受到了地里有多少菜鸡喜欢装逼。
实话，被怼的这几位连最基本的分析都出错哪里来的自信。
大约CS这个行业确实太火爆了
顶楼主，祝早日拿到梦想的offer

fangwei007 发表于 2018-11-15 05:00
请问 O(k *kn) 和O(logk *kn) 那个更优?

另外, 这个题做一下吧 https://www.lintcode.com/problem/mer ...

楼主您好，我现在要昂赛亚麻information security下面的组叫consumer cloud security,能问问您当时面试官是谁吗，找不到准备回国了T T