西雅图OCI 安赛

第二轮比较难。第三轮被一个老硬坑了。估计希望不大。

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

楼主之前没有安赛过，就当是练习赞经验了。 第三轮的硬度人很奇葩，感觉他就是想来搞你。不知道大家对于这种情况有什么高见没。

yangmyfly 发表于 2019-12-28 06:03
第二轮区间树，考这个不知道基本gg

补充内容 (2019-12-27 14:06):

为什么是区间树， 他题目没有说频繁更改range和对应的值。 treemap就好吧

第二题，用一个LIST存INTERVAL。每次PUT的时候，都根据INTERVAL START的时间来BINARY SEARCH一次自己要插入的位置，这样子就可以得到一个根据START时间递增的INTERVAL LIST。检查冲突的时候就是根据BINARY SEARCH得到的INDEX来检查自己和前后的INTERVAL有没有冲突。 可以这样做吗。

yangmyfly 发表于 2019-12-28 08:41
TreeMap也可以, 但是interval tree专门就是做这个的

老哥 能方便解释下这个 interval tree么 我看了些 资料 ， 他是存储 一个当前节点下subtree可以达到最大的值的一个数据结构。 但是对于这个题， 是需要一个map的结构。 请问怎么用interval tree？ 我只能想到maptree。

。。lz请问是什么组啊？ BQ多么？
至于你这个第三轮问题。我觉得可以和HM沟通下。 说不定可以加面。
谢谢。

第三轮老印是不是要two pass + O(N) space的解？

第二轮区间树，考这个不知道基本gg

补充内容 (2019-12-27 14:06):
知道就很简单了。。

wtcupup 发表于 2019-12-27 13:43
第三轮老印是不是要two pass + O(N) space的解？

不是的。two passes + O(1)

yangmyfly 发表于 2019-12-28 06:03
第二轮区间树，考这个不知道基本gg

补充内容 (2019-12-27 14:06):

对。。这个就是treemap。。如果用python的话 还不好写。。只有java c++有这个

ninepig 发表于 2019/12/28 08:36:17
对。。这个就是treemap。。如果用python的话 还不好写。。只有java c++有这个

TreeMap也可以, 但是interval tree专门就是做这个的

ninepig 发表于 2019/12/29 08:45:23
老哥 能方便解释下这个 interval tree么 我看了些 资料 ， 他是存储 一个当前节点下subtree可以达到...

写了下，treemap确实更好写，就是calendar1，interval tree的max不是存最大值，存的是当前node下的最大边界值

补充内容 (2019-12-28 17:07):
treemap本质也是棵平衡二叉搜索树呀，没有什么map