一亩三分地论坛

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

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

fan tv (rovi) 蛋疼面试全过程

[复制链接] |试试Instant~ |关注本帖
calvinq 发表于 2015-5-24 08:26:46 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@fan tv - 内推 - Onsite 在线笔试 |Failfresh grad应届毕业生

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

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

x
其实就是面fan tv....hr聊完后给你一个oa....之后面试的各个环节都会跟这个oa紧紧相关....
oa 题目: 給你m个meeting(meeting id, start时间,end 时间,priority) 和n个rooms,要求你尽量多的将高priority 的meeting 安排到n个r里面。输入是m,n和好多个string,一个string包含meeting id, start时间,end 时间,priority。 返回安排进去了n个room里面的meeting 的id(按顺序)
时间理论上一个小时,但是可以跟hr 要求延长。
. Waral 鍗氬鏈夋洿澶氭枃绔,
lz oa 用了一个诡异的方法...然后test case都过了....然后就拿到on site...
第一轮: 讨论project.鐣欏璁哄潧-涓浜-涓夊垎鍦
第二轮: 讲一遍你oa的解题思路....然后那个美国小哥...说我这奇葩思路虽然把testcase 都过了...但是有个好大问题.就是m安排得不够紧密。例如说...m1 m2 m3 m4 安排在r1 和r2 里面,我将m1安排在 r1,  m2安排在 r2, m3 可以放在r1和r2,但是我的算法,会优先放在r1(遍历顺序的缘故)。 然后在安排m4的时候,可能r1 和 r2 都安排不进去了。 然后我的算法,就会抛弃m4,其实,我没有考虑一种情况是m3 移动到r2后,m4可以放在r1。
然后美国小哥就一直让我解决这个case......lz 比较挫..只想到了用recur dfs 来遍历....想不到好方法....
第三轮: 在上一轮的小哥强烈要求下..又继续解上面的case....一定要我想个好办法,不能用brute...妈蛋...
第四轮:本来要继续讨论刚刚那问题的....但是新来的小哥比较有主见...不让我继续解那题了....解了一个leetcode 原题...Unique Paths 然后没了
第五轮: 大manager来聊人生聊理想....

反正,这公司.估计就是看你oa那个题吧...弄出来了...估计offer就有了.....
lz比价挫..至今扔想不出好办法...求各路大神指导......

评分

5

查看全部评分

 楼主| calvinq 发表于 2015-5-26 05:11:41 | 显示全部楼层
readman 发表于 2015-5-24 12:53
stable sort 2次就可以了把.1point3acres缃
一次用优先级
然后用完成时间

想问问大神.具体什么意思?优先级sort 完了.然后呢?全部的开始时间sort一遍?
然后怎么排?
回复 支持 1 反对 0

使用道具 举报

readman 发表于 2015-5-24 12:53:01 | 显示全部楼层
stable sort 2次就可以了把. from: 1point3acres.com/bbs
一次用优先级
然后用完成时间
回复 支持 1 反对 0

使用道具 举报

slbsmglt 发表于 2015-5-24 09:50:49 | 显示全部楼层
不知道时间是离散的还是连续的,假设是连续的吧,复杂一些。

维护一个时间轴,记录有多少个meeting重叠在一个时间内,比如,1-2,1.5-4两个meeting,那么1-1.5,2-4重叠为1,1.5-2重叠为2。从高到低每次读入一个meeting,将其起止时间标注在时间轴上,起止时间内的重叠次数加1。直到某个时间段重叠为n+1,扔掉最后一个,保证重叠最多为n。
-google 1point3acres
从最开始的时间点,每次将这个时间段内存在的meeting安排到不同会议室内,依次向后类推,不会出现重叠。
.1point3acres缃
举例(用离散的举例更清楚):
m1 起止点1-4;m2 3-5; m3 2-4; m4 4-6; m5 5-6; m6: 1-3;m7: 1-4,优先级递减,放在3个room里的话,不能安排m7。
安排m1-m6,此时时间段1-2 2-3 3-4 4-5 5-6重叠为2 3 3 2 2(加m7的话2-4重叠为4,显然同时进行4meetings不能安排3room内):-google 1point3acres
1-2对应m1,6,放在r1 r2内;. Waral 鍗氬鏈夋洿澶氭枃绔,
2-3对应m136,m3放在r3;
3-4对应m123,m2->r2;
4-5对应m24, m4->r1 (多个可能的话随便选一个就好,放在index小的吧)
5-6对应m45,m5->r2。

m1-6安排完毕。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
如果没bug的话求大米。

补充内容 (2015-5-24 10:08):
要求会议时间是连续的,不能一个会议1点到2点,然后歇一个小时再从3点到4点(没那么变态吧)

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

mkcing 发表于 2015-5-24 10:31:51 | 显示全部楼层
slbsmglt 发表于 2015-5-24 09:50
不知道时间是离散的还是连续的,假设是连续的吧,复杂一些。
. visit 1point3acres.com for more.
维护一个时间轴,记录有多少个meeting重叠 ...

尽量多的将高priority 的meeting 安排到n个r里面

这句话,有点歧义,你觉得楼主意思是优先级高的一定要先排还是可以不排优先级高的,保证能排会议最多
回复 支持 反对

使用道具 举报

slbsmglt 发表于 2015-5-24 12:40:04 | 显示全部楼层
mkcing 发表于 2015-5-24 10:31
尽量多的将高priority 的meeting 安排到n个r里面

这句话,有点歧义,你觉得楼主意思是优先级高的一定 ...

哦,我的理解是前者
回复 支持 反对

使用道具 举报

 楼主| calvinq 发表于 2015-5-25 06:56:36 | 显示全部楼层
对的对的..就是大神理解这意思.... 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
回复 支持 反对

使用道具 举报

slbsmglt 发表于 2015-5-25 08:33:00 | 显示全部楼层
calvinq 发表于 2015-5-25 06:56
对的对的..就是大神理解这意思...

readman是对的,我做复杂了。
回复 支持 反对

使用道具 举报

jasusy 发表于 2015-8-2 02:44:30 | 显示全部楼层
readman 发表于 2015-5-23 20:53
stable sort 2次就可以了把.鐣欏璁哄潧-涓浜-涓夊垎鍦
一次用优先级. more info on 1point3acres.com
然后用完成时间

觉得有点问题啊,
比如:2 个room
id, start, end, priority
1,  0, 4,  100
2,  2, 5,  80
3,  3, 7,  80
4,  6, 10,  80. 鍥磋鎴戜滑@1point 3 acres
应该得到, 1, 2, 4 吧,如果用greedy, 会得到1, 3. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

回复 支持 反对

使用道具 举报

jasusy 发表于 2015-8-2 03:21:20 | 显示全部楼层
问一下楼主,题目是要求输出结果高priority后meeting数最多,还是高priority后meeting时间最长
回复 支持 反对

使用道具 举报

jasusy 发表于 2015-8-2 04:00:58 | 显示全部楼层
readman 发表于 2015-5-23 20:53
stable sort 2次就可以了把
一次用优先级
然后用完成时间

大神,对于你的算法,现在看懂了一点,要求的是最多meeting数量,我理解成最长meeting时间了。

但是有一个问题:
比如, 3 个room,meeting如下
priority 100: . visit 1point3acres.com for more.
----------
      ------------
      ------------
      ------------. from: 1point3acres.com/bbs
priority 90:. 1point 3acres 璁哄潧
----
----
----

这个例子,如果按照你所的greedy,会安排如2*90 + 3*100 5个meeting
-----------google 1point3acres
----  ------------
----  ------------
但是如如果把第一个100 priority的换成另一个,就能把剩下的90 priority 也安排景进去,相当于多了一个90 priority的meeting!!:
----  ------------
----  ------------
----  ------------
想不出来这个用什么方法解决。
能帮忙看一下吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 18:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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