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

v*m2013-10-14 07:10

1 楼

就不怕媳妇也骂你们？你们在这里大骂婆婆

a*92013-10-14 07:10

2 楼

已挂
电面 1
国人大哥，应该有点放水
1) fabanacia，期待o(lgn)解法,但O(n)也行
2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
只知道worse case 是O(n^2)
onsite1
behavior: 1)有什么跟同事意见冲突的案例，怎么解决
2) 以前做过的项目如果现在再做会有什么不同/改进
3）divide and mod，但不能用/或者%，基本也是leetcode原题了
onsite2
system desgin: 因为我是kernel背景，让我用mutex,cv实现一个semephor，说先考虑
单核，然后拓展到多核，但我只写了单核的就没时间了，不知道多核的会有什么不同，
要求code compilable，MD三哥从一进来就没好脸色，此轮negative
onsite3:
1) 给你10g文件，1g内存，数总共有多少个不同的数，答案是用bit来记录数字，总共
4b个interger,最多用0.5gb来记录，follow up是如果只有400m怎么办，答案是把数字
hash一下或者说scan文件多次，每次取尾数bits不一样的数，不用code
2) read file up to 4K, 也是老题了
3) 求平方根，基本也是leetcode原题，但给的数是double，这样如果给的n是小于1的
数，初始的right就得取1而不是n
onsite4:
也是kernel组的三哥，先上来问了btree跟bst的区别，btree里放多少个index怎么决定
，答案是disk block size / 每个index的长度，如果是内存的话就用cache line size除
还有vm的，我也不大懂，好像是说如何解决内存的fagement问题，如何把多个分开的小
片段移到一起，用到了madvise这个syscall,还问为什么返回一个新的page之前要清零
，答案是因为page上可能是别的process的内容
code题是decode，比如说1 → 1, 2 -- > 01, 3 → 001, 4 → 0001,....，给你一个
无限的stream，要求输出数字，应该没啥难度，follow up是如何优化，我给的答案是
map，就是依次取char而不是bit，然后把char的值对应到string上，他说cpu还有一个
instruction可以直接查询此个char有多少个leading zero
最后祝我跟大家都能拿到满意的offer！

s*s2013-10-14 07:10

3 楼

问题是，现在不骂婆婆，将来媳妇就不骂自己了？

d*n2013-10-14 07:10

4 楼

谢谢共享。FB有kernel组？具体做什么的

A*k2013-10-14 07:10

5 楼

re

【在 s*****s 的大作中提到】

: 问题是，现在不骂婆婆，将来媳妇就不骂自己了？

a*92013-10-14 07:10

6 楼

有总共就4个，有个极品老印，千万要小心。。他们就是做optimaztion，比如面我那人
说的fagmental问题

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

: 谢谢共享。FB有kernel组？具体做什么的

l*t2013-10-14 07:10

7 楼

不得不承认有些婆婆就是该骂。

b*e2013-10-14 07:10

8 楼

什么是fabanacia？

k*b2013-10-14 07:10

9 楼

打算按照美国习惯办:
不期望儿子儿媳帮生孙子，也不帮他们作免费保姆，更不指望他们养老。
只作礼貌性短期拜访，吃饭可以出去吃，也可以AA制，家里住着不方便就住宾馆。
这样该相安无事吧。

k*t2013-10-14 07:10

10 楼

bless

k*12013-10-14 07:10

11 楼

我就是这么打算的。不过我不知道这是美国习惯。我希望他们不要想着来占
我的便宜，我也不会增加他们的负担，酱紫。

住宾馆。

【在 k******b 的大作中提到】

: 打算按照美国习惯办:
: 不期望儿子儿媳帮生孙子，也不帮他们作免费保姆，更不指望他们养老。
: 只作礼貌性短期拜访，吃饭可以出去吃，也可以AA制，家里住着不方便就住宾馆。
: 这样该相安无事吧。

k*t2013-10-14 07:10

12 楼

fibonacci吧

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

: 什么是fabanacia？

m*n2013-10-14 07:10

13 楼

我没骂过我婆婆阿
我儿子肯定找个跟我差不多的老婆
也不会骂我的

a*92013-10-14 07:10

14 楼

对，不好意思，英语比较烂

【在 k*******t 的大作中提到】

: fibonacci吧

h*12013-10-14 07:10

15 楼

不知道你说的骂是什么意思。最近很少看这里的坑。
反正我不怕做婆婆，因为我当过人媳妇，自己还有一个女儿，我更不会没有自知之明，
绝对不是传统的，自以为是的中国婆婆~！

s*u2013-10-14 07:10

16 楼

bless.lz拼写错误好多汗。。

c*b2013-10-14 07:10

17 楼

以德报怨,何以报德?

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

: 就不怕媳妇也骂你们？你们在这里大骂婆婆

b*e2013-10-14 07:10

18 楼

谢谢分享

c*e2013-10-14 07:10

19 楼

楼主的意思是：
左脸被人打了，要再把右脸给人打，这样以后就再也不会被打了。

【在 c**b 的大作中提到】

: 以德报怨,何以报德?

r*62013-10-14 07:10

20 楼

facebook的kernel组是干什么的

c*b2013-10-14 07:10

21 楼

那再把2个屁股蛋子也让人打.

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

: 楼主的意思是：
: 左脸被人打了，要再把右脸给人打，这样以后就再也不会被打了。

a*e2013-10-14 07:10

22 楼

菲波那契数列为啥都期待o(log n)解法呢。就是期待你做过这道题么？
我怎么觉得没见过的话，基本上没可能想出来呢。。。

【在 a********9 的大作中提到】

: 已挂
: 电面 1
: 国人大哥，应该有点放水
: 1) fabanacia，期待o(lgn)解法,但O(n)也行
: 2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
: 只知道worse case 是O(n^2)
: onsite1
: behavior: 1)有什么跟同事意见冲突的案例，怎么解决
: 2) 以前做过的项目如果现在再做会有什么不同/改进
: 3）divide and mod，但不能用/或者%，基本也是leetcode原题了

m*y2013-10-14 07:10

23 楼

我对婆婆很好，我婆婆到处夸我，在国内的时候。
我不怕做婆婆，做婆婆就是要不管不问，人家自己过自己的日子---

b*e2013-10-14 07:10

24 楼

Fibo 那题是analytic formula + optimized power function么？

c*b2013-10-14 07:10

25 楼

我见过一婆婆,狠不得把孙子当儿子养,把儿媳妇完全架空.

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

: 我对婆婆很好，我婆婆到处夸我，在国内的时候。
: 我不怕做婆婆，做婆婆就是要不管不问，人家自己过自己的日子---

k*a2013-10-14 07:10

26 楼

用矩阵

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

: Fibo 那题是analytic formula + optimized power function么？

V*82013-10-14 07:10

27 楼

以直报怨，以德报德

【在 c**b 的大作中提到】

: 以德报怨,何以报德?

s*u2013-10-14 07:10

28 楼

其实可以O（1），就是公式背不出来。
http://discuss.leetcode.com/questions/246/climbing-stairs

V*82013-10-14 07:10

29 楼

骂婆婆的要想一想，这么一个“老巫婆”能生养出让你们情有独钟，非君不嫁，心甘情
愿为他吃苦受累，生儿育女的男人，应该是你们的福气。

k*a2013-10-14 07:10

30 楼

可以现推导
不过 pow() 里幂是float 还是O(1)么...？

【在 s********u 的大作中提到】

: 其实可以O（1），就是公式背不出来。
: http://discuss.leetcode.com/questions/246/climbing-stairs

C*y2013-10-14 07:10

31 楼

谢谢分享，看来leetcode得使劲练啊

g*u2013-10-14 07:10

32 楼

公式是 log N

【在 s********u 的大作中提到】

: 其实可以O（1），就是公式背不出来。
: http://discuss.leetcode.com/questions/246/climbing-stairs

s*u2013-10-14 07:10

33 楼

多谢指正

【在 g**u 的大作中提到】

: 公式是 log N

a*92013-10-14 07:10

34 楼

我得到的教训反而是CS基本功以及自己那一块别落下了。。因为code题都很简单。。

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

: 谢谢分享，看来leetcode得使劲练啊

w*e2013-10-14 07:10

35 楼

"让我用mutex,cv实现一个semephor",
请问这个cv是啥意思？

r*e2013-10-14 07:10

36 楼

conditional variable

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

: "让我用mutex,cv实现一个semephor",
: 请问这个cv是啥意思？

a*92013-10-14 07:10

37 楼

conditional variable

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

: "让我用mutex,cv实现一个semephor",
: 请问这个cv是啥意思？

z*u2013-10-14 07:10

38 楼

第二题的时间复杂度不是n^2吧

【在 a********9 的大作中提到】

: 已挂
: 电面 1
: 国人大哥，应该有点放水
: 1) fabanacia，期待o(lgn)解法,但O(n)也行
: 2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
: 只知道worse case 是O(n^2)
: onsite1
: behavior: 1)有什么跟同事意见冲突的案例，怎么解决
: 2) 以前做过的项目如果现在再做会有什么不同/改进
: 3）divide and mod，但不能用/或者%，基本也是leetcode原题了

s*d2013-10-14 07:10

39 楼

cv= condition variable

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

: "让我用mutex,cv实现一个semephor",
: 请问这个cv是啥意思？

w*g2013-10-14 07:10

40 楼

一个O(logn)的解法
class Solution {
public:
int climbStairs(int n) {
// Start typing your Java solution below
// DO NOT write main() function
if(n==1){return 1;}
if(n==2){return 2;}
if(n==3){return 3;}
int low;
int high;
if(n%2==0){
low = n/2;
high = n/2;
}
else {
low = (n-1)/2;
high = (n+1)/2;
}
return climbStairs(low)*climbStairs(high)+climbStairs(low-1)*climbStairs
(high-1);
}
};

x*02013-10-14 07:10

41 楼

mark

t*72013-10-14 07:10

42 楼

mark

a*92013-10-14 07:10

43 楼

已挂
电面 1
国人大哥，应该有点放水
1) fabanacia，期待o(lgn)解法,但O(n)也行
2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
只知道worse case 是O(n^2)
onsite1
behavior: 1)有什么跟同事意见冲突的案例，怎么解决
2) 以前做过的项目如果现在再做会有什么不同/改进
3）divide and mod，但不能用/或者%，基本也是leetcode原题了
onsite2
system desgin: 因为我是kernel背景，让我用mutex,cv实现一个semephor，说先考虑
单核，然后拓展到多核，但我只写了单核的就没时间了，不知道多核的会有什么不同，
要求code compilable，MD三哥从一进来就没好脸色，此轮negative
onsite3:
1) 给你10g文件，1g内存，数总共有多少个不同的数，答案是用bit来记录数字，总共
4b个interger,最多用0.5gb来记录，follow up是如果只有400m怎么办，答案是把数字
hash一下或者说scan文件多次，每次取尾数bits不一样的数，不用code
2) read file up to 4K, 也是老题了
3) 求平方根，基本也是leetcode原题，但给的数是double，这样如果给的n是小于1的
数，初始的right就得取1而不是n
onsite4:
也是kernel组的三哥，先上来问了btree跟bst的区别，btree里放多少个index怎么决定
，答案是disk block size / 每个index的长度，如果是内存的话就用cache line size除
还有vm的，我也不大懂，好像是说如何解决内存的fagement问题，如何把多个分开的小
片段移到一起，用到了madvise这个syscall,还问为什么返回一个新的page之前要清零
，答案是因为page上可能是别的process的内容
code题是decode，比如说1 → 1, 2 -- > 01, 3 → 001, 4 → 0001,....，给你一个
无限的stream，要求输出数字，应该没啥难度，follow up是如何优化，我给的答案是
map，就是依次取char而不是bit，然后把char的值对应到string上，他说cpu还有一个
instruction可以直接查询此个char有多少个leading zero
最后祝我跟大家都能拿到满意的offer！

d*n2013-10-14 07:10

44 楼

谢谢共享。FB有kernel组？具体做什么的

a*92013-10-14 07:10

45 楼

有总共就4个，有个极品老印，千万要小心。。他们就是做optimaztion，比如面我那人
说的fagmental问题

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

: 谢谢共享。FB有kernel组？具体做什么的

b*e2013-10-14 07:10

46 楼

什么是fabanacia？

k*t2013-10-14 07:10

47 楼

bless

k*t2013-10-14 07:10

48 楼

fibonacci吧

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

: 什么是fabanacia？

a*92013-10-14 07:10

49 楼

对，不好意思，英语比较烂

【在 k*******t 的大作中提到】

: fibonacci吧

s*u2013-10-14 07:10

50 楼

bless.lz拼写错误好多汗。。

b*e2013-10-14 07:10

51 楼

谢谢分享

r*62013-10-14 07:10

52 楼

facebook的kernel组是干什么的

a*e2013-10-14 07:10

53 楼

菲波那契数列为啥都期待o(log n)解法呢。就是期待你做过这道题么？
我怎么觉得没见过的话，基本上没可能想出来呢。。。

【在 a********9 的大作中提到】

: 已挂
: 电面 1
: 国人大哥，应该有点放水
: 1) fabanacia，期待o(lgn)解法,但O(n)也行
: 2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
: 只知道worse case 是O(n^2)
: onsite1
: behavior: 1)有什么跟同事意见冲突的案例，怎么解决
: 2) 以前做过的项目如果现在再做会有什么不同/改进
: 3）divide and mod，但不能用/或者%，基本也是leetcode原题了

b*e2013-10-14 07:10

54 楼

Fibo 那题是analytic formula + optimized power function么？

k*a2013-10-14 07:10

55 楼

用矩阵

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

: Fibo 那题是analytic formula + optimized power function么？

s*u2013-10-14 07:10

56 楼

其实可以O（1），就是公式背不出来。
http://discuss.leetcode.com/questions/246/climbing-stairs

k*a2013-10-14 07:10

57 楼

可以现推导
不过 pow() 里幂是float 还是O(1)么...？

【在 s********u 的大作中提到】

: 其实可以O（1），就是公式背不出来。
: http://discuss.leetcode.com/questions/246/climbing-stairs

C*y2013-10-14 07:10

58 楼

谢谢分享，看来leetcode得使劲练啊

g*u2013-10-14 07:10

59 楼

公式是 log N

【在 s********u 的大作中提到】

: 其实可以O（1），就是公式背不出来。
: http://discuss.leetcode.com/questions/246/climbing-stairs

s*u2013-10-14 07:10

60 楼

多谢指正

【在 g**u 的大作中提到】

: 公式是 log N

a*92013-10-14 07:10

61 楼

我得到的教训反而是CS基本功以及自己那一块别落下了。。因为code题都很简单。。

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

: 谢谢分享，看来leetcode得使劲练啊

w*e2013-10-14 07:10

62 楼

"让我用mutex,cv实现一个semephor",
请问这个cv是啥意思？

r*e2013-10-14 07:10

63 楼

conditional variable

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

: "让我用mutex,cv实现一个semephor",
: 请问这个cv是啥意思？

a*92013-10-14 07:10

64 楼

conditional variable

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

: "让我用mutex,cv实现一个semephor",
: 请问这个cv是啥意思？

z*u2013-10-14 07:10

65 楼

第二题的时间复杂度不是n^2吧

【在 a********9 的大作中提到】

: 已挂
: 电面 1
: 国人大哥，应该有点放水
: 1) fabanacia，期待o(lgn)解法,但O(n)也行
: 2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
: 只知道worse case 是O(n^2)
: onsite1
: behavior: 1)有什么跟同事意见冲突的案例，怎么解决
: 2) 以前做过的项目如果现在再做会有什么不同/改进
: 3）divide and mod，但不能用/或者%，基本也是leetcode原题了

s*d2013-10-14 07:10

66 楼

cv= condition variable

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

: "让我用mutex,cv实现一个semephor",
: 请问这个cv是啥意思？

w*g2013-10-14 07:10

67 楼

一个O(logn)的解法
class Solution {
public:
int climbStairs(int n) {
// Start typing your Java solution below
// DO NOT write main() function
if(n==1){return 1;}
if(n==2){return 2;}
if(n==3){return 3;}
int low;
int high;
if(n%2==0){
low = n/2;
high = n/2;
}
else {
low = (n-1)/2;
high = (n+1)/2;
}
return climbStairs(low)*climbStairs(high)+climbStairs(low-1)*climbStairs
(high-1);
}
};

x*02013-10-14 07:10

68 楼

mark

t*72013-10-14 07:10

69 楼

mark

s*d2013-10-14 07:10

70 楼

"让我用mutex,cv实现一个semephor，说先考虑单核，然后拓展到多核。"
不太理解多核的意思？是说resource count可以大于1么？单核就是binary semaphore?
简单写一个POSIX的，请大家指正。
pthread_mutex_t mutex;
pthread_cond_t convar;
int count = N;//N is the number of threads allows to work at the same time
void sem_wait() {
pthread_mutex_lock(&mutex);
count--;
if (count < 0)//no resource, have to wait
pthread_cont_wait(&convar,&mutex);//mutex will be released when
waiting
pthread_mutex_unlock(&mutex);
}
void sem_post() {
pthread_mutex_lock(&mutex);
count++;
if (count <= 0)//someone's waiting...
pthread_cont_signal(&convar);
pthread_mutex_unlock(&mutex);
}

【在 a********9 的大作中提到】

: 已挂
: 电面 1
: 国人大哥，应该有点放水
: 1) fabanacia，期待o(lgn)解法,但O(n)也行
: 2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
: 只知道worse case 是O(n^2)
: onsite1
: behavior: 1)有什么跟同事意见冲突的案例，怎么解决
: 2) 以前做过的项目如果现在再做会有什么不同/改进
: 3）divide and mod，但不能用/或者%，基本也是leetcode原题了

o*c2013-10-14 07:10

71 楼

数学不好，求大神指导怎么推导这个递推式？

【在 w******g 的大作中提到】

: 一个O(logn)的解法
: class Solution {
: public:
: int climbStairs(int n) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if(n==1){return 1;}
: if(n==2){return 2;}
: if(n==3){return 3;}
: int low;

b*i2013-10-14 07:10

72 楼

你好，很感谢你的面经，想就此问几个问题：
1. generate all possible parentheses, 这题为什么时间是O(n^2)呢？你是用的类似
于DP的方法做的吗？我看九章和careercup只是一个dfs的方法，复杂度感觉是指数的。
2. onsite 3里面10G文件那题的follow up，不是很懂你的答案：follow up是如果只有
400m怎么办，答案是把数字
hash一下或者说scan文件多次，每次取尾数bits不一样的数，不用code
hash每次取尾数bits不一样的数以后，是再如何找出其中所有不同的数呢？再哈希一遍？
这题careercup150上面有，好像是分block来做的。
谢谢

【在 a********9 的大作中提到】

: 已挂
: 电面 1
: 国人大哥，应该有点放水
: 1) fabanacia，期待o(lgn)解法,但O(n)也行
: 2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
: 只知道worse case 是O(n^2)
: onsite1
: behavior: 1)有什么跟同事意见冲突的案例，怎么解决
: 2) 以前做过的项目如果现在再做会有什么不同/改进
: 3）divide and mod，但不能用/或者%，基本也是leetcode原题了

n*n2013-10-14 07:10

73 楼

N应该是输入长度吧。

【在 g**u 的大作中提到】

: 公式是 log N

s*d2013-10-14 07:10

74 楼

"让我用mutex,cv实现一个semephor，说先考虑单核，然后拓展到多核。"
不太理解多核的意思？是说resource count可以大于1么？单核就是binary semaphore?
简单写一个POSIX的，请大家指正。
pthread_mutex_t mutex;
pthread_cond_t convar;
int count = N;//N is the number of threads allows to work at the same time
void sem_wait() {
pthread_mutex_lock(&mutex);
count--;
if (count < 0)//no resource, have to wait
pthread_cont_wait(&convar,&mutex);//mutex will be released when
waiting
pthread_mutex_unlock(&mutex);
}
void sem_post() {
pthread_mutex_lock(&mutex);
count++;
if (count <= 0)//someone's waiting...
pthread_cont_signal(&convar);
pthread_mutex_unlock(&mutex);
}

【在 a********9 的大作中提到】

: 已挂
: 电面 1
: 国人大哥，应该有点放水
: 1) fabanacia，期待o(lgn)解法,但O(n)也行
: 2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
: 只知道worse case 是O(n^2)
: onsite1
: behavior: 1)有什么跟同事意见冲突的案例，怎么解决
: 2) 以前做过的项目如果现在再做会有什么不同/改进
: 3）divide and mod，但不能用/或者%，基本也是leetcode原题了

o*c2013-10-14 07:10

75 楼

数学不好，求大神指导怎么推导这个递推式？

【在 w******g 的大作中提到】

: 一个O(logn)的解法
: class Solution {
: public:
: int climbStairs(int n) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if(n==1){return 1;}
: if(n==2){return 2;}
: if(n==3){return 3;}
: int low;

b*i2013-10-14 07:10

76 楼

你好，很感谢你的面经，想就此问几个问题：
1. generate all possible parentheses, 这题为什么时间是O(n^2)呢？你是用的类似
于DP的方法做的吗？我看九章和careercup只是一个dfs的方法，复杂度感觉是指数的。
2. onsite 3里面10G文件那题的follow up，不是很懂你的答案：follow up是如果只有
400m怎么办，答案是把数字
hash一下或者说scan文件多次，每次取尾数bits不一样的数，不用code
hash每次取尾数bits不一样的数以后，是再如何找出其中所有不同的数呢？再哈希一遍？
这题careercup150上面有，好像是分block来做的。
谢谢

【在 a********9 的大作中提到】

: 已挂
: 电面 1
: 国人大哥，应该有点放水
: 1) fabanacia，期待o(lgn)解法,但O(n)也行
: 2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
: 只知道worse case 是O(n^2)
: onsite1
: behavior: 1)有什么跟同事意见冲突的案例，怎么解决
: 2) 以前做过的项目如果现在再做会有什么不同/改进
: 3）divide and mod，但不能用/或者%，基本也是leetcode原题了

n*n2013-10-14 07:10

77 楼

N应该是输入长度吧。

【在 g**u 的大作中提到】

: 公式是 log N

s*y2013-10-14 07:10

78 楼

Log(n)
http://www.geeksforgeeks.org/count-ways-reach-nth-stair/
http://www.geeksforgeeks.org/program-for-nth-fibonacci-number/