📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 3077| 回复: 18
跳转到指定楼层
上一主题 下一主题
收起左侧

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

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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

因为我实在水平有限。。。 也还没怎么看过 设计题。 所以总感觉被黑了。。也有可能是我冤枉了面试官= =~~

上一篇:问一个关于while的问题
下一篇:怎么创建一个static unordered_map
推荐
 楼主| milanelllo13 2015-7-5 13:23:34 | 只看该作者
全局:
handsomecool 发表于 2015-7-5 12:24
呃。。。又想了想,貌似有不用interval tree的做法。。。
Insert的时候通过取交集把这些interval细分成更 ...

感谢分享解法! ~
回复

使用道具 举报

全局:
本帖最后由 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, 这样就简单多了。
回复

使用道具 举报

推荐
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),这点应该是优于此方法的。
回复

使用道具 举报

全局:
感觉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 试试!
回复

使用道具 举报

全局:
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的第一轮。。  我是真的感觉自己被黑= =~
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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