多年不打鱼连网都不会用了 - 未名空间MITBBS历史存档

A*i2014-03-01 08:03

1 楼

今天刚被一个游戏公司虐了
原题如下：
三个methods: addRange(), queryRange(), deleteRange();
addRange用来给定一个范围内的数字比如addRange(10, 200)表示10到200这个区间的数
字被加入到range中，queryRange用来判定当前range有没有在被加进去的range里面举
个例子：
addRange(10, 200);
addRange(250, 500);
然后再queryRange(180, 300)的时候应该返回false，因为有201-249这一段没有被加入
deleteRange很简单只要delete掉相应的range就可以
弄了很久总觉得不能优化……遂放弃

f*e2014-03-01 08:03

2 楼

不是leetcode题么？周六面试比较奇葩。

【在 A*****i 的大作中提到】

: 今天刚被一个游戏公司虐了
: 原题如下：
: 三个methods: addRange(), queryRange(), deleteRange();
: addRange用来给定一个范围内的数字比如addRange(10, 200)表示10到200这个区间的数
: 字被加入到range中，queryRange用来判定当前range有没有在被加进去的range里面举
: 个例子：
: addRange(10, 200);
: addRange(250, 500);
: 然后再queryRange(180, 300)的时候应该返回false，因为有201-249这一段没有被加入
: deleteRange很简单只要delete掉相应的range就可以

A*i2014-03-01 08:03

3 楼

想知道有没有最优解……
leetcode上现在有解了？

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

: 不是leetcode题么？周六面试比较奇葩。

e*a2014-03-01 08:03

4 楼

what is the name of this company?

A*i2014-03-01 08:03

5 楼

machine zone
游戏公司用来练手的，没想到丫也从leetcode上出题啊
真没节操

y*n2014-03-01 08:03

6 楼

我怎么没有见过

x*r2014-03-01 08:03

7 楼

这是leetcode哪个题？
好像没见过。

【在 A*****i 的大作中提到】

: machine zone
: 游戏公司用来练手的，没想到丫也从leetcode上出题啊
: 真没节操

p*22014-03-01 08:03

8 楼

大牛这题怎么解的？他们有复杂度要求吗？

A*i2014-03-01 08:03

9 楼

我擦我就是想不出更牛逼的办法了才来问的
没复杂度要求但是说目标数组是M级别的所以需要优化时间和空间……

【在 p*****2 的大作中提到】

: 大牛这题怎么解的？他们有复杂度要求吗？

p*22014-03-01 08:03

10 楼

O(n)的话比较容易，M级别感觉O(n)也够了，不然就上interval tree?

【在 A*****i 的大作中提到】

: 我擦我就是想不出更牛逼的办法了才来问的
: 没复杂度要求但是说目标数组是M级别的所以需要优化时间和空间……

A*i2014-03-01 08:03

11 楼

我觉得O（N）太容易了，弄个大点儿的数组就成，但是我觉得人家的要求应该在O(1)左右
我开始写个O(N)的发现太容易了，觉得人家给我俩小时不能就弄个这吧……结果琢磨到
点儿了还没想出更好的

【在 p*****2 的大作中提到】

:
: O(n)的话比较容易，M级别感觉O(n)也够了，不然就上interval tree?

p*22014-03-01 08:03

12 楼

左右
O(N) bug free也不容易。O(1)不可能吧，最多就是优化到logN吧。

【在 A*****i 的大作中提到】

: 我觉得O（N）太容易了，弄个大点儿的数组就成，但是我觉得人家的要求应该在O(1)左右
: 我开始写个O(N)的发现太容易了，觉得人家给我俩小时不能就弄个这吧……结果琢磨到
: 点儿了还没想出更好的

t*h2014-03-01 08:03

13 楼

这个按左边边界binary search一下发现180 在10，250之间那肯定就没在range里了
log(n)

【在 A*****i 的大作中提到】

: 今天刚被一个游戏公司虐了
: 原题如下：
: 三个methods: addRange(), queryRange(), deleteRange();
: addRange用来给定一个范围内的数字比如addRange(10, 200)表示10到200这个区间的数
: 字被加入到range中，queryRange用来判定当前range有没有在被加进去的range里面举
: 个例子：
: addRange(10, 200);
: addRange(250, 500);
: 然后再queryRange(180, 300)的时候应该返回false，因为有201-249这一段没有被加入
: deleteRange很简单只要delete掉相应的range就可以

d*g2014-03-01 08:03

14 楼

把rang存为pair
class Pair{
int start;
int end;
}
然后每次addRang()的时候对已经存在的pair进行融合,,,
然后query的时候就进行比较,
感觉就是lc原题啊..有点变化,时间复杂度是多少?我不知道啊...总之好于O(n)

m*l2014-03-01 08:03

15 楼

不是吧
右边界也要考虑啊
（180， 190）就是返回true啊

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

: 这个按左边边界binary search一下发现180 在10，250之间那肯定就没在range里了
: log(n)

m*l2014-03-01 08:03

16 楼

哪道原题啊
我咋没有印象

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

: 把rang存为pair
: class Pair{
: int start;
: int end;
: }
: 然后每次addRang()的时候对已经存在的pair进行融合,,,
: 然后query的时候就进行比较,
: 感觉就是lc原题啊..有点变化,时间复杂度是多少?我不知道啊...总之好于O(n)

t*h2014-03-01 08:03

17 楼

每次addrange之后你都要merge好这样每次查询看一边就可以了

【在 m********l 的大作中提到】

: 不是吧
: 右边界也要考虑啊
: （180， 190）就是返回true啊

A*i2014-03-01 08:03

18 楼

今天刚被一个游戏公司虐了
原题如下：
三个methods: addRange(), queryRange(), deleteRange();
addRange用来给定一个范围内的数字比如addRange(10, 200)表示10到200这个区间的数
字被加入到range中，queryRange用来判定当前range有没有在被加进去的range里面举
个例子：
addRange(10, 200);
addRange(250, 500);
然后再queryRange(180, 300)的时候应该返回false，因为有201-249这一段没有被加入
deleteRange很简单只要delete掉相应的range就可以
弄了很久总觉得不能优化……遂放弃

f*e2014-03-01 08:03

19 楼

不是leetcode题么？周六面试比较奇葩。

【在 A*****i 的大作中提到】

: 今天刚被一个游戏公司虐了
: 原题如下：
: 三个methods: addRange(), queryRange(), deleteRange();
: addRange用来给定一个范围内的数字比如addRange(10, 200)表示10到200这个区间的数
: 字被加入到range中，queryRange用来判定当前range有没有在被加进去的range里面举
: 个例子：
: addRange(10, 200);
: addRange(250, 500);
: 然后再queryRange(180, 300)的时候应该返回false，因为有201-249这一段没有被加入
: deleteRange很简单只要delete掉相应的range就可以

A*i2014-03-01 08:03

20 楼

想知道有没有最优解……
leetcode上现在有解了？

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

: 不是leetcode题么？周六面试比较奇葩。

e*a2014-03-01 08:03

21 楼

what is the name of this company?

A*i2014-03-01 08:03

22 楼

machine zone
游戏公司用来练手的，没想到丫也从leetcode上出题啊
真没节操

y*n2014-03-01 08:03

23 楼

我怎么没有见过

x*r2014-03-01 08:03

24 楼

这是leetcode哪个题？
好像没见过。

【在 A*****i 的大作中提到】

: machine zone
: 游戏公司用来练手的，没想到丫也从leetcode上出题啊
: 真没节操

p*22014-03-01 08:03

25 楼

大牛这题怎么解的？他们有复杂度要求吗？

A*i2014-03-01 08:03

26 楼

我擦我就是想不出更牛逼的办法了才来问的
没复杂度要求但是说目标数组是M级别的所以需要优化时间和空间……

【在 p*****2 的大作中提到】

: 大牛这题怎么解的？他们有复杂度要求吗？

p*22014-03-01 08:03

27 楼

O(n)的话比较容易，M级别感觉O(n)也够了，不然就上interval tree?

【在 A*****i 的大作中提到】

: 我擦我就是想不出更牛逼的办法了才来问的
: 没复杂度要求但是说目标数组是M级别的所以需要优化时间和空间……

A*i2014-03-01 08:03

28 楼

我觉得O（N）太容易了，弄个大点儿的数组就成，但是我觉得人家的要求应该在O(1)左右
我开始写个O(N)的发现太容易了，觉得人家给我俩小时不能就弄个这吧……结果琢磨到
点儿了还没想出更好的

【在 p*****2 的大作中提到】

:
: O(n)的话比较容易，M级别感觉O(n)也够了，不然就上interval tree?

p*22014-03-01 08:03

29 楼

左右
O(N) bug free也不容易。O(1)不可能吧，最多就是优化到logN吧。

【在 A*****i 的大作中提到】

: 我觉得O（N）太容易了，弄个大点儿的数组就成，但是我觉得人家的要求应该在O(1)左右
: 我开始写个O(N)的发现太容易了，觉得人家给我俩小时不能就弄个这吧……结果琢磨到
: 点儿了还没想出更好的

t*h2014-03-01 08:03

30 楼

这个按左边边界binary search一下发现180 在10，250之间那肯定就没在range里了
log(n)

【在 A*****i 的大作中提到】

: 今天刚被一个游戏公司虐了
: 原题如下：
: 三个methods: addRange(), queryRange(), deleteRange();
: addRange用来给定一个范围内的数字比如addRange(10, 200)表示10到200这个区间的数
: 字被加入到range中，queryRange用来判定当前range有没有在被加进去的range里面举
: 个例子：
: addRange(10, 200);
: addRange(250, 500);
: 然后再queryRange(180, 300)的时候应该返回false，因为有201-249这一段没有被加入
: deleteRange很简单只要delete掉相应的range就可以

d*g2014-03-01 08:03

31 楼

把rang存为pair
class Pair{
int start;
int end;
}
然后每次addRang()的时候对已经存在的pair进行融合,,,
然后query的时候就进行比较,
感觉就是lc原题啊..有点变化,时间复杂度是多少?我不知道啊...总之好于O(n)

m*l2014-03-01 08:03

32 楼

不是吧
右边界也要考虑啊
（180， 190）就是返回true啊

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

: 这个按左边边界binary search一下发现180 在10，250之间那肯定就没在range里了
: log(n)

m*l2014-03-01 08:03

33 楼

哪道原题啊
我咋没有印象

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

: 把rang存为pair
: class Pair{
: int start;
: int end;
: }
: 然后每次addRang()的时候对已经存在的pair进行融合,,,
: 然后query的时候就进行比较,
: 感觉就是lc原题啊..有点变化,时间复杂度是多少?我不知道啊...总之好于O(n)

t*h2014-03-01 08:03

34 楼

每次addrange之后你都要merge好这样每次查询看一边就可以了

【在 m********l 的大作中提到】

: 不是吧
: 右边界也要考虑啊
: （180， 190）就是返回true啊

d*n2014-03-01 08:03

35 楼

请问大神，后来又拿到onsite吗？

【在 A*****i 的大作中提到】

: 今天刚被一个游戏公司虐了
: 原题如下：
: 三个methods: addRange(), queryRange(), deleteRange();
: addRange用来给定一个范围内的数字比如addRange(10, 200)表示10到200这个区间的数
: 字被加入到range中，queryRange用来判定当前range有没有在被加进去的range里面举
: 个例子：
: addRange(10, 200);
: addRange(250, 500);
: 然后再queryRange(180, 300)的时候应该返回false，因为有201-249这一段没有被加入
: deleteRange很简单只要delete掉相应的range就可以

t*h2014-03-01 08:03

36 楼

不是lc 题

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

: 不是leetcode题么？周六面试比较奇葩。

l*a2014-03-01 08:03

37 楼

addRange不就是insert interval吗？
query 也差不多，binary search找出start/end的插入位置，就可以判断是不是在原来
区间了

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

: 不是lc 题