FB 面经 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

FB 面经

FB 面经# JobHunting - 待字闺中

l*i2014-04-08 07:04

1 楼

日本大地震发生快满 100天，灾后重建尚未全面开始，依然有逾 8万人在避难所生活。
经历生关死劫的夫妻，本来应该更加懂得珍惜眼前人，但事实上，灾区夫妻离婚案件是
急剧上升，最多的离婚理由，竟然是地震发生时，丈夫先夺门而逃，完全把妻子搁在脑
后。
东京专门接受离婚案商谈的机构「东京家族实验室」表示，地震发生后，打电话或登门
询问离婚手续的个案急升。妻子要求离婚的原因有各种各样，但最多是在大地震和海啸
发生时，丈夫没有拉妻子一起跑，反而自己先夺门逃跑，将妻儿搁在家里。「跟这样没
有责任心的男人继续生活在一起，是一大悲剧」，这是许多妻子的叹息。
要求离婚的另一大原因是，妻子发现地震和海啸发生时，丈夫的第一个电话不是打给自
己，而是打给他的母亲或情人。
「东京家族实验室」指出，有些灾区妻子在查看了丈夫的手机通话纪录后发现，地震发
生后，自己的丈夫打出的第一个电话不是给自己和孩子，而是给了一个陌生人，陌生人
大多是丈夫的秘密情人。患难见如此「真」情，真是可悲可泣。

r*i2014-04-08 07:04

2 楼

上周去facebook onsite，昨天收到hr电话告知没过，把题贴出来跟大家分享一下吧
电面
1.判断一个树是bst
2.给一个含有节点的数组，每个节点指向数组其他节点，或者数组外的节点，判断这个
数组中的节点所构成的树是tree
Onsite
1.介绍background，各种讨论
2.一个有序数组被rotate过，判断rotate的距离。考虑无重复和有重复
3.设计题。设计一个shorten url的service。讨论包括design，scale，各方各面
4.N个数中拿出K个数的组合并打印出来
5.二叉树的Deserializing
面完之后感觉很好，聊的也都很开心，题也不难，答的也很顺利，昨天接到电话还是有
点失望，要move on了。
各位也都加油！

d*i2014-04-08 07:04

3 楼

楼主能给个二叉树的Deserializing的代码吗？谢谢。

b*n2014-04-08 07:04

4 楼

Thanks for sharing this with us!

h*d2014-04-08 07:04

5 楼

leetcode reconstruct binary tree？

【在 d********i 的大作中提到】

: 楼主能给个二叉树的Deserializing的代码吗？谢谢。

v*y2014-04-08 07:04

6 楼

楼主不要灰心，继续加油！
另外楼主是在哪里on site的？加州还是西雅图？

n*e2014-04-08 07:04

7 楼

判断rotate 距离。。。可以重复的话
如果数组是[1,1,1,1,1,1]
输出是啥。。。

r*i2014-04-08 07:04

8 楼

我用递归做的，leetcode上有类似的吧

【在 d********i 的大作中提到】

: 楼主能给个二叉树的Deserializing的代码吗？谢谢。

r*i2014-04-08 07:04

9 楼

西雅图的

【在 v*****y 的大作中提到】

: 楼主不要灰心，继续加油！
: 另外楼主是在哪里on site的？加州还是西雅图？

r*i2014-04-08 07:04

10 楼

输出0就行了，当时跟面试官还讨论了一下

【在 n********e 的大作中提到】

: 判断rotate 距离。。。可以重复的话
: 如果数组是[1,1,1,1,1,1]
: 输出是啥。。。

l*o2014-04-08 07:04

11 楼

电面的第二题有什么好方法么？是不是和普通的isTree做法差不多，然后用一个
HashSet来验证连出去的某个node是不是在数组里，如果不在数组里直接忽略。

B*g2014-04-08 07:04

12 楼

thanks and bless

【在 r*****i 的大作中提到】

: 上周去facebook onsite，昨天收到hr电话告知没过，把题贴出来跟大家分享一下吧
: 电面
: 1.判断一个树是bst
: 2.给一个含有节点的数组，每个节点指向数组其他节点，或者数组外的节点，判断这个
: 数组中的节点所构成的树是tree
: Onsite
: 1.介绍background，各种讨论
: 2.一个有序数组被rotate过，判断rotate的距离。考虑无重复和有重复
: 3.设计题。设计一个shorten url的service。讨论包括design，scale，各方各面
: 4.N个数中拿出K个数的组合并打印出来

x*m2014-04-08 07:04

13 楼

感觉不难，是不是程序有bug

n*e2014-04-08 07:04

14 楼

多谢分享
lz 其他面试顺利

【在 r*****i 的大作中提到】

: 输出0就行了，当时跟面试官还讨论了一下

b*g2014-04-08 07:04

15 楼

"一个有序数组被rotate过，判断rotate的距离。考虑无重复和有重复"
无重复用binary search，有重复只能用linear的O(n)方法了吧？

t*72014-04-08 07:04

16 楼

mark

v*y2014-04-08 07:04

17 楼

你跟HR聊过了吗？她有没有告诉你哪个环节不太理想？

【在 r*****i 的大作中提到】

: 西雅图的

b*g2014-04-08 07:04

18 楼

//Find valley(rotation distance) in a rotated array with unique numbers
int findValley(vector num) {
if (num.empty()) return 0;
int lower = 0;
int upper = num.size()-1;
while (lower <= upper) {
if (upper-lower <= 1)
return num[lower] < num[upper] ? lower : upper;
int mid = lower+(upper-lower)/2;
if (num[mid-1] > num[mid] && num[mid] < num[mid+1])
return mid;
if (num[lower] < num[mid])
lower = mid+1;
else
upper = mid-1;
}
}
对[5,1,2,3,4],[4,5,1,2,3],[3,4,5,1,2],[2,3,4,5,1]work
如果rotate回原数组[1,2,3,4,5]就不work了。。。

m*f2014-04-08 07:04

19 楼

弱问lz的设计题怎么答的?

r*n2014-04-08 07:04

20 楼

楼主是按照inorder和preorder reconstruct的方式写的吗？我现在觉得这种方式比较
容易写的clean，assume 已经把tree load到数组里，不必要写文件IO的操作。
我之前按照leetcode网站的方式写的，serialize 按照inOrder写，遇到null就写#。
这样deserialize 可以写成：
public TreeNode btDeSerialization(String fileName) throws
FileNotFoundException {
Scanner s = new Scanner(new File(fileName)); //default delimiter is
white space
String token = s.next();
if(token.equals("#")) {
return null;
} else {
TreeNode root = new TreeNode(Integer.parseInt(token));
btDeSerializationHelper(root, true, s);
btDeSerializationHelper(root, false, s);
return root;
}
}
private void btDeSerializationHelper(TreeNode root, boolean left,
Scanner s) {
if(!s.hasNext()) {
return;
}
String token = s.next();
if(token.equals("#")) {
return;
}
TreeNode newNode = new TreeNode(Integer.parseInt(token));
if(left) {
root.left = newNode;
} else {
root.right = newNode;
}
btDeSerializationHelper(newNode, true, s);
btDeSerializationHelper(newNode, false, s);
}
不知道各位面试时是怎么操作的？

【在 r*****i 的大作中提到】

: 我用递归做的，leetcode上有类似的吧

X*42014-04-08 07:04

21 楼

这咋做呢

w*s2014-04-08 07:04

22 楼

判断bst，只需要中序遍历，判断当前的节点比之前访问的大。

【在 r*****i 的大作中提到】

f*n2014-04-08 07:04

23 楼

mark

w*s2014-04-08 07:04

24 楼

当然是0，O(n)复杂度
#include
int abs_diff(int a, int b)
{
if (a < b) return b - a;
return a - b;
}
int rotate_min_step(int k, int size)
{
int p = k + 1;
if (p < size - p) return p;
return size - p;
}
int rotation_distance(int* a, int size)
{
if (size == 1) return 0;
int max_diff = abs_diff(a[0], a[1]);
int max_pos = 0;
for (int i = 1; i < size; ++i)
{
int di = abs_diff(a[i], a[(i + 1) % size]);
if (di > max_diff)
{
max_diff = di;
max_pos = i;
}
else if (di == max_diff)
{
// equals
int s1 = rotate_min_step(max_pos, size);
int s2 = rotate_min_step(i, size);
if (s2 < s1)
{
max_diff = di;
max_pos = i;
}
}
}
return rotate_min_step(max_pos, size);
}
int main()
{
int a[] = {0,1,4,3,2};
std::cout << rotation_distance(a, sizeof(a) / sizeof(int));
return 0;
}

【在 n********e 的大作中提到】

: 判断rotate 距离。。。可以重复的话
: 如果数组是[1,1,1,1,1,1]
: 输出是啥。。。

w*s2014-04-08 07:04

25 楼

n取k，似乎很简单
#include
#include
#include
typedef std::vector > ResultVec;
ResultVec comb(int* array, int n, int k)
{
ResultVec v;
if (k == 1)
{
for (int i = 0; i < n; ++i)
{
std::vector e;
e.push_back(array[i]);
v.push_back(e);
}
return v;
}
for (int i = 0; i <= n - k; ++i)
{
int head = array[i];
ResultVec vec = comb(array + i + 1, n - i - 1, k - 1);
BOOST_FOREACH(std::vector e, vec)
{
e.push_back(head);
v.push_back(e);
}
}
return v;
}

【在 r*****i 的大作中提到】

x*z2014-04-08 07:04

26 楼

请问楼主面的是master new grad的职位么？不是说fb一般master new grad不会被问
system design的题么？

【在 r*****i 的大作中提到】

l*o2014-04-08 07:04

27 楼

Rotate的那题我是这样做的，大牛们帮忙看一下吧
public static int findRotatePos(int[] arr) {
int i=0, j=arr.length-1;
while (iif (i+1==j) {
if (arr[i]>arr[j]) return j;
else i++;
} else {
int mid = (i+j)/2;
if (arr[i]i=mid;
} else if (arr[i]>arr[mid]) {
j=mid;
} else { // ==
i++;
}
}
}
if (i==arr.length-1) return -1;
else return i+1;
}

f*r2014-04-08 07:04

28 楼

mark.

b*d2014-04-08 07:04

29 楼

mark