FB onsite 面经# JobHunting - 待字闺中
h*8
1 楼
跪了，上面经，估计是有一轮算法不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代表时间。
鸟。
都不难，欢迎大家讨论
第一轮：聊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代表时间。
