一亩三分地论坛

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

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

FB电面,目测已跪

[复制链接] |试试Instant~ |关注本帖
ryuichist 发表于 2015-4-1 07:30:55 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 本科 全职@Facebook - 猎头 - 技术电面 |Fail在职跳槽

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

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

x
如题。第一题基本算是秒了,花了大概20分钟
第二题最后一点没做出来,卡了一个special case。目测已跪. From 1point 3acres bbs

第一题
question: write a function that detects conflicts in given meeting schedules
input: N intervals, [(s1, e1), (s2, e2), ..]
output: return True if there's any conflict, False otherwise

第二题
question: write a function that calculates the minimum number of rooms that can accommodate given meeting schedules
input: the same. 1point 3acres 璁哄潧
output: # of rooms. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

sanguine 发表于 2015-4-1 12:02:04 | 显示全部楼层
碰到面经题就是好啊%>_<%

第二题可以把所有的开始和结束时间放到一个list里面吧,开始时间正常放,结束时间放负数,然后绝对值排序(overide compareTo method),然后遍历一遍,遇到开始时间就+1,结束时间就-1,最后max就是结果
. 鍥磋鎴戜滑@1point 3 acres
或者你override compareTo,按照开始时间排序,然后另外一个list按照结束时间排序,然后两个list比较,也可以得出结果
回复 支持 5 反对 0

使用道具 举报

seabiscuit119 发表于 2015-4-1 07:33:41 | 显示全部楼层
最近好多次看到这道题啊
回复 支持 反对

使用道具 举报

 楼主| ryuichist 发表于 2015-4-1 07:38:16 | 显示全部楼层
http://collabedit.com/9gnaf
这里是code,有兴趣的同学可以看下
回复 支持 反对

使用道具 举报

 楼主| ryuichist 发表于 2015-4-1 07:38:31 | 显示全部楼层
seabiscuit119 发表于 2015-4-1 07:33
最近好多次看到这道题啊
. 1point 3acres 璁哄潧
第二题卡了一个special case,跪了估计
回复 支持 反对

使用道具 举报

seabiscuit119 发表于 2015-4-1 08:20:22 | 显示全部楼层
ryuichist 发表于 2015-4-1 07:38
第二题卡了一个special case,跪了估计

For the second problem, can we merge the intervals together and the calculate the number of the result list?
回复 支持 反对

使用道具 举报

 楼主| ryuichist 发表于 2015-4-1 08:21:23 | 显示全部楼层
seabiscuit119 发表于 2015-4-1 08:20. visit 1point3acres.com for more.
For the second problem, can we merge the intervals together and the calculate the number of the re ...

我觉得不能merge,因为是要根据conflict的次数,来决定需要的房间的数量,如果merge了,那么conflict就没了
回复 支持 反对

使用道具 举报

seabiscuit119 发表于 2015-4-1 08:38:37 | 显示全部楼层
ryuichist 发表于 2015-4-1 08:21. From 1point 3acres bbs
我觉得不能merge,因为是要根据conflict的次数,来决定需要的房间的数量,如果merge了,那么conflict就没 ...

Oh, this is wrong. Can we do like this.
First, we sort by the starttime of each interval, then we store all of the intervals as lists, then we go through the entire time and check at each time, how many intervals are overlapped. The biggest number of overlap through the entire time is the number of rooms.
回复 支持 反对

使用道具 举报

 楼主| ryuichist 发表于 2015-4-1 08:42:08 | 显示全部楼层
seabiscuit119 发表于 2015-4-1 08:38
Oh, this is wrong. Can we do like this.
First, we sort by the starttime of each interval, then we ...
. From 1point 3acres bbs
这样就错了,不能按照重复的最多的来
比如你有
(1,3) (2,7) (4, 10)
按照你的方法,需要3个房间,但实际上只需要2间
回复 支持 反对

使用道具 举报

seabiscuit119 发表于 2015-4-1 08:46:06 | 显示全部楼层
ryuichist 发表于 2015-4-1 08:42
这样就错了,不能按照重复的最多的来
比如你有
(1,3) (2,7) (4, 10)

For this situation, I think the biggest overlap is 2.. From 2-3, the overlap is 2, from 4-7, the overlap is 2. From1-2 and 7-10, the overlap is 1.  So the biggest overlap is 2..
回复 支持 反对

使用道具 举报

 楼主| ryuichist 发表于 2015-4-1 08:46:43 | 显示全部楼层
seabiscuit119 发表于 2015-4-1 08:46 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
For this situation, I think the biggest overlap is 2.. From 2-3, the overlap is 2, from 4-7, the o ...

biggest overlap,你觉得该怎么写?
回复 支持 反对

使用道具 举报

seabiscuit119 发表于 2015-4-1 08:51:23 | 显示全部楼层
ryuichist 发表于 2015-4-1 08:46. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
biggest overlap,你觉得该怎么写?

Suppose we have the whole starttime and the whole endtime. Use a whole variable 'count' to count the max number overlap.
For each one time in this period, I check all of the interval, whether the time i is in this interval. If yes, we can add one, and we can update the whole biggest overlap. I think the time complexity for this method is N^2. Let me think of a better solution for a while..

补充内容 (2015-4-1 09:28):
In the traverse of the whole time ,if we meet the start  we add the count by 1, if we meet the end of the interval, we decrease the count by 1. Then we can get the maximum of count, time Nlog(N)
回复 支持 反对

使用道具 举报

likenisha 发表于 2015-4-2 01:42:06 | 显示全部楼层
第二题就是第一题的follow up?
回复 支持 反对

使用道具 举报

碇真嗣 发表于 2015-4-2 01:44:14 | 显示全部楼层
LZ的题目和我的一模一样。。。。。。
回复 支持 反对

使用道具 举报

seabiscuit119 发表于 2015-4-2 01:46:45 | 显示全部楼层
碇真嗣 发表于 2015-4-2 01:44
LZ的题目和我的一模一样。。。。。。

when did you interview? I will have one on Friday..
回复 支持 反对

使用道具 举报

 楼主| ryuichist 发表于 2015-4-2 02:03:57 | 显示全部楼层
碇真嗣 发表于 2015-4-2 01:44
LZ的题目和我的一模一样。。。。。。

估计跪了,不过本来也没抱什么希望。FB要求实在太高了,只要卡住就挂
回复 支持 反对

使用道具 举报

碇真嗣 发表于 2015-4-2 02:18:55 | 显示全部楼层
ryuichist 发表于 2015-4-1 13:03
估计跪了,不过本来也没抱什么希望。FB要求实在太高了,只要卡住就挂
. 1point 3acres 璁哄潧
和面试官关系也比较大吧。。http://www.1point3acres.com/bbs/thread-127282-1-1.html 我的面经。。一模一样。。
回复 支持 反对

使用道具 举报

碇真嗣 发表于 2015-4-2 02:19:10 | 显示全部楼层
seabiscuit119 发表于 2015-4-1 12:46
when did you interview? I will have one on Friday..

last thursday
回复 支持 反对

使用道具 举报

 楼主| ryuichist 发表于 2015-4-2 02:36:43 | 显示全部楼层
likenisha 发表于 2015-4-2 01:42
第二题就是第一题的follow up?

对的!我follow up 卡主了
回复 支持 反对

使用道具 举报

seabiscuit119 发表于 2015-4-2 03:01:48 | 显示全部楼层

OH, yes, I find your blog.
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 01:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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