一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2225|回复: 17
收起左侧

Facebook on campus interview 跪经

[复制链接] |试试Instant~ |关注本帖
enirinth 发表于 2016-2-12 13:43:11 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 实习@Facebook - 校园招聘会 - 校园招聘会 |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
第一次发面经贴...轻喷...
学校career fair上投的简历,收到面试已经感觉thank god了...
面试官最开始是facebook的,后来跳槽oculus,然后oculus又被facebook收购了.....目前他在facebook西雅图office, 之前pre interview social的时候他说过实习生最好还是去menlo park. 1point3acres.com/bbs

1.流程:
自我介绍+most interesting project + what feature do you want to add to facebook + 白板做题 + 问问题
2.题目:
collection of objects,只能两两判断大小。只有“大”和“小”, 没有”等“。 然后也没有transitivity,也就是A > B && B > C 不能推出A > C。 类似石头剪刀布。
要求找出max, max的定义是比起他所有都大。

他的问题是纯口述,interface还有object类我都自己写,他说他觉得reasonable就好。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
先写了时间O(n^2) 空间O(n)的, 然后优化成空间O(1)
最后优化成了时间O(n)空间O(n). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
他说时间不是O(n), 但马上又改口说是
最后我说想优化空间,他说不用了,问了半天问题。主要就是问他们用的那些framework什么的。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
然后我回去想了一下我优化之后确实不是O(n) ,感觉小哥自己没想清楚就改口了...
. more info on 1point3acres.com
3.结果:
在我前一天面的同学周四下午已经收到了onsite,我觉得过的email肯定是一起发的,我现在周四晚还没消息,所以目测跪了....

4.注:.1point3acres缃
不懂题目意思的可以问我,题目解法就不要在本帖底下讨论了....毕竟跪经,伤心回忆....


补充内容 (2016-2-12 13:47):
过的同学面试官是国人小哥,考的是first bad version

补充内容 (2016-2-13 16:12):
半夜突然收到邮件说过了给了onsite.....求rp.....

评分

1

查看全部评分

本帖被以下淘专辑推荐:

yucheyang2 发表于 2016-2-13 11:39:56 | 显示全部楼层
类似于MergeSort?两个HashMap,胜利的进入胜者组,败的进入败者组,然后胜者组再出来做比较?这样N,空间N,为什么N,假设8个Object,第一轮比4次,胜者组4个,然后这4个比两次,胜者组2个,然后比较1次,最后复杂度4+2+1 = 7,所以是N的,应该是N/2 + N/4 + N/8 + ....这样加起来N。
回复 支持 1 反对 0

使用道具 举报

duduhaha 发表于 2016-2-12 14:37:46 | 显示全部楼层
pat pat. 这题类似 quick select 吧?  随机选一个object, 比它小的去左边, 比它大的去右边, 然后递归从右边开始。
average time O(n). worst case time O(n *n ).
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-2-12 15:03:49 | 显示全部楼层
我也觉得quick select可以 但是最后筛选出来的值不一定是解 要最后过一遍所有值验证。另外开始的时候可以随机shuffle 一下 保证o(n) time no extra memory needed
回复 支持 反对

使用道具 举报

lyburke 发表于 2016-2-13 03:44:46 | 显示全部楼层
这道题感觉以前面经出现过。。。LZ难道是因为复杂度分析错然后被挂了吗?感觉要求好高啊
回复 支持 反对

使用道具 举报

czbnlzd920706 发表于 2016-2-13 05:26:20 | 显示全部楼层
请问下,facebook 实习 on campus 如果跪了的话一年之内还可以申请他的全职吗?他给我发的邮件里这么说的,. more info on 1point3acres.com
If it doesn't go great, I will reach out to you and let you know. If this occurs, you can apply for any of our positions again on or after a year from your interview date.
回复 支持 反对

使用道具 举报

 楼主| enirinth 发表于 2016-2-13 09:13:26 | 显示全部楼层
czbnlzd920706 发表于 2016-2-13 05:26
请问下,facebook 实习 on campus 如果跪了的话一年之内还可以申请他的全职吗?他给我发的邮件里这么说的, ...

据我了解他家全职和intern是共用冷冻期的....
回复 支持 反对

使用道具 举报

singku 发表于 2016-2-13 11:09:20 | 显示全部楼层
注意没有transitivity. quick select 选出来的左右两边 是右边的大于pivot pivot大于左边的 然后默认右边的大于左边的 这个是有transitivity的
回复 支持 反对

使用道具 举报

 楼主| enirinth 发表于 2016-2-13 16:17:24 | 显示全部楼层
yucheyang2 发表于 2016-2-13 11:39.鏈枃鍘熷垱鑷1point3acres璁哄潧
类似于MergeSort?两个HashMap,胜利的进入胜者组,败的进入败者组,然后胜者组再出来做比较?这样N,空间N ...
. from: 1point3acres.com/bbs
感觉你想出来的方法是对的且是最快的。两两比较必定淘汰一个,所以每次子问题必定缩小一半。胜者组的只能算“可能最大”,所以胜者组的最后一个还要和其他所有比较一遍,不过也是O(N)啦。
(如果胜者组剩一个之前就全被淘汰了,那就没有最大。类似于石头剪刀布。). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
多谢你的解法!
回复 支持 反对

使用道具 举报

woshixuyoudan 发表于 2016-2-14 01:49:10 | 显示全部楼层
不知道是不是我理解错题目了.... 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
从第一个开始和下一个比较,选出大的那个,继续跟下一个比较,一直到最后,得到的那个值应该就是吧。然后再用这个值遍历一遍,看看是不是大于所有的,如果是的话就输出,不是的话就是不存在。
回复 支持 反对

使用道具 举报

Morphy 发表于 2016-2-14 02:13:18 | 显示全部楼层
感觉像是lc原题,https://leetcode.com/problems/find-the-celebrity/
区别只是knows变成了compare。
和楼上差不多解法。从开头一直记录到最后,得到一个记录的”可能解“,然后再遍历一遍这个”可能解“是否满足比所有的都大。.鏈枃鍘熷垱鑷1point3acres璁哄潧
假设默认可能解为1,从2...N进行比较,如果在比到i的时候输了,可能解就记录为i。(因为1...i-1中每个数都存在比它大的数,因此不用考虑)。然后走完一遍数组就得到一个唯一的可能解。(解最多只可能有一个)然后再走一遍数组进行检验。
O(n)时间,O(1)空间。
回复 支持 反对

使用道具 举报

frank11118 发表于 2016-2-14 02:47:42 | 显示全部楼层
on campus in UMich?
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-2-14 09:21:59 | 显示全部楼层
我开始也觉得像 find celebrity 仔细想想不行。
回复 支持 反对

使用道具 举报

czbnlzd920706 发表于 2016-2-14 10:44:10 | 显示全部楼层
singku 发表于 2016-2-13 11:09
注意没有transitivity. quick select 选出来的左右两边 是右边的大于pivot pivot大于左边的 然后默认右边的 ...

左边的那一组元素,一定小于某个元素,所以他们不可能是max element。可能性只有在右边的那一组元素。所以并没有使用 transitivity. 最后选出来的元素,遍历一遍所有数组。在最后确认下所选出来的这个max是不是max。
回复 支持 反对

使用道具 举报

tmaconfire 发表于 2016-2-18 07:25:16 | 显示全部楼层
kinggarden2001 发表于 2016-2-14 09:21
我开始也觉得像 find celebrity 仔细想想不行。

这个max就相当于celebrity啊,有什么例子让你觉得不行的呢?
回复 支持 反对

使用道具 举报

tk1322715 发表于 2016-2-19 07:59:54 | 显示全部楼层
首先弄一个hash table,key是元素比如"A",value是比A小的元素的个数。 然后扫一遍输入,统计下就好了。举个例子:
input A>B, B>C, C>D, A>D, A>B, A>C
扫了一遍之后hash table的存储如下:
A:4
B:1
C:1 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
D:0
然后再遍历一下hash table发现A对应的value就是4,所以返回A既可
回复 支持 反对

使用道具 举报

yourdoraemon 发表于 2016-9-25 04:56:17 | 显示全部楼层
用个queue就能搞定吧, 每次pop两个比较,留下大的,最后剩一个。如果解是唯一的,那就存在, 如果不唯一,还需要再遍历一遍,确保没有object比剩下的大???O(N)的空间和时间。。。
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-9-28 10:51:35 | 显示全部楼层
Morphy 发表于 2016-2-14 02:13
感觉像是lc原题,https://leetcode.com/problems/find-the-celebrity/
区别只是knows变成了compare。
和 ...

两两比较,取胜的那个和第三个比较,然后再取胜的和第四个比较,最后得到最后一个,最后一个是唯一一个有可能成为MAX的,因为其他的都比输过,然后拿最后一个重新再和所有的比一遍,如果全部都赢那么最后一个是最大,不然就没有最大值
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 09:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表