w******a 发帖数: 236 | 1 本人在湾区一个IT大公司工作,3年软工经验。现在做的东西没啥意思,对将来的发展
没有什么帮助,所以想换工作。
我不是大牛,连小牛都算不上,所以就投一家试一家,不行再投下一个。FaceBook是我
投的第一家也是目前唯一的一家,三次on-site折腾了一个月,目前正在等final
decision。
热身前奏:
他家recruiter打电话来,聊了15分钟,然后就问能否on-site,吃个他家免费的
lunch顺带45分钟的preliminary coding interview。
第一轮:
那天如约前往,和recruiter共进午餐。recruiter人很nice,当时正是世界杯期间,
小小的餐厅里挤满了球迷,大呼小叫,好不热闹。FaceBook三餐免费,但是选择不多,
午餐大概两种main course可供挑选。然后是10分钟参观时间。感觉那里的工作环境就
是university里面的computer room,大家一个挨一个地坐着,每人面前一个大显示屏
,没有自己的cube或者工作电话,当然桌子底下的文件柜还是一人一个滴。大部分人看
着刚从校园出来的样子,很年轻。
之后是4 |
x***y 发帖数: 633 | 2 Can you elaborate the first question? thanks...
【在 w******a 的大作中提到】 : 本人在湾区一个IT大公司工作,3年软工经验。现在做的东西没啥意思,对将来的发展 : 没有什么帮助,所以想换工作。 : 我不是大牛,连小牛都算不上,所以就投一家试一家,不行再投下一个。FaceBook是我 : 投的第一家也是目前唯一的一家,三次on-site折腾了一个月,目前正在等final : decision。 : 热身前奏: : 他家recruiter打电话来,聊了15分钟,然后就问能否on-site,吃个他家免费的 : lunch顺带45分钟的preliminary coding interview。 : 第一轮: : 那天如约前往,和recruiter共进午餐。recruiter人很nice,当时正是世界杯期间,
|
w******a 发帖数: 236 | 3 第一个问题,具体说就是给定一个数组A:
A[0],A[1],A[2],...
和一个常数N。这个数组的元素有这个特性:
A[i]
问如何对该数组进行排序。
其实就是N-way归并算法的变体。 |
I**A 发帖数: 2345 | 4 i think it is the same as
merge N sorted array...
http://inder-gnu.blogspot.com/2008/01/merge-k-sorted-lists-of-size-n.html
i didn't look at its second solution carefully though..
welcome lz share code~~
【在 x***y 的大作中提到】 : Can you elaborate the first question? thanks...
|
I**A 发帖数: 2345 | 5 我觉得算法很简单
可是要写出CODE来好像很繁琐?
【在 w******a 的大作中提到】 : 第一个问题,具体说就是给定一个数组A: : A[0],A[1],A[2],... : 和一个常数N。这个数组的元素有这个特性: : A[i]: 问如何对该数组进行排序。 : 其实就是N-way归并算法的变体。
|
w******a 发帖数: 236 | 6 没错,code写起来就发现不是那么容易的,比2-way merge复杂不少。
我当时写得满头大汗,还是没写完。那个哥哥大概看我太可怜,然后说算了,我知道你
的思路就可以了。我是用C写的,主要是注意移动各个已经排好序的子数组的当前指针
,不要出错就好。
【在 I**A 的大作中提到】 : 我觉得算法很简单 : 可是要写出CODE来好像很繁琐?
|
I**A 发帖数: 2345 | 7 你用辅助数组了没?
【在 w******a 的大作中提到】 : 没错,code写起来就发现不是那么容易的,比2-way merge复杂不少。 : 我当时写得满头大汗,还是没写完。那个哥哥大概看我太可怜,然后说算了,我知道你 : 的思路就可以了。我是用C写的,主要是注意移动各个已经排好序的子数组的当前指针 : ,不要出错就好。
|
h**6 发帖数: 4160 | 8 用C是麻烦点,如果能用C++STL的话,用qriority_queue倒是很方便。 |
w******a 发帖数: 236 | 9 用了。当时和interviewer确认了,是可以用的。
【在 I**A 的大作中提到】 : 你用辅助数组了没?
|
w******a 发帖数: 236 | 10 这个还真不知道,我去学习一下。
【在 h**6 的大作中提到】 : 用C是麻烦点,如果能用C++STL的话,用qriority_queue倒是很方便。
|
|
|
a*******n 发帖数: 64 | 11 顺便问一个老题目
2GB的数组,要排序
通常解法就是先分成K个array
然后对每一个array在memory里做sort 时间复杂度(n/k)*lg(n/k)
最后一步是做K-way merge
这一步到底是在memory里做还是disk上啊?因为最后也还是需要o(n)空间啊
有人能解释下吗
【在 w******a 的大作中提到】 : 第一个问题,具体说就是给定一个数组A: : A[0],A[1],A[2],... : 和一个常数N。这个数组的元素有这个特性: : A[i]: 问如何对该数组进行排序。 : 其实就是N-way归并算法的变体。
|
I**A 发帖数: 2345 | 12 跟排序是一样的,
分批读入memory做merge,然后写出到disk上。。
http://en.wikipedia.org/wiki/External_sorting
【在 a*******n 的大作中提到】 : 顺便问一个老题目 : 2GB的数组,要排序 : 通常解法就是先分成K个array : 然后对每一个array在memory里做sort 时间复杂度(n/k)*lg(n/k) : 最后一步是做K-way merge : 这一步到底是在memory里做还是disk上啊?因为最后也还是需要o(n)空间啊 : 有人能解释下吗
|
c*********e 发帖数: 644 | 13 总看大家的面经 发现这些企业就是在招民工一样啊 真邪恶
【在 w******a 的大作中提到】 : 本人在湾区一个IT大公司工作,3年软工经验。现在做的东西没啥意思,对将来的发展 : 没有什么帮助,所以想换工作。 : 我不是大牛,连小牛都算不上,所以就投一家试一家,不行再投下一个。FaceBook是我 : 投的第一家也是目前唯一的一家,三次on-site折腾了一个月,目前正在等final : decision。 : 热身前奏: : 他家recruiter打电话来,聊了15分钟,然后就问能否on-site,吃个他家免费的 : lunch顺带45分钟的preliminary coding interview。 : 第一轮: : 那天如约前往,和recruiter共进午餐。recruiter人很nice,当时正是世界杯期间,
|
m*******i 发帖数: 8711 | 14 So? that's your value. what do you expect?
【在 c*********e 的大作中提到】 : 总看大家的面经 发现这些企业就是在招民工一样啊 真邪恶
|
n***d 发帖数: 8857 | 15 they are valued at 24B, if IPO
【在 c*********e 的大作中提到】 : 总看大家的面经 发现这些企业就是在招民工一样啊 真邪恶
|
t*******7 发帖数: 108 | 16 inplace or not?
【在 w******a 的大作中提到】 : 第一个问题,具体说就是给定一个数组A: : A[0],A[1],A[2],... : 和一个常数N。这个数组的元素有这个特性: : A[i]: 问如何对该数组进行排序。 : 其实就是N-way归并算法的变体。
|
c***m 发帖数: 56 | |
p********7 发帖数: 549 | |
p********7 发帖数: 549 | 19 楼主面的不是fresh的职位吧,看流程不像呢,题目也难些
【在 w******a 的大作中提到】 : 本人在湾区一个IT大公司工作,3年软工经验。现在做的东西没啥意思,对将来的发展 : 没有什么帮助,所以想换工作。 : 我不是大牛,连小牛都算不上,所以就投一家试一家,不行再投下一个。FaceBook是我 : 投的第一家也是目前唯一的一家,三次on-site折腾了一个月,目前正在等final : decision。 : 热身前奏: : 他家recruiter打电话来,聊了15分钟,然后就问能否on-site,吃个他家免费的 : lunch顺带45分钟的preliminary coding interview。 : 第一轮: : 那天如约前往,和recruiter共进午餐。recruiter人很nice,当时正是世界杯期间,
|
w******a 发帖数: 236 | 20 我原来在公司里做的是海量数据处理,所以本来投的是他们的data team。结果HR的人
说所有招进FaceBook的人一开始都没有对应的组,而是大家一起培训6个星期,然后自
己选组。
貌似不管有没有工作经验,都是这样连锅端。
发信人: paul198247 (S.Battier), 信区: JobHunting
标 题: Re: FaceBook面经--第一部分
发信站: BBS 未名空间站 (Wed Aug 4 21:51:05 2010, 美东)
楼主面的不是fresh的职位吧,看流程不像呢,题目也难些 |
|
|
p********7 发帖数: 549 | 21 N way 并归代码可真长,怎么可能当场写完.......N way N不是2的N次方,就复杂了
【在 w******a 的大作中提到】 : 我原来在公司里做的是海量数据处理,所以本来投的是他们的data team。结果HR的人 : 说所有招进FaceBook的人一开始都没有对应的组,而是大家一起培训6个星期,然后自 : 己选组。 : 貌似不管有没有工作经验,都是这样连锅端。 : 发信人: paul198247 (S.Battier), 信区: JobHunting : 标 题: Re: FaceBook面经--第一部分 : 发信站: BBS 未名空间站 (Wed Aug 4 21:51:05 2010, 美东) : 楼主面的不是fresh的职位吧,看流程不像呢,题目也难些
|
x******3 发帖数: 245 | |
p********7 发帖数: 549 | 23 应该不行,input[x] < input[x+3] 就用3 way
【在 x******3 的大作中提到】 : 2way 归并递归可以吗
|
c******n 发帖数: 4965 | 24 必需得用,否则每merge 一个cell, 你要挪n 个cell,
用2个extra N-cell array 就行了,
treat a subsequence by jumping every other K elements, so you have K
subarrays
for each of the K-"sub array"s
merge_sort(sub_array, tmp_buffer ---> tmp-buffer2 )
switch the 2 tmp_buffers
finally you have the result in tmp_buffer2
【在 w******a 的大作中提到】 : 用了。当时和interviewer确认了,是可以用的。
|
P********l 发帖数: 452 | 25 Obviously, the first one is shell-sort half way done.
http://en.wikipedia.org/wiki/Shell_sort
So, just continue the shell-sort until the last N=1.
【在 w******a 的大作中提到】 : 本人在湾区一个IT大公司工作,3年软工经验。现在做的东西没啥意思,对将来的发展 : 没有什么帮助,所以想换工作。 : 我不是大牛,连小牛都算不上,所以就投一家试一家,不行再投下一个。FaceBook是我 : 投的第一家也是目前唯一的一家,三次on-site折腾了一个月,目前正在等final : decision。 : 热身前奏: : 他家recruiter打电话来,聊了15分钟,然后就问能否on-site,吃个他家免费的 : lunch顺带45分钟的preliminary coding interview。 : 第一轮: : 那天如约前往,和recruiter共进午餐。recruiter人很nice,当时正是世界杯期间,
|
g*****e 发帖数: 282 | 26 我也想到shell sort了。但是shell sort的效率不如merge sort。不过shell sort的
code可是简单多了。fb不必求最优算法,差不多的算法加快点写出code才是王道?——
看板上讨论fb的感受。。。
【在 P********l 的大作中提到】 : Obviously, the first one is shell-sort half way done. : http://en.wikipedia.org/wiki/Shell_sort : So, just continue the shell-sort until the last N=1.
|