FB onsite 面经

http://www.mitbbs.com/article_t/JobHunting/32849681.html

发信人: henry2568 (shuxiaofei), 信区: JobHunting
标  题: FB onsite 面经
发信站: BBS 未名空间站 (Mon Dec 15 12:37:27 2014, 美东)

跪了，上面经，估计是有一轮算法不smooth。本人fresh phd。anyway，反正要从别家
鸟。

都不难，欢迎大家讨论

第一轮：聊research，最后问了一题，
write a function f(x), so that f(x) returns true with x% probability。

第二轮：Given k sorted linked list, n elements in total, merge them into one
sorted linked list。
经典题吧，但是居然在复杂度上卡了一下，给出的 log(k)*n的recursion解法。follow
up是如果不允许用recursion如何达到log(k)*n。follow up也没答好，提示是可以用
heap。

中午吃饭

第三轮：convert a binary search tree into sorted double-linked list。
implement memcpy.

第四轮：System design。
Given a location (a coordinate), return top 100 nearest places.
Follow up, given a location, return top 100 events within x months in
nearest places。follow up 其实就是多加一个时间维度。

提出的方案就是对平面坐标系做grid，每个grid里的locations放到一台机器上。搜索
的时候就是针对input的location找到候选的grids(以某个半径画个圆)，再从中通过
map-reduce找到前100个location。

可以根据grid里location的密度或者访问量决定是不是要再做partition以提高
scalability。

follow up的话就是多加一个dimension代表时间。