facebook过经

电面:

  1. 二叉搜索树的一些操作

  2. 压缩一个稀疏矩阵

onsite

  1. 设计一个搜索系统。主要focus在反向索引在磁盘上的存储,FST等提高查询效率的技术,sharding策略,多个filter如何handle等等

  2. 给一个链表,把它分成若干的sublist并反转。应该是leetcode上比较早的原题,印象里好像刷过。

  3. 设计facebook post的实时comment系统,用户可以看到其它人在typing,并且实时弹出新的comment。这一题一开始想当然的使用push model,后来发现pull model应该更合理。

  4. 给一个二叉搜索书的前序遍历,输出其中序遍历。

  5. 聊了了之前的经验,然后做了一个题,判断一句话(不考虑标点符号和空格)是不是回文。

fb给的level不满意,然后公司感觉前景一般,wlb还很差,最后给的package还可以,但是还是pass了。

补充
对第一题有疑惑的,可以直接去网上搜搜lucene底层的实现原理

BST 给定前序,输出中序,如果不要求重构 BST 的话,直接输出从小到大的排序结果就可以了吧?

时间复杂度要求线性的