一亩三分地论坛

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

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

FB电面

[复制链接] |试试Instant~ |关注本帖
becky11 发表于 2014-11-11 06:32:57 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 博士 实习@Facebook - 内推 - 技术电面 |Other

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

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

x
发面经攒人品。。

印度哥好能扯,一上来先说了一通自己在干吗干吗,木有问我任何问题,然后开始做题
. visit 1point3acres.com for more.
1. 二进制字符串相加
   follow up: 换成八进制

2. 给一串会议开始结束时间 [(start, end), ...]
   看一个人是否能出席全部会议
   follow up: 给所有会议安排房间,要求最小化房间个数 (不用写代码)

最后那个贪心算法,蒙了一个按开始时间顺序安排,本来以为要好好讨论一下,给个证明什么的,这哥什么也不说,就问了一下复杂度就完了@@ .鐣欏璁哄潧-涓浜-涓夊垎鍦
我给的是O(n^2), 后来看了一下用Priority queue可以O(nlogn), 悲剧啊。。。

最后其实还有好多时间,他问我要不要写code, up to me, 那当然不写啦,然后就又听他扯淡。。哎哎
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
整个过程面试官完全不指导,也不要求我优化之类的,就光围观,请问一般都这样么??. more info on 1point3acres.com

评分

6

查看全部评分

leyhzm 发表于 2014-11-11 08:47:06 | 显示全部楼层
感谢楼主~请问lz,fb家的面试流程是咋样的?投完简历,recruiter直接联系电面嘛?然后on-site?有online assessment这种的嘛?
回复 支持 反对

使用道具 举报

pyemma 发表于 2014-11-11 08:51:52 | 显示全部楼层
第二道题的第一问:一个人能否出席所有的会议,是否就是寻找有两个会议overlap了?
第二问:按照开始时间排序后来贪心的求解是否可以?
回复 支持 反对

使用道具 举报

 楼主| becky11 发表于 2014-11-11 09:53:46 | 显示全部楼层
leyhzm 发表于 2014-11-11 08:47
感谢楼主~请问lz,fb家的面试流程是咋样的?投完简历,recruiter直接联系电面嘛?然后on-site?有online ass ...

我是面实习,找人内推了,直接电面的,应该不用on-site.
回复 支持 反对

使用道具 举报

 楼主| becky11 发表于 2014-11-11 09:55:20 | 显示全部楼层
pyemma 发表于 2014-11-11 08:51
第二道题的第一问:一个人能否出席所有的会议,是否就是寻找有两个会议overlap了?
第二问:按照开始时间 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
我觉得是。
那个是典型的一个贪心算法的例子,教材上一般都有吧,我当时没想出来,后来查了一下确实是按开始时间。不过面试官一直不置可否。。
回复 支持 反对

使用道具 举报

pyemma 发表于 2014-11-11 14:13:52 | 显示全部楼层
becky11 发表于 2014-11-10 17:55
我觉得是。
那个是典型的一个贪心算法的例子,教材上一般都有吧,我当时没想出来,后来查了一下确实是按 ...

恩,我和我基友讨论后觉得就是贪心没问题,还有FB一般都有一轮onsite的
回复 支持 反对

使用道具 举报

sweeney1130 发表于 2014-11-12 23:28:01 | 显示全部楼层
第二题应该是按照结束时间最早的排序贪心吧,不是由开始时间。比较经典的interval schedule问题
回复 支持 反对

使用道具 举报

mylogic 发表于 2014-11-13 00:08:03 | 显示全部楼层
我的理解:
第二题第一问 判断是否有overlap的会议。
第二题第二问按start 或者 end 时间从小到大排序, 从0 到n-1遍历一遍, 遇到start点,房间个数+1, 遇到end点 房间个数-1, 这个过程中房间个数的最大值就是需要的最少房间个数。
回复 支持 反对

使用道具 举报

csstudyup234 发表于 2015-2-2 12:10:22 | 显示全部楼层
mylogic 发表于 2014-11-13 00:08
我的理解:
第二题第一问 判断是否有overlap的会议。
第二题第二问按start 或者 end 时间从小到大排序,  ...

请问下时间复杂度分别是多少啊?
回复 支持 反对

使用道具 举报

csstudyup234 发表于 2015-2-2 12:10:48 | 显示全部楼层
mylogic 发表于 2014-11-13 00:08. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我的理解:
第二题第一问 判断是否有overlap的会议。
-google 1point3acres第二题第二问按start 或者 end 时间从小到大排序,  ...

请问下时间复杂度分别是多少啊?
回复 支持 反对

使用道具 举报

toeflibt 发表于 2015-2-2 16:52:43 | 显示全部楼层
csstudyup234 发表于 2015-2-2 12:10.鐣欏璁哄潧-涓浜-涓夊垎鍦
请问下时间复杂度分别是多少啊?

理解没错的话,就是nlogn
回复 支持 反对

使用道具 举报

z3581640 发表于 2015-2-11 23:38:35 | 显示全部楼层
请教一下楼主,是否第二题面试官有说 是完全重叠不能算参加,还是只要有overlap就不行, 例如 : [1, 3], [2, 4] 这种
回复 支持 反对

使用道具 举报

crazybadboy 发表于 2015-2-13 03:23:36 | 显示全部楼层
谢谢分享。第二题解法太巧妙。
回复 支持 反对

使用道具 举报

碇真嗣 发表于 2015-2-24 23:34:43 | 显示全部楼层
第二题另外一个不错的解法就是一开始将2n个时间点一起排序,对于相同的时间点结束的排在开始的前面,然后遍历一遍排序好的数组就可以解决了,每次都尽量用之前用过的房间,用一个queue保存用过的房间。。结束入queue,如果queue不为空出queue,queue如果是空的那就新取一个房间来坐。
回复 支持 反对

使用道具 举报

likenisha 发表于 2015-4-8 04:29:33 | 显示全部楼层
楼主知否过了呐
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 00:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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