买房小白任秀坡在湾区买房经历(一)

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
[Google级团队]:实时大数据分析领域践行者
北京/深圳-大数据/搜索/机器学习职位
日志易机器大数据行业践行者Web/大数据/机器学习等职位-北京or深圳
把贵司招聘信息放这里
查看: 3242|回复: 19
收起左侧

Facebook 第二轮电面

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

2016(7-9月) 码农类 本科 实习@Facebook - 校园招聘会 - 技术电面  | Other | 其他

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

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

x
刚面完的facebook题目是find kth largest element in array的变形-google 1point3acres
给一个array of points (x, y coordinates)
然后给一个点origin. 鍥磋鎴戜滑@1point 3 acres
print k closest emelents to origin

follow up是如果array length很大 k很小

都是用heap做的 问了time 和 space complexity

小哥叫andrian 很有趣



评分

4

查看全部评分

本帖被以下淘专辑推荐:

BrilliantBean 发表于 2016-2-13 10:33:57 | 显示全部楼层
请问楼主为何有两轮电面啊
回复 支持 0 反对 1

使用道具 举报

Jester_Z 发表于 2016-2-18 05:52:59 | 显示全部楼层
beer 发表于 2016-2-18 05:33
Sorry. 好像我说错了。Quick Select的average expect time complexity 是 O(n).

哈哈 对 感觉quick select这道题应该是nk 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
n特别长的话 用heap查询可以klgn  但是建堆还是要o(n) 感觉还是慢=  =
回复 支持 1 反对 0

使用道具 举报

mclover 发表于 2016-3-3 13:10:39 | 显示全部楼层
max heap是nlogk+k, min heap是klogn+n, n大k小的时候用max heap比较好吧
回复 支持 1 反对 0

使用道具 举报

lyburke 发表于 2016-2-13 03:46:09 | 显示全部楼层
求问LZ第一题的思路是什么啊
回复 支持 反对

使用道具 举报

beer 发表于 2016-2-13 04:00:56 | 显示全部楼层
用heap的话,O(nlgn)
用quick select的话,O(KlgN)

如果K很小, N很大的话,用quick select比较好。如果N和K差不多的话,两种方法差不多。
回复 支持 反对

使用道具 举报

czbnlzd920706 发表于 2016-2-13 05:26:44 | 显示全部楼层
请问下,facebook 实习 on campus 如果跪了的话一年之内还可以申请他的全职吗?他给我发的邮件里这么说的,. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
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.
回复 支持 反对

使用道具 举报

eko910817 发表于 2016-2-18 04:24:26 | 显示全部楼层
beer 发表于 2016-2-12 12:00
用heap的话,O(nlgn)
用quick select的话,O(KlgN)
.1point3acres缃
用k大小的heap就可以了,所以heap应该是 O(nlgk)
回复 支持 反对

使用道具 举报

beer 发表于 2016-2-18 04:46:49 | 显示全部楼层
eko910817 发表于 2016-2-18 04:24
用k大小的heap就可以了,所以heap应该是 O(nlgk)

exactly.
回复 支持 反对

使用道具 举报

Jester_Z 发表于 2016-2-18 05:23:28 | 显示全部楼层

可以讲一下用quick select 的klgn的思路吗~
回复 支持 反对

使用道具 举报

beer 发表于 2016-2-18 05:33:52 | 显示全部楼层
Jester_Z 发表于 2016-2-18 05:23
可以讲一下用quick select 的klgn的思路吗~

Sorry. 好像我说错了。Quick Select的average expect time complexity 是 O(n).
  1. An important detail here is that there are indeed O(log n) different iterations here, but not all of them are doing an equal amount of work. Indeed, each iteration does half as much work as the previous iteration. If we ignore the fact that the work is decreasing, you can conclude that the work is O(n log n), which is correct but not a tight bound. This more precise analysis, which uses the fact that the work done keeps decreasing on each iteration, gives the O(n) runtime.
复制代码
回复 支持 反对

使用道具 举报

Howie 发表于 2016-2-18 06:10:36 | 显示全部楼层
这就是挂我的小哥。。
回复 支持 反对

使用道具 举报

 楼主| ape047 发表于 2016-2-24 03:48:45 | 显示全部楼层
BrilliantBean 发表于 2016-2-13 10:33.鐣欏璁哄潧-涓浜-涓夊垎鍦
请问楼主为何有两轮电面啊

第一轮不是电面 是学校career fair facebook来的 然后报名去面了 第二轮是skype
回复 支持 反对

使用道具 举报

 楼主| ape047 发表于 2016-2-24 03:49:26 | 显示全部楼层
Howie 发表于 2016-2-18 06:10
这就是挂我的小哥。。

他估计说我的code质量不行 于是我要面第三轮= =
回复 支持 反对

使用道具 举报

haling27188 发表于 2016-2-24 04:05:10 | 显示全部楼层
ape047 发表于 2016-2-24 03:49.鏈枃鍘熷垱鑷1point3acres璁哄潧
他估计说我的code质量不行 于是我要面第三轮= =

这。。。果然是FB啊, 我马上要面第一面。。。求人品,题好难
回复 支持 反对

使用道具 举报

haling27188 发表于 2016-2-24 05:32:49 | 显示全部楼层
这个就是算出每个point到origin的距离,然后把N个distance放到Ksize的heap,再比较(N-K)个值得大小,最后输出minheap中最大的Kth, 思路对么?
回复 支持 反对

使用道具 举报

 楼主| ape047 发表于 2016-2-24 05:38:44 | 显示全部楼层
haling27188 发表于 2016-2-24 05:32
这个就是算出每个point到origin的距离,然后把N个distance放到Ksize的heap,再比较(N-K)个值得大小,最后输 ...

我就是这么回答的
回复 支持 反对

使用道具 举报

Howie 发表于 2016-2-24 07:46:44 | 显示全部楼层
ape047 发表于 2016-2-24 03:49
他估计说我的code质量不行 于是我要面第三轮= =

恩 我感觉他要求挺高的。。。
回复 支持 反对

使用道具 举报

valleyvalley 发表于 2016-3-3 12:35:48 | 显示全部楼层
请问一般酱紫的题,用heap/priority queue, 是可以直接用api还是要自己写啊。。。
回复 支持 反对

使用道具 举报

sealove999 发表于 2016-4-19 05:35:56 | 显示全部楼层
mclover 发表于 2016-3-3 13:10
max heap是nlogk+k, min heap是klogn+n, n大k小的时候用max heap比较好吧
. Waral 鍗氬鏈夋洿澶氭枃绔,
不论n大还是n小,用quick select都是n,比heap快
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-388663-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-4-20 13:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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