Facebook 脸书 莫名其妙跪经

Job Hunting Interview
, , , , , ,
1

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)的空间复杂度蹦出来, 请看清楚题目. 另外, 其实面试官有说, 要实时维护一个排序好的输出.

2

第一题数据量大的话 比如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

3

BST K nearest neighbors也不是最优

4

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

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

5

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

6

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

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

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

7

第一题时间复杂度最优感觉是 O(k^2 * n)啊，进行kn次k个element中搜索最小值的操作，这一步时间复杂度O(k) 用for loop找出最小即可，不需要heap。。空间复杂度 O(k) 记录k个current index。。