一亩三分地论坛

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

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

[学Java/C#] 分享一个昨天被三哥黑的题。。。

[复制链接] |试试Instant~ |关注本帖
milanelllo13 发表于 2015-7-4 06:29:49 | 显示全部楼层 |阅读模式

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

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

x
昨天面的是一家start up。
题目是,有一个不断给 interval 的stream,每个interval都会有个id  比如 1 {1, 3},2 {2, 10},3 {3, 2^26}, 怎么存这个interval,以及给出一个数,实现delete掉所有包含了这个数的intervals。比如 给个数2,那么第一个 和 第二个interval 就要delete掉。 要尽量fast。

因为我实在水平有限。。。 也还没怎么看过 设计题。 所以总感觉被黑了。。也有可能是我冤枉了面试官= =~~
 楼主| milanelllo13 发表于 2015-7-5 13:23:34 | 显示全部楼层
handsomecool 发表于 2015-7-5 12:24
呃。。。又想了想,貌似有不用interval tree的做法。。。
Insert的时候通过取交集把这些interval细分成更 ...

感谢分享解法! ~
回复 支持 1 反对 0

使用道具 举报

glaciersilent 发表于 2015-7-4 06:44:37 | 显示全部楼层
感觉Interval tree似乎挺适合这个问题
回复 支持 反对

使用道具 举报

 楼主| milanelllo13 发表于 2015-7-4 09:13:44 | 显示全部楼层
glaciersilent 发表于 2015-7-4 06:44
感觉Interval tree似乎挺适合这个问题

感觉可以 但我不会
回复 支持 反对

使用道具 举报

 楼主| milanelllo13 发表于 2015-7-4 09:19:43 | 显示全部楼层
glaciersilent 发表于 2015-7-4 06:44
感觉Interval tree似乎挺适合这个问题

刚刚看了下interval tree..  我当时也想到了  写了 大概画了画 还没想明白  他就说 你这个search 时间是多少,然后感觉他想要O(1), 意思,要用map?。。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-4 10:14:44 | 显示全部楼层
milanelllo13 发表于 2015-7-4 09:19
刚刚看了下interval tree..  我当时也想到了  写了 大概画了画 还没想明白  他就说 你这个search 时间是 ...

O(1)应该不太可能。因为最坏情况下可能需要删除所有的intervals。这至少是一个O(N)操作。
回复 支持 反对

使用道具 举报

 楼主| milanelllo13 发表于 2015-7-4 10:51:44 | 显示全部楼层
stellari 发表于 2015-7-4 10:14
O(1)应该不太可能。因为最坏情况下可能需要删除所有的intervals。这至少是一个O(N)操作。

那大概应该怎么做呢。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-4 11:06:23 | 显示全部楼层
milanelllo13 发表于 2015-7-4 10:51
那大概应该怎么做呢。

我能想到的最好解法就是Interval Tree了。总之,想在O(1)时间内删除K个范围,这点理论上来说不太可能。
回复 支持 反对

使用道具 举报

 楼主| milanelllo13 发表于 2015-7-4 11:20:25 | 显示全部楼层
stellari 发表于 2015-7-4 11:06
我能想到的最好解法就是Interval Tree了。总之,想在O(1)时间内删除K个范围,这点理论上来说不太可能。

谢谢,我用interval tree 试试!
回复 支持 反对

使用道具 举报

glaciersilent 发表于 2015-7-4 11:36:08 | 显示全部楼层
milanelllo13 发表于 2015-7-4 11:20
谢谢,我用interval tree 试试!

这是个电面么?感觉如果真需要用Interval tree才能做得话 这确实是三哥在黑你。。。
回复 支持 反对

使用道具 举报

 楼主| milanelllo13 发表于 2015-7-4 12:21:32 | 显示全部楼层
glaciersilent 发表于 2015-7-4 11:36
这是个电面么?感觉如果真需要用Interval tree才能做得话 这确实是三哥在黑你。。。

是onsite的第一轮。。  我是真的感觉自己被黑= =~
回复 支持 反对

使用道具 举报

wangxinlei 发表于 2015-7-4 14:26:01 | 显示全部楼层
楼主面的是不是H打头的那家?因为我也是被问到这个题。。
回复 支持 反对

使用道具 举报

 楼主| milanelllo13 发表于 2015-7-4 14:30:02 | 显示全部楼层
wangxinlei 发表于 2015-7-4 14:26
楼主面的是不是H打头的那家?因为我也是被问到这个题。。

是啊。。 你感觉是被被黑了吗。。。
回复 支持 反对

使用道具 举报

wangxinlei 发表于 2015-7-4 23:17:59 | 显示全部楼层
必须是啊,阿三全程啃手指玩手机。。。或者他们是要找更牛逼的人?
回复 支持 反对

使用道具 举报

 楼主| milanelllo13 发表于 2015-7-5 02:42:35 | 显示全部楼层
wangxinlei 发表于 2015-7-4 23:17
必须是啊,阿三全程啃手指玩手机。。。或者他们是要找更牛逼的人?

我狭隘的认为他想找个印度人。。。
回复 支持 反对

使用道具 举报

handsomecool 发表于 2015-7-5 06:25:33 | 显示全部楼层
应该是interval tree了, 支持log(n)的各种操作 , interval tree本身不难但没学过要现场想就好难啊我感觉。。。 我就没学过,刷题才偶然接触到的,还觉得一定不会考呢。。 ╮(╯_╰)╭
回复 支持 反对

使用道具 举报

handsomecool 发表于 2015-7-5 12:24:22 | 显示全部楼层
本帖最后由 handsomecool 于 2015-7-5 12:34 编辑

呃。。。又想了想,貌似有不用interval tree的做法。。。
Insert的时候通过取交集把这些interval细分成更小的闭区间,以区间开始为key用BST结构去存,并记录下每个区间对应的原区间的ID。
1 {1, 3},2 {2, 10},3 {3, 2^26} 就变成了:

Interval ----------------------------ID
[1,   1]                                   1
[2,   2]                                   1, 2
[3,   3]                                   1, 2, 3
[4,  10]                                  2, 3
[11, 2^26]                             3


然后如果你要删掉含有2的interval, 只要log(n)的时间(因为用了BST) 就可以找到它所在的区间[2, 2] 然后删掉对应的ID 1 和 2 。
如果还要删掉细分后的Interval里对应的ID就比较麻烦了, 而且如果Interval的ID删完变空了,那个Interval就直接不要了, 所以还要个map来存ID反过来对应了哪些细分的Interval, 比如ID 2:{2, 3, 4}  (这里的 2, 3, 4 是细分Interval的key)...
下图的红色部分是删掉的。

Interval ----------------------------ID
[1,   1]                                   1
[2,   2]                                   1, 2

[3,   3]                                   1, 2, 3
[4,  10]                                  2, 3
[11, 2^26]                             3


也可以不删掉细分后的interval, 给每个ID存一个是否已经被删除的flag, 这样就简单多了。
回复 支持 反对

使用道具 举报

 楼主| milanelllo13 发表于 2015-7-5 13:17:33 | 显示全部楼层
handsomecool 发表于 2015-7-5 12:24
呃。。。又想了想,貌似有不用interval tree的做法。。。
Insert的时候通过取交集把这些interval细分成更 ...

我觉得这样做是对的!
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-5 14:09:41 | 显示全部楼层
handsomecool 发表于 2015-7-5 12:24
呃。。。又想了想,貌似有不用interval tree的做法。。。
Insert的时候通过取交集把这些interval细分成更 ...

这其实就是“离散化的线段树(segment tree)”吧。这种方法可以,但是插入时间似乎会比较长,比如如果某时刻加入了一个很长的interval,覆盖了之前的所有interval,那么之前每个Interval对应的ID就必须更新,这是一个O(N)操作。查找+删除依然是O(logN + N)操作,和Interval Tree一样。但是Interval Tree的插入时间是O(logN),这点应该是优于此方法的。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 16:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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