Facebook 脸书 莫名其妙跪经

10月12号面的onsite, 题目因为太简单, 就挑两个稍微有点难度的说说:

1. LC 原题, merge K sorted arrays, 唯一就是告诉你数据量可能很大, 我用min-heap做的, heap里面存row的pointer或者row id + current position啥的struct都可以, priority queue; 论坛的朋友如果你有效率更高或者速度更快的, 请留下你的算法. (因为被告知是speed/efficiency挂了, 一脸苦笑, 这个理由也是够搞笑的, 我自己做的还真的心里清楚)

2. 求一个binary tree 里离一个给定node距离小于K的所有节点的集合, 这个也是简单到想笑, 主要就是创建一个hash table存下parent node, 然后用BFS就好了.

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

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

蹦出来, 请看清楚题目. 另外, 其实面试官有说, 要实时维护一个排序好的输出.

补充内容 (2019-8-27 03:20):
时隔一年了, 后面有跟Facebook的朋友followup, 确实是因为head count满了才没过; 不过所有的失败都是为成功积累经验, 今年拿了亚麻家30万的大包, 也算是没有辜负一年的时间. 再次祝愿所有朋友们都拿到心仪的offer

第一题我稍微写一下，用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

第一题数据量大的话 比如K很大这样复杂度为 k*n*log(k*n) k为list个数，n为长度
不如二分两两merge 时间复杂度 k/2 * 2 * n + k / 4 * 4 * n + ... + k * n = log(k) * k * n
correct me if i'm wrong

BST K nearest neighbors也不是最优
https://www.geeksforgeeks.org/print-nodes-distance-k-given-node-binary-tree/

????运气不好。。

lz又是你呀，貌似狗毕业运气不好

sshic 发表于 2018-11-2 01:03
lz又是你呀，貌似狗毕业运气不好

这两个月运气差到爆炸, 开了三年的车, lease到期的前一个月被淹了, 引擎全换, 花了1.5W, 艾玛, 所有事情全在这俩月

kxace 发表于 2018-11-2 01:33
BST K nearest neighbors也不是最优
https://www.geeksforgeeks.org/print-nodes-distance-k-given-node-b ...

首先, 面试官是个中国哥们, 面完很开心, 我俩中文聊天的时候给我讲了会给strong positive; 回到你的问题, 为啥不是最优?? DFS要考虑实际应用中会stack overflow.

kxace 发表于 2018-11-2 01:24
第一题数据量大的话 比如K很大这样复杂度为 k*n*log(k*n) k为list个数，n为长度
不如二分两两merge 时间复 ...

别的不说, 两两merge的空间复杂度恐怕你就过不去, 题目已经讲了很明确数据量会很大. 不然我直接一个set<int> 就搞定了, 还两两merge啥, O(n)解决

补充内容 (2018-11-2 01:43):
加上insertion的logn, nlogn, 但是空间复杂度是O(n); 这个是面试官明确说了空间复杂度不过

lz 多久之后得到feedback?

tl635 发表于 2018-11-2 01:52
lz 多久之后得到feedback?

时间我写错了, 是10月19号面的, 昨天给的消息, 11天左右吧