一亩三分地论坛

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

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

Facebook 第二轮电面

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

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

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

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

x
刚面完的facebook题目是find kth largest element in array的变形
给一个array of points (x, y coordinates)
然后给一个点origin
print k closest emelents to origin

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

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

小哥叫andrian 很有趣


. from: 1point3acres.com/bbs

评分

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)

用k大小的heap就可以了,所以heap应该是 O(nlgk)
回复 支持 反对

使用道具 举报

beer 发表于 2016-2-18 04:46:49 | 显示全部楼层
eko910817 发表于 2016-2-18 04:24
.1point3acres缃用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. 鍥磋鎴戜滑@1point 3 acres
可以讲一下用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. visit 1point3acres.com for more.
他估计说我的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比较好吧

不论n大还是n小,用quick select都是n,比heap快
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 06:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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