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.
|
