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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 面试从来没有bug free 这一说。
|
e*******s 发帖数: 1979 | 4 感觉刚开始把题目问清楚就好了
是烙印么 感觉题目都没说清楚 0-9和不是0-9完全是不同的解法
【在 y***l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先上题: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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感觉刚开始把题目问清楚就好了 : 是烙印么 感觉题目都没说清楚 0-9和不是0-9完全是不同的解法
|
m******n 发帖数: 1691 | 6 is it one of leetcode problems?
【在 y***l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感觉像老美。不过说话嘟嘟囔囔的。他给了个例子数组只包含5/6个数,不过又说实际 : 中数组可能很大,当时就被误导到数的范围可能也很大。 : 我想解题过程在某种意义上应该要展现思维过程的由一般到特殊。我的思维过程就是先 : 想最直接的做法,然后不行就用空间换时间来优化,再然后考虑条件的特殊性。难道不 : 成一上来就给最优解?如果真这样,facebook的bar真可能达不到。
|
y***l 发帖数: 72 | 7 是个马甲。
【在 m******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : is it one of leetcode problems?
|
b***e 发帖数: 383 | 8 个人感觉lz答得很好啊,各种possible solution都答上来了。难道他认为你应该先问
清楚题目,了解data的分布情况,然后再答题?即便是这样,给据还是很难让人理解啊
。 |
e*******s 发帖数: 1979 | 9 是不是fresh grads 听说fb基本不招fresh了
【在 b***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 个人感觉lz答得很好啊,各种possible solution都答上来了。难道他认为你应该先问 : 清楚题目,了解data的分布情况,然后再答题?即便是这样,给据还是很难让人理解啊 : 。
|
y***l 发帖数: 72 | 10 工作三年了。
【在 e*******s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是不是fresh grads 听说fb基本不招fresh了
|
|
|
h*******0 发帖数: 270 | |
e*******s 发帖数: 1979 | 12 我也觉得至少这个应该是第一个提出来的方案
sort heap什么的其实都慢
【在 h*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是不是应该用quick select?
|
h*******0 发帖数: 270 | 13 然后如果对方说数有范围,然后再counting sort?
【在 e*******s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我也觉得至少这个应该是第一个提出来的方案 : sort heap什么的其实都慢
|
m******n 发帖数: 1691 | 14 the worst case for quick select is (n-k)*n
【在 e*******s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我也觉得至少这个应该是第一个提出来的方案 : sort heap什么的其实都慢
|
e*******s 发帖数: 1979 | 15 很有可能 counting sort应该是第二个 HashMap什么的其实还是慢
【在 h*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 然后如果对方说数有范围,然后再counting sort?
|
e*******s 发帖数: 1979 | 16 quick select worst case当然慢.
这么想quick sort quick select都不能叫算法了
【在 m******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : the worst case for quick select is (n-k)*n
|
h*******0 发帖数: 270 | 17 average 是 O(n)吧
【在 m******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : quick select worst case当然慢. : 这么想quick sort quick select都不能叫算法了
|
e*******s 发帖数: 1979 | 19 看来还是要先问数据分布
如果没要求 就自己把可能的都列出来
然后说什么样的数据有什么方法 应该就没漏洞了
【在 m******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : i am just thinking that might not be something in that interviewer's mind.
|
m******n 发帖数: 1691 | 20 sometimes communication skill counts.
【在 e*******s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 看来还是要先问数据分布 : 如果没要求 就自己把可能的都列出来 : 然后说什么样的数据有什么方法 应该就没漏洞了
|
|
|
h*******0 发帖数: 270 | 21 直接用introselect worse case 也是n
【在 m******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : sometimes communication skill counts.
|
y***l 发帖数: 72 | 22 我其实在heap后提了quick sort/select, 就是先随机取个数,然后根据这个数分区整
个数组,小的在一端,大的在另一端,这样就会不断去除一部分。可是面试官对这个也
不感兴趣,重复说如果k很大或者数组很大如何如何,感觉他可能根本没想过这种算法
,所以就move on了。
【在 m******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我其实在heap后提了quick sort/select, 就是先随机取个数,然后根据这个数分区整 : 个数组,小的在一端,大的在另一端,这样就会不断去除一部分。可是面试官对这个也 : 不感兴趣,重复说如果k很大或者数组很大如何如何,感觉他可能根本没想过这种算法 : ,所以就move on了。
|
e*******s 发帖数: 1979 | 24 嗯 面试官完全不明白也是有可能的 只能是运气不好了
select
【在 h*******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : quick select 如果k很大或者数组很大会有什么影响吗? 貌似最坏情况是pivot选择不 : 好的情况下吧。。 如果我理解的是正确的,那就是面试官压根就不明白quick select
|
l*********s 发帖数: 38 | 25 怎么感觉是被黑了。
难不成以后要把所有的可能的solutions全部列举出来,然后让面试官选择一个。
【在 y***l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先上题: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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先上题: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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先上题: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 我觉得楼主答的已经非常好非常到位了,可能就是纯粹刁难
加油,有更好的机会等着呢 |