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 x*****0 发帖数: 452 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
x*****0 发帖数: 452 G*********e 发帖数: 56 12
如果说对区间测长度有一个先验的估计, 这个算法是n log n
的。 j*****d 发帖数: 1625 G*********e 发帖数: 56 14
如果说对区间测长度有一个先验的估计, 这个算法是n log n
的。 j*****d 发帖数: 1625 c***t 发帖数: 50 d****n 发帖数: 233 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
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