由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - rocket fuel/online test/auto racer解法
相关主题
Rocket Fuel今天Skpye面经问个array in place operation的题目
一道rocket f 电面题问个算法题, 关于区间 overlap的
求intersect的圆,求O(nlogn)的方法问一道题(5)
programming pearl看不懂这个题一道大公司诡异的complete binary tree max sum of 2 nodes 题
an old problem on algorithmg公司面试问Longest increasing subsequence,意义在哪里?
程序员的思维太牛逼了 (转载)关于最长递增子序列的问题。
大家来讨论一下这个求长方形面积的问题吧请问两道题
再贴这道算法题,寻答案,有包子送问一道G家经典老题
相关话题的讨论汇总
话题: start话题: end话题: racer话题: idx话题: time
进入JobHunting版参与讨论
1 (共1页)
p*u
发帖数: 136
1
分享一个得到positive feedback的解题思路,代码就不贴了,因为邮件里面说rocket
fuel的engineer会code review
题目网上有,这个链接里面的第3题:http://get-that-job-at-google.blogspot.jp/2013/02/rocketfuel-codesprint-at-iit-bombay.html
首先题目里面给了一个提示:把所有的输入,按照start time均分为K个区间去处理
我的思路用sample input解释一下:
5
2 100 200
3 110 190
4 105 145
1 90 150
5 102 198
1,所有的开始时间和结束时间没有重复的,对输入得到三元组 start|end>,然后根据time排序得到:
idx time r_id type value/ret
--------------------------------------------
0 90 1 start 0 +1
1 100 2 start 0 +1
2 102 5 start 0 +1
3 105 4 start 0 +1
4 110 3 start 0 +1
5 145 4 end 0 *0
6 150 1 end 0 *1
7 190 3 end 0 *0
8 198 5 end 0 *2
9 200 2 end 0 *3
上图中+1表示value, *x表示ret
2,对排好序的数组从前往后扫描:
2.1 当碰到标记为start的item时,记录racer_id对应的idx是多少:
比如{"1":"0", "2":"1", "5":"3", "4":"3", "3":"4"}
2.2 当碰到标记为end的item时,比如racer_id=4这一行,当前end_idx=5,做2件事
情:
找到racer_id=4对应start time的start_idx=3
2.2.1 value[start_idx]++,也就是value[3]++
2.2.2 对[start_idx + 1, end_idx]这个区间的value求和,就是racer_id=4的
最终结果,ret=0
上面图中以列为时间轴,大致把过程模拟了一遍
3,对所有的结果按照题目要求排序即可
=====分割线:以上是本题的解法,以下是本题用到的数据结构=====
抽象以上过程,有个数组,不断的修改其中某个位置的值,不断要求某个区间的和。典
型的数据结构是线段树:http://en.wikipedia.org/wiki/Segment_tree 线段树比较好写,本质上就是个二叉树。
最后这个解法的整体时间复杂度是O(nlogn)的,写起来也比较容易,比hint的解法要上
流一点。
下周安排了skype interview,求rp!
s*****n
发帖数: 994
2
这为什么是nlogn?
当中区间求和是n^2。
example:
sort完以后是
start_n
...
start_2
start_1
end_1
end_2
...
end_n
这样求和一共要n(n-1)/2次操作

rocket

【在 p*u 的大作中提到】
: 分享一个得到positive feedback的解题思路,代码就不贴了,因为邮件里面说rocket
: fuel的engineer会code review
: 题目网上有,这个链接里面的第3题:http://get-that-job-at-google.blogspot.jp/2013/02/rocketfuel-codesprint-at-iit-bombay.html
: 首先题目里面给了一个提示:把所有的输入,按照start time均分为K个区间去处理
: 我的思路用sample input解释一下:
: 5
: 2 100 200
: 3 110 190
: 4 105 145
: 1 90 150

e*******8
发帖数: 94
3
其实就是inversion counting的马甲...
c********p
发帖数: 1969
4
mark
x*****0
发帖数: 452
5
m
f*******w
发帖数: 1243
6
Mark
貌似用BIT比segment tree更方便啊
p*u
发帖数: 136
7
分享一个得到positive feedback的解题思路,代码就不贴了,因为邮件里面说rocket
fuel的engineer会code review
题目网上有,这个链接里面的第3题:http://get-that-job-at-google.blogspot.jp/2013/02/rocketfuel-codesprint-at-iit-bombay.html
首先题目里面给了一个提示:把所有的输入,按照start time均分为K个区间去处理
我的思路用sample input解释一下:
5
2 100 200
3 110 190
4 105 145
1 90 150
5 102 198
1,所有的开始时间和结束时间没有重复的,对输入得到三元组 start|end>,然后根据time排序得到:
idx time r_id type value/ret
--------------------------------------------
0 90 1 start 0 +1
1 100 2 start 0 +1
2 102 5 start 0 +1
3 105 4 start 0 +1
4 110 3 start 0 +1
5 145 4 end 0 *0
6 150 1 end 0 *1
7 190 3 end 0 *0
8 198 5 end 0 *2
9 200 2 end 0 *3
上图中+1表示value, *x表示ret
2,对排好序的数组从前往后扫描:
2.1 当碰到标记为start的item时,记录racer_id对应的idx是多少:
比如{"1":"0", "2":"1", "5":"3", "4":"3", "3":"4"}
2.2 当碰到标记为end的item时,比如racer_id=4这一行,当前end_idx=5,做2件事
情:
找到racer_id=4对应start time的start_idx=3
2.2.1 value[start_idx]++,也就是value[3]++
2.2.2 对[start_idx + 1, end_idx]这个区间的value求和,就是racer_id=4的
最终结果,ret=0
上面图中以列为时间轴,大致把过程模拟了一遍
3,对所有的结果按照题目要求排序即可
=====分割线:以上是本题的解法,以下是本题用到的数据结构=====
抽象以上过程,有个数组,不断的修改其中某个位置的值,不断要求某个区间的和。典
型的数据结构是线段树:http://en.wikipedia.org/wiki/Segment_tree 线段树比较好写,本质上就是个二叉树。
最后这个解法的整体时间复杂度是O(nlogn)的,写起来也比较容易,比hint的解法要上
流一点。
下周安排了skype interview,求rp!
s*****n
发帖数: 994
8
这为什么是nlogn?
当中区间求和是n^2。
example:
sort完以后是
start_n
...
start_2
start_1
end_1
end_2
...
end_n
这样求和一共要n(n-1)/2次操作

rocket

【在 p*u 的大作中提到】
: 分享一个得到positive feedback的解题思路,代码就不贴了,因为邮件里面说rocket
: fuel的engineer会code review
: 题目网上有,这个链接里面的第3题:http://get-that-job-at-google.blogspot.jp/2013/02/rocketfuel-codesprint-at-iit-bombay.html
: 首先题目里面给了一个提示:把所有的输入,按照start time均分为K个区间去处理
: 我的思路用sample input解释一下:
: 5
: 2 100 200
: 3 110 190
: 4 105 145
: 1 90 150

e*******8
发帖数: 94
9
其实就是inversion counting的马甲...
c********p
发帖数: 1969
10
mark
相关主题
程序员的思维太牛逼了 (转载)问个array in place operation的题目
大家来讨论一下这个求长方形面积的问题吧问个算法题, 关于区间 overlap的
再贴这道算法题,寻答案,有包子送问一道题(5)
进入JobHunting版参与讨论
x*****0
发帖数: 452
11
m
G*********e
发帖数: 56
12
如果说对区间测长度有一个先验的估计, 这个算法是n log n
的。
j*****d
发帖数: 1625
13
居然还有人往这坑里面跳。我老佩服了
G*********e
发帖数: 56
14
如果说对区间测长度有一个先验的估计, 这个算法是n log n
的。
j*****d
发帖数: 1625
15
居然还有人往这坑里面跳。我老佩服了
c***t
发帖数: 50
16
mark
d****n
发帖数: 233
17
You can also check here:
http://codeanytime.blogspot.com/2013/05/score-of-racers.html

【在 c***t 的大作中提到】
: mark
v*******2
发帖数: 18
18
收到rocket fuel的online test,叫word game 俩小时,借楼求问有谁做过没?题意是
啥,多谢多谢!
j*******n
发帖数: 10
19
这个题目用merge sort, 先按照start time sort , 然后按照 end time merge sort
, 类似inverse count
复杂度 nlogn
能通过所有test,代码简洁

rocket

【在 p*u 的大作中提到】
: 分享一个得到positive feedback的解题思路,代码就不贴了,因为邮件里面说rocket
: fuel的engineer会code review
: 题目网上有,这个链接里面的第3题:http://get-that-job-at-google.blogspot.jp/2013/02/rocketfuel-codesprint-at-iit-bombay.html
: 首先题目里面给了一个提示:把所有的输入,按照start time均分为K个区间去处理
: 我的思路用sample input解释一下:
: 5
: 2 100 200
: 3 110 190
: 4 105 145
: 1 90 150

e*********5
发帖数: 137
20
merge的时间是 O(n),但是似乎update score的复杂度是不是 O(n^2)?比如 考虑
data (start, end) (1, 16), (2,15), (3,14), (4,13), (5,12), (6,11), (7,10), (
8,9)
下面是两段的end time.第一段的start time小于第二段的start time
13 14 15 16 | 9 10 11 12
merge: end time 13>9,所以跟13, 14, 15 16对应的score都+1。跟9对应的racer
score不变。 不过比较的话至多就是O(n).
这样如果按update score算复杂度,最差可达到 O(n^2).
还是说是另外一种思路?

sort

【在 j*******n 的大作中提到】
: 这个题目用merge sort, 先按照start time sort , 然后按照 end time merge sort
: , 类似inverse count
: 复杂度 nlogn
: 能通过所有test,代码简洁
:
: rocket

相关主题
一道大公司诡异的complete binary tree max sum of 2 nodes 题请问两道题
g公司面试问Longest increasing subsequence,意义在哪里?问一道G家经典老题
关于最长递增子序列的问题。求 Maximum Subarray divide and conquer 解法
进入JobHunting版参与讨论
C********e
发帖数: 492
21
你这个解法是O(n^2)的,虽然可以通过所有的test,但是不符合题目的要求。

sort

【在 j*******n 的大作中提到】
: 这个题目用merge sort, 先按照start time sort , 然后按照 end time merge sort
: , 类似inverse count
: 复杂度 nlogn
: 能通过所有test,代码简洁
:
: rocket

e*********5
发帖数: 137
22
请问LS有什么好建议?

【在 C********e 的大作中提到】
: 你这个解法是O(n^2)的,虽然可以通过所有的test,但是不符合题目的要求。
:
: sort

e*********5
发帖数: 137
23
这个merge了之后本身就已经是按end time排序了。 我的意思是如何update score使得
update的总时间不是 O(n^2)
j*******n
发帖数: 10
24
不是你说的思路, merge 时候修改score的 只有当第二个array 比第一个大的时候
下面代码看了就肯定明白了,就是merge sort 多了一行,每个元素只扫描一次
void merge(vector &racers, int low, int mid, int high)
{
int p1 = low;
int p2 = mid+1;
vector tmp(high-low+1);
int k=0;
while(p1<=mid || p2<=high){
if(p1>mid || (p1<=mid && p2<=high && racers[p2]->end < racers[p1]->end
)){
tmp[k] = racers[p2];
p2++;
}else if (p2>high || (p1<=mid && p2<=high && racers[p2]->end > racers[
p1]->end) ) {
tmp[k] = racers[p1];
racers[p1]->score += (p2-mid-1);
p1++;
}
k++;
}
-------省略----
}
复杂度分析和merge sort 一样 NlogN

(

【在 e*********5 的大作中提到】
: merge的时间是 O(n),但是似乎update score的复杂度是不是 O(n^2)?比如 考虑
: data (start, end) (1, 16), (2,15), (3,14), (4,13), (5,12), (6,11), (7,10), (
: 8,9)
: 下面是两段的end time.第一段的start time小于第二段的start time
: 13 14 15 16 | 9 10 11 12
: merge: end time 13>9,所以跟13, 14, 15 16对应的score都+1。跟9对应的racer
: score不变。 不过比较的话至多就是O(n).
: 这样如果按update score算复杂度,最差可达到 O(n^2).
: 还是说是另外一种思路?
:

j*******n
发帖数: 10
25
同学merge sort 怎么是N^2复杂度,如果你的是N^2,那就不叫merge sort了
anyway 刚解答过了,另外 那个online test case 里面数据很大 NlogN 和N2 差很多,
如果N^2肯定是算法超时,不可能通过测试的,如果他们连超时检测都没有的话,那
test case
设计的也太失败吧 你可以试试N2的算法能通过吗

【在 C********e 的大作中提到】
: 你这个解法是O(n^2)的,虽然可以通过所有的test,但是不符合题目的要求。
:
: sort

e*********5
发帖数: 137
26
明白你的意思了。我知道我的update score为什么出现问题了。 我不应该加+1那么
update. 就是update的时候住需要加合适的数字,只加一次。复杂度确实 O(N logN).
谢谢

end

【在 j*******n 的大作中提到】
: 不是你说的思路, merge 时候修改score的 只有当第二个array 比第一个大的时候
: 下面代码看了就肯定明白了,就是merge sort 多了一行,每个元素只扫描一次
: void merge(vector &racers, int low, int mid, int high)
: {
: int p1 = low;
: int p2 = mid+1;
: vector tmp(high-low+1);
: int k=0;
: while(p1<=mid || p2<=high){
: if(p1>mid || (p1<=mid && p2<=high && racers[p2]->end < racers[p1]->end

C********e
发帖数: 492
27
问题不在merge的时候,而在update的过程。你需要有个list来保存已经出现的stratum
吧,这个update是N^2的

多,

【在 j*******n 的大作中提到】
: 同学merge sort 怎么是N^2复杂度,如果你的是N^2,那就不叫merge sort了
: anyway 刚解答过了,另外 那个online test case 里面数据很大 NlogN 和N2 差很多,
: 如果N^2肯定是算法超时,不可能通过测试的,如果他们连超时检测都没有的话,那
: test case
: 设计的也太失败吧 你可以试试N2的算法能通过吗

n******n
发帖数: 567
28
...............
1 (共1页)
进入JobHunting版参与讨论
相关主题
问一道G家经典老题an old problem on algorithm
求 Maximum Subarray divide and conquer 解法程序员的思维太牛逼了 (转载)
问一道算法题(zz)大家来讨论一下这个求长方形面积的问题吧
Finding all paths sum up to a given value in 150不对吧?再贴这道算法题,寻答案,有包子送
Rocket Fuel今天Skpye面经问个array in place operation的题目
一道rocket f 电面题问个算法题, 关于区间 overlap的
求intersect的圆,求O(nlogn)的方法问一道题(5)
programming pearl看不懂这个题一道大公司诡异的complete binary tree max sum of 2 nodes 题
相关话题的讨论汇总
话题: start话题: end话题: racer话题: idx话题: time