版标的狗狗表情好有范儿哦 - 未名空间MITBBS历史存档

版标的狗狗表情好有范儿哦# pets - 心有所宠

U*i2012-11-18 08:11

1 楼

got several extras

p*u2012-11-18 08:11

2 楼

分享一个得到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！

g*e2012-11-18 08:11

3 楼

不在乎refurbished
有一个18-55的镜头就好
多少钱可以出手?

p*o2012-11-18 08:11

4 楼

跟这个表情一样~~

s*n2012-11-18 08:11

5 楼

这为什么是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

t*82012-11-18 08:11

6 楼

来问的太晚了
前一段时间太多deal了

【在 g*********e 的大作中提到】

: 不在乎refurbished
: 有一个18-55的镜头就好
: 多少钱可以出手?

e*82012-11-18 08:11

7 楼

其实就是inversion counting的马甲...

c*p2012-11-18 08:11

8 楼

mark

x*02012-11-18 08:11

9 楼

m

f*w2012-11-18 08:11

10 楼

Mark
貌似用BIT比segment tree更方便啊

p*u2012-11-18 08:11

11 楼

分享一个得到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*n2012-11-18 08:11

12 楼

这为什么是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*82012-11-18 08:11

13 楼

其实就是inversion counting的马甲...

c*p2012-11-18 08:11

14 楼

mark

x*02012-11-18 08:11

15 楼

m

G*e2012-11-18 08:11

16 楼

如果说对区间测长度有一个先验的估计，这个算法是n log n
的。

j*d2012-11-18 08:11

17 楼

居然还有人往这坑里面跳。我老佩服了

G*e2012-11-18 08:11

18 楼

如果说对区间测长度有一个先验的估计，这个算法是n log n
的。

j*d2012-11-18 08:11

19 楼

居然还有人往这坑里面跳。我老佩服了

c*t2012-11-18 08:11

20 楼

mark

d*n2012-11-18 08:11

21 楼

You can also check here:
http://codeanytime.blogspot.com/2013/05/score-of-racers.html

【在 c***t 的大作中提到】

: mark

v*22012-11-18 08:11

22 楼

收到rocket fuel的online test，叫word game 俩小时，借楼求问有谁做过没？题意是
啥，多谢多谢！

j*n2012-11-18 08:11

23 楼

这个题目用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*52012-11-18 08:11

24 楼

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*e2012-11-18 08:11

25 楼

你这个解法是O(n^2)的，虽然可以通过所有的test，但是不符合题目的要求。

sort

【在 j*******n 的大作中提到】

: 这个题目用merge sort，先按照start time sort ，然后按照 end time merge sort
: ，类似inverse count
: 复杂度 nlogn
: 能通过所有test，代码简洁
:
: rocket

e*52012-11-18 08:11

26 楼

请问LS有什么好建议？

【在 C********e 的大作中提到】

: 你这个解法是O(n^2)的，虽然可以通过所有的test，但是不符合题目的要求。
:
: sort

e*52012-11-18 08:11

27 楼

这个merge了之后本身就已经是按end time排序了。我的意思是如何update score使得
update的总时间不是 O(n^2)

j*n2012-11-18 08:11

28 楼

不是你说的思路， 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*n2012-11-18 08:11

29 楼

同学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*52012-11-18 08:11

30 楼

明白你的意思了。我知道我的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*e2012-11-18 08:11

31 楼

问题不在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*n2012-11-18 08:11

32 楼

...............