一亩三分地论坛

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

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

Rocket Fuel Online Test原题!

[复制链接] |试试Instant~ |关注本帖
yyboyz 发表于 2014-11-1 00:22:39 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 本科 全职@Rocket Fuel - 内推 - 在线笔试 |Other

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

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

x
回馈大家 ONLINE TEST 3小时, 做一个auto racer的题:

Input:
Id, startTime ,EndTime

Output:
Id, score

大意是让你设计一个算法来评价每个赛车手的成绩, 根据[size=14.3999996185303px]startTime[size=14.3999996185303px] 和[size=14.3999996185303px]EndTime。 算法里面有具体要求:
[size=14.3999996185303px]判断快的条件:A.startTime>B.startTime && [size=14.3999996185303px]A.endTime<B.endTime[size=14.3999996185303px]  
[size=14.3999996185303px]. 鍥磋鎴戜滑@1point 3 acres

[size=14.3999996185303px]这样A才算比B快
[size=14.3999996185303px]分数是越小越快
以上例子就是: A.score=0  B.score=1
score就是比该车手要快的人的个数


. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷我用的是二叉树, 但最后2个test cases还是timeout了

请问有做过的同学出来吼一声啊。。
说说你们有拿到ONSITE吗? 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
谢谢了

评分

2

查看全部评分

1guangnian 发表于 2014-11-1 04:40:05 | 显示全部楼层
就是问你一个区间能被多少个区间完整覆盖吧。。。。可不可以这样离线做,把线段按左端点排序,然后对于一个线段[l,r],之前的线段左端点都是小于l的,去query比它的右端点r大的有多少,就是query [r+1, +oo]这个区间有多少个数,最后把它的右端点r的个数+1,这些query和update可以logn时间完成
回复 支持 反对

使用道具 举报

qiaokan 发表于 2014-11-1 04:49:15 | 显示全部楼层
1guangnian 发表于 2014-11-1 04:40
就是问你一个区间能被多少个区间完整覆盖吧。。。。可不可以这样离线做,把线段按左端点排序,然后对于一个 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
恩。基本没问题。
回复 支持 反对

使用道具 举报

xx8833 发表于 2014-11-1 07:30:14 | 显示全部楼层
题目中不是提示用bucket做吗,按照start time分bucket,可以跑过所有test,3小时还是比充裕的。
回复 支持 反对

使用道具 举报

 楼主| yyboyz 发表于 2014-11-1 07:35:12 来自手机 | 显示全部楼层
xx8833 发表于 2014-11-1 07:30
题目中不是提示用bucket做吗,按照start time分bucket,可以跑过所有test,3小时还是比充裕的。

我没太明白用bucket怎么记录结束时间比目前记录要晚的数目
回复 支持 反对

使用道具 举报

xx8833 发表于 2014-11-1 07:43:51 | 显示全部楼层
yyboyz 发表于 2014-11-1 07:35
我没太明白用bucket怎么记录结束时间比目前记录要晚的数目

bucket中按照end时间排序,就能二分搜索了。如果bucket大小选为sqrt(n),复杂度是n * (sqrt(n) + sqrt(n)*log(sort(n)))。对于每个racer,有一个bucket需要枚举(start time正好在那个bucket范围中),其他bucket都是二分。
回复 支持 反对

使用道具 举报

 楼主| yyboyz 发表于 2014-11-1 08:07:47 来自手机 | 显示全部楼层
那你怎么算出结束时间小于某个值的个数?
回复 支持 反对

使用道具 举报

pro 发表于 2014-11-13 00:50:42 | 显示全部楼层
我今天也做了这个……最后用线段树把大数据量的test case都搞过去了……但最后test case2一直过不去不知道怎么回事
回复 支持 反对

使用道具 举报

BlueElephant 发表于 2014-11-13 01:39:03 | 显示全部楼层
没过最后两个大case正常的,因为95%时间都在I/O上,不是程序问题
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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