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就好了.

  3. system design, recruiter不给别的feedback, 但是明说system design是positive, 所以也没啥好说的, 题目是设计一个service, 供用户查询任何时间段内的数据信息(之前面过类似的, 查询股票信息系统啥的), 难点在于aggregator知不知道, 怎么数据库sharding, cache怎么用, 怎么做分布式, 还有就是要分析和算QPS, 怎么优化存储, retention的处理等等.

还有两轮的题目, 因为实在太简单了, 我都没啥印象了, 就是LC上easy差不多的题.

面完本以为安心等offer, 结果收到邮件被拒, 还不死心给recruitor打了电话, 结果是不透露具体信息, 然后请来年再面. 感觉挺莫名其妙和有点生气的, 因为所有题目基本都是秒杀, 然后面试官时间充分到给我每轮出2-3个题, 还有5-10分钟聊天. 没有任何卡壳或者说hint啥的. system design也是positive, 完全想不通哪里能挂我. 今年果然脸不行 😔.

希望大家有好运拿到心仪的offer

匿了

补充内容 (2018-11-2 01:54):
对不起, 时间写错了, 是10/19面的

补充内容 (2018-11-2 02:19):
别被那个叫 kxace 的人给误导了, 他的复杂度分析是错的, 别因为他面试给弄错了

补充内容 (2018-11-2 22:18):
很多朋友可能没搞清楚题意, 第一题是lintcode上的题目, 是sorted arrays不是linkedlists, 不是链表题, 竟然有O(1)的空间复杂度蹦出来, 请看清楚题目. 另外, 其实面试官有说, 要实时维护一个排序好的输出.

第一题数据量大的话 比如K很大这样复杂度为 knlog(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也不是最优

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

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

第一题我稍微写一下,用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可以编译:

比如说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++中有多线程实现的代码:

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

以及C++标准库中parallel部分作者讨论并行多路归并排序(Parallel Multiway Mergesort)的ppt,从第11页开始:

楼主,如果是k个array,每个Array长度为n
那么总共需要sort的元素数目为kn
那么用heap sort 时间复杂度应该是k
n * log(k*n)吧? (参照heap sort average performance O(nlogn))
空间复杂度,用queue的话是o(k)
您觉得呢?

补充内容 (2018-11-7 09:52):
而且,用heap sort 每个元素都要进heap一次,出heap一次,感觉 时间复杂度应该是kn * log(kn)。

手机上补充不了,应该还有个就是可以并行进行merge sort

空间复杂度是priority queue好,不算最后结束占的n,只用k,merge sort需要额外n。如果把最后结果算的空间算上,就是priority queue需要额外k。

时间复杂度啥priority queue是每个数字都要经历一次logk,merge sort 的话并不算每个数字都要logk。理论上有个巨长无比的数组最后合并,只需要n时间。

很久不做算法题了,可能这儿说的不对。但是,逻辑上就是外排序最后用merge sort是有原因的。

我服你的敢说, 张口闭口 discuss里面有, 自己没背下来强行秀一波吗???

???运气不好。。

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

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

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

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

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

lz 多久之后得到feedback?

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