y***l
发帖数: 72 | 1 先上题：sum of k largest numbers in an unsorted array.
过程：
面试官迟到8分钟。先让我背景介绍，期间不断追问专业背景，研究经历，工作经历，
所以大概用了20分钟回答。然后interviewer说要面的第一题是：sum of k, 当时一听
就有点蒙，因为大约还剩15分钟的时间，难道要面2个题？就追问了一下，他说是。
解题过程：我先说了最自然的方法：sort和时间复杂度O(nlogn)，面试官不满意，说
array可能很大；然后我说了heap和O(nlogk), 面试官追问如何实现，解释了用最小堆
，比较top item。面试官还是不满意，说k可能很大。然后我说用binary search 和
partition, 交换k largest numbers到数组的一端，面试官还是不满意。看他给的
example中数只有几个数，就问他是否number有范围，他回答实际不一定，不过这题可
以假定[0-9]。然后我说直接用hash table，他这才满意。之后是写code。写完后给他
说自己要run test cases。检查过程中，他说函数主体pretty good，就是函数开始有
毛病。看了几遍，才发现判断输入参数为空时，把个“==”写成“！=”了，赶紧改了
过来。整个解题过程大概花了15分钟左右。
然后面试官说时间到了，要我问问题。问了facebook的午餐和他是否觉得facebook工作
excited。
然后，就没有然后了。两天后收到recruiter的拒信
对这次facebook的面试经历真是非常confusing。过来的同学能帮忙分析分析吗？被拒
是因为没做第二道题，还是那个typo导致了非bug-free? |
s**x
发帖数: 7506 | |
e*******s
发帖数: 1979 | 3 不是说fb是要这样的
【在 s**x 的大作中提到】
: 面试从来没有bug free 这一说。
|
e*******s
发帖数: 1979 | 4 感觉刚开始把题目问清楚就好了
是烙印么 感觉题目都没说清楚 0-9和不是0-9完全是不同的解法
【在 y***l 的大作中提到】
: 先上题：sum of k largest numbers in an unsorted array.
: 过程：
: 面试官迟到8分钟。先让我背景介绍，期间不断追问专业背景，研究经历，工作经历，
: 所以大概用了20分钟回答。然后interviewer说要面的第一题是：sum of k, 当时一听
: 就有点蒙，因为大约还剩15分钟的时间，难道要面2个题？就追问了一下，他说是。
: 解题过程：我先说了最自然的方法：sort和时间复杂度O(nlogn)，面试官不满意，说
: array可能很大；然后我说了heap和O(nlogk), 面试官追问如何实现，解释了用最小堆
: ，比较top item。面试官还是不满意，说k可能很大。然后我说用binary search 和
: partition, 交换k largest numbers到数组的一端，面试官还是不满意。看他给的
: example中数只有几个数，就问他是否number有范围，他回答实际不一定，不过这题可
|
y***l
发帖数: 72 | 5 感觉像老美。不过说话嘟嘟囔囔的。他给了个例子数组只包含5/6个数，不过又说实际
中数组可能很大，当时就被误导到数的范围可能也很大。
我想解题过程在某种意义上应该要展现思维过程的由一般到特殊。我的思维过程就是先
想最直接的做法，然后不行就用空间换时间来优化，再然后考虑条件的特殊性。难道不
成一上来就给最优解？如果真这样，facebook的bar真可能达不到。
【在 e*******s 的大作中提到】
: 感觉刚开始把题目问清楚就好了
: 是烙印么 感觉题目都没说清楚 0-9和不是0-9完全是不同的解法
|
m******n
发帖数: 1691 | 6 is it one of leetcode problems?
【在 y***l 的大作中提到】
: 感觉像老美。不过说话嘟嘟囔囔的。他给了个例子数组只包含5/6个数，不过又说实际
: 中数组可能很大，当时就被误导到数的范围可能也很大。
: 我想解题过程在某种意义上应该要展现思维过程的由一般到特殊。我的思维过程就是先
: 想最直接的做法，然后不行就用空间换时间来优化，再然后考虑条件的特殊性。难道不
: 成一上来就给最优解？如果真这样，facebook的bar真可能达不到。
|
y***l
发帖数: 72 | 7 是个马甲。
【在 m******n 的大作中提到】
: is it one of leetcode problems?
|
b***e
发帖数: 383 | 8 个人感觉lz答得很好啊，各种possible solution都答上来了。难道他认为你应该先问
清楚题目，了解data的分布情况，然后再答题？即便是这样，给据还是很难让人理解啊
。 |
e*******s
发帖数: 1979 | 9 是不是fresh grads 听说fb基本不招fresh了
【在 b***e 的大作中提到】
: 个人感觉lz答得很好啊，各种possible solution都答上来了。难道他认为你应该先问
: 清楚题目，了解data的分布情况，然后再答题？即便是这样，给据还是很难让人理解啊
: 。
|
y***l
发帖数: 72 | 10 工作三年了。
【在 e*******s 的大作中提到】
: 是不是fresh grads 听说fb基本不招fresh了
|
|
|
h*******0
发帖数: 270 | |
e*******s
发帖数: 1979 | 12 我也觉得至少这个应该是第一个提出来的方案
sort heap什么的其实都慢
【在 h*******0 的大作中提到】
: 是不是应该用quick select？
|
h*******0
发帖数: 270 | 13 然后如果对方说数有范围，然后再counting sort？
【在 e*******s 的大作中提到】
: 我也觉得至少这个应该是第一个提出来的方案
: sort heap什么的其实都慢
|
m******n
发帖数: 1691 | 14 the worst case for quick select is (n-k)*n
【在 e*******s 的大作中提到】
: 我也觉得至少这个应该是第一个提出来的方案
: sort heap什么的其实都慢
|
e*******s
发帖数: 1979 | 15 很有可能 counting sort应该是第二个 HashMap什么的其实还是慢
【在 h*******0 的大作中提到】
: 然后如果对方说数有范围，然后再counting sort？
|
e*******s
发帖数: 1979 | 16 quick select worst case当然慢.
这么想quick sort quick select都不能叫算法了
【在 m******n 的大作中提到】
: the worst case for quick select is (n-k)*n
|
h*******0
发帖数: 270 | 17 average 是 O（n）吧
【在 m******n 的大作中提到】
: the worst case for quick select is (n-k)*n
|
m******n
发帖数: 1691 | 18 i am just thinking that might not be something in that interviewer's mind.
【在 e*******s 的大作中提到】
: quick select worst case当然慢.
: 这么想quick sort quick select都不能叫算法了
|
e*******s
发帖数: 1979 | 19 看来还是要先问数据分布
如果没要求 就自己把可能的都列出来
然后说什么样的数据有什么方法 应该就没漏洞了
【在 m******n 的大作中提到】
: i am just thinking that might not be something in that interviewer's mind.
|
m******n
发帖数: 1691 | 20 sometimes communication skill counts.
【在 e*******s 的大作中提到】
: 看来还是要先问数据分布
: 如果没要求 就自己把可能的都列出来
: 然后说什么样的数据有什么方法 应该就没漏洞了
|
|
|
h*******0
发帖数: 270 | 21 直接用introselect worse case 也是n
【在 m******n 的大作中提到】
: sometimes communication skill counts.
|
y***l
发帖数: 72 | 22 我其实在heap后提了quick sort/select, 就是先随机取个数，然后根据这个数分区整
个数组，小的在一端，大的在另一端，这样就会不断去除一部分。可是面试官对这个也
不感兴趣，重复说如果k很大或者数组很大如何如何，感觉他可能根本没想过这种算法
，所以就move on了。
【在 m******n 的大作中提到】
: i am just thinking that might not be something in that interviewer's mind.
|
h*******0
发帖数: 270 | 23 quick select 如果k很大或者数组很大会有什么影响吗？ 貌似最坏情况是pivot选择不
好的情况下吧。。 如果我理解的是正确的，那就是面试官压根就不明白quick select
【在 y***l 的大作中提到】
: 我其实在heap后提了quick sort/select, 就是先随机取个数，然后根据这个数分区整
: 个数组，小的在一端，大的在另一端，这样就会不断去除一部分。可是面试官对这个也
: 不感兴趣，重复说如果k很大或者数组很大如何如何，感觉他可能根本没想过这种算法
: ，所以就move on了。
|
e*******s
发帖数: 1979 | 24 嗯 面试官完全不明白也是有可能的 只能是运气不好了
select
【在 h*******0 的大作中提到】
: quick select 如果k很大或者数组很大会有什么影响吗？ 貌似最坏情况是pivot选择不
: 好的情况下吧。。 如果我理解的是正确的，那就是面试官压根就不明白quick select
|
l*********s
发帖数: 38 | 25 怎么感觉是被黑了。
难不成以后要把所有的可能的solutions全部列举出来，然后让面试官选择一个。
【在 y***l 的大作中提到】
: 先上题：sum of k largest numbers in an unsorted array.
: 过程：
: 面试官迟到8分钟。先让我背景介绍，期间不断追问专业背景，研究经历，工作经历，
: 所以大概用了20分钟回答。然后interviewer说要面的第一题是：sum of k, 当时一听
: 就有点蒙，因为大约还剩15分钟的时间，难道要面2个题？就追问了一下，他说是。
: 解题过程：我先说了最自然的方法：sort和时间复杂度O(nlogn)，面试官不满意，说
: array可能很大；然后我说了heap和O(nlogk), 面试官追问如何实现，解释了用最小堆
: ，比较top item。面试官还是不满意，说k可能很大。然后我说用binary search 和
: partition, 交换k largest numbers到数组的一端，面试官还是不满意。看他给的
: example中数只有几个数，就问他是否number有范围，他回答实际不一定，不过这题可
|
W***o
发帖数: 6519 | 26 更好的机会在等你呢
【在 y***l 的大作中提到】
: 先上题：sum of k largest numbers in an unsorted array.
: 过程：
: 面试官迟到8分钟。先让我背景介绍，期间不断追问专业背景，研究经历，工作经历，
: 所以大概用了20分钟回答。然后interviewer说要面的第一题是：sum of k, 当时一听
: 就有点蒙，因为大约还剩15分钟的时间，难道要面2个题？就追问了一下，他说是。
: 解题过程：我先说了最自然的方法：sort和时间复杂度O(nlogn)，面试官不满意，说
: array可能很大；然后我说了heap和O(nlogk), 面试官追问如何实现，解释了用最小堆
: ，比较top item。面试官还是不满意，说k可能很大。然后我说用binary search 和
: partition, 交换k largest numbers到数组的一端，面试官还是不满意。看他给的
: example中数只有几个数，就问他是否number有范围，他回答实际不一定，不过这题可
|
m******e
发帖数: 242 | |
W***o
发帖数: 6519 | 28 不管k多大，quick select都是一样啊，这fb的面试官不懂或者故意刁难楼主的
select
【在 h*******0 的大作中提到】
: quick select 如果k很大或者数组很大会有什么影响吗？ 貌似最坏情况是pivot选择不
: 好的情况下吧。。 如果我理解的是正确的，那就是面试官压根就不明白quick select
|
d*******e
发帖数: 113 | |
w***9
发帖数: 14 | 30 感觉就是quick select的做法啊，average time是o(n)，难道不是吗？ |
|
|
G****A
发帖数: 4160 | 31 我遇到问一大堆背景问题，剩20分钟开始叫做题的大都压根没想要你
【在 y***l 的大作中提到】
: 先上题：sum of k largest numbers in an unsorted array.
: 过程：
: 面试官迟到8分钟。先让我背景介绍，期间不断追问专业背景，研究经历，工作经历，
: 所以大概用了20分钟回答。然后interviewer说要面的第一题是：sum of k, 当时一听
: 就有点蒙，因为大约还剩15分钟的时间，难道要面2个题？就追问了一下，他说是。
: 解题过程：我先说了最自然的方法：sort和时间复杂度O(nlogn)，面试官不满意，说
: array可能很大；然后我说了heap和O(nlogk), 面试官追问如何实现，解释了用最小堆
: ，比较top item。面试官还是不满意，说k可能很大。然后我说用binary search 和
: partition, 交换k largest numbers到数组的一端，面试官还是不满意。看他给的
: example中数只有几个数，就问他是否number有范围，他回答实际不一定，不过这题可
|
b**********5
发帖数: 7881 | 32 问了facebook的午餐...
what?!! |
c*****0
发帖数: 53 | |
c*****0
发帖数: 53 | |
p******o
发帖数: 147 | 35 我觉得楼主答的已经非常好非常到位了，可能就是纯粹刁难
加油，有更好的机会等着呢 |
