F家onsite面经# JobHunting - 待字闺中
f*r
1 楼
四轮，其中一轮是research:
第一轮：design，设计fb的newsfeed结构，如何储存数据，如何实现给每个用户显示不
同的内容，如何对newsfeed做ranking，如何训练ranking的model，基本上是讨论的形
式，以及讨论各种方式的优缺点。
第二轮：coding，应该都比较typical：（1）给n个2维的点，找出其中离原点最近的k
个。followup：如果n很大，如何做mapreduce；further followup：reduce的时候应该
怎么做最有效？（2）给n个positive int，计算他们两两之间hamming distance的和\
sum_{i
；further follow up: 给一棵树，计算每两个节点之间的距离的和，距离定义为path
的长度。
回答：
（1）max heap（最开始说成了min heap，后来改了），复杂度O(nlogk)。mapreduce就
是每个mapper找k个最近的然后merge。reduce的时候可以用binary tree的结构reduce
，所以如果有m个chunk，就是O(logm)个reducer。
（2）从低到高计算每一个bit位，每一个bit位只需要计算有多少个1和多少个0即可。
复杂度是O(nm)，m是最大数字的bit位数。第二个问题直接看前几个n的例子可以推算。
第三个问题我给了O(n^2)：计算两两距离，然后取和；要了hint以后给了O(n)：就是
tree的每条边上的flow的总和。
第三轮：research，面试官是mit phd，很tough。问了一个leetcode上的word ladder
，要求编程。解法不难，就是bfs search，不过我忘了c++下面hashset的interface，
面试官貌似不太高兴。
第四轮：继续coding。(1) 有一溜n个房子，每个房子里面的东西的value是给定的一个
正整数，小偷准备去偷东西来maximize gain，但是有一个条件是不能偷连续两幢房子
的东西，因为房主挨偷以后会告诉左右邻居。要求给出能偷到的最大value的值。
followup：怎么样给出具体偷的方案？(2) leetcode Search in Rotated Sorted
Array
回答：（1）dynamic programming，O(n) time complexity，最开始给了O(n) space
complexity, 然后improve到O(1)。写了code，followup解释了用back pointer，然后
面试官说不用再写这个了。(2) 基本上就是各种ifthen，然后面试官问了一些特殊情况
下怎么speed up，基本上就是再加两个ifthen，最后两人都晕了，“this is right
right?”“Yeah I think it is right”，结束。
第一轮：design，设计fb的newsfeed结构，如何储存数据，如何实现给每个用户显示不
同的内容，如何对newsfeed做ranking，如何训练ranking的model，基本上是讨论的形
式，以及讨论各种方式的优缺点。
第二轮：coding，应该都比较typical：（1）给n个2维的点，找出其中离原点最近的k
个。followup：如果n很大，如何做mapreduce；further followup：reduce的时候应该
怎么做最有效？（2）给n个positive int，计算他们两两之间hamming distance的和\
sum_{i
；further follow up: 给一棵树，计算每两个节点之间的距离的和，距离定义为path
的长度。
回答：
（1）max heap（最开始说成了min heap，后来改了），复杂度O(nlogk)。mapreduce就
是每个mapper找k个最近的然后merge。reduce的时候可以用binary tree的结构reduce
，所以如果有m个chunk，就是O(logm)个reducer。
（2）从低到高计算每一个bit位，每一个bit位只需要计算有多少个1和多少个0即可。
复杂度是O(nm)，m是最大数字的bit位数。第二个问题直接看前几个n的例子可以推算。
第三个问题我给了O(n^2)：计算两两距离，然后取和；要了hint以后给了O(n)：就是
tree的每条边上的flow的总和。
第三轮：research，面试官是mit phd，很tough。问了一个leetcode上的word ladder
，要求编程。解法不难，就是bfs search，不过我忘了c++下面hashset的interface，
面试官貌似不太高兴。
第四轮：继续coding。(1) 有一溜n个房子，每个房子里面的东西的value是给定的一个
正整数，小偷准备去偷东西来maximize gain，但是有一个条件是不能偷连续两幢房子
的东西，因为房主挨偷以后会告诉左右邻居。要求给出能偷到的最大value的值。
followup：怎么样给出具体偷的方案？(2) leetcode Search in Rotated Sorted
Array
回答：（1）dynamic programming，O(n) time complexity，最开始给了O(n) space
complexity, 然后improve到O(1)。写了code，followup解释了用back pointer，然后
面试官说不用再写这个了。(2) 基本上就是各种ifthen，然后面试官问了一些特殊情况
下怎么speed up，基本上就是再加两个ifthen，最后两人都晕了，“this is right
right?”“Yeah I think it is right”，结束。
