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

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

5

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

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

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

6

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

7

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

8

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

9

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

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

10

lz 多久之后得到feedback?

11

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