s********u
发帖数: 1109 | 1 是个国人大哥，人很nice，不过下午很冷，穿了衣服还哆嗦。而且中间collabedit抽风
了几次，然后有些写的就没了，谁知道什么问题么？感觉很奇怪啊，就算断网也不该这
样吧。不过他说会给足时间。
题目好像以前见过，就是给一些不重叠的interval，然后设计一个数据结构来存储，实
现插入interval和find一个value两个函数，前者碰到重叠就return false，后者碰到
所在的interval返回。
分享题目和答案：https://docs.google.com/document/d/
1fXfv0GDKc6Uu03ZUU7iac9TcEqpv2YePDE9IAzwhPGo/edit
这个我记得就是用BST做的。
有一个bug，就是插入的时候给空指针 n = new Node(c),这么做了，被指出了，还是基
础不扎实啊，可能以前都是链表或者用递归做的，就从来没发现这个问题。应该说明下
还可以用递归做的。
中间讨论了一下维护min和max变量是否必要，我说主要是在val超出范围的时候直接判
断，他说那其实interval中间也有空当。我就说那就只有两端的时候，会比较有用，而
且我这个办法维护min和max每次都要做一次，应该有更好的。对average case是没有用
的。
最后问了下time cost，就是O(lgn)和o(n)，分别对应average和worst，他说怎么保证
balanced，就说就可以了，我说可以用红黑树或者AVL，或者先找中位数插入（后来一
想应该是先排序）
用sorted array行不行，与BST比较优缺点（前者没overhead，但是无法动态插入和删
除）。似乎他还挺满意。
让我问问题之后就欢快的结束了。 |
m********y
发帖数: 84 | |
P*******r
发帖数: 210 | |
b*******e
发帖数: 123 | |
u*****o
发帖数: 1224 | |
d**********x
发帖数: 4083 | 6 zhu wu yun chang long!
bless!
【在 s********u 的大作中提到】
: 是个国人大哥，人很nice，不过下午很冷，穿了衣服还哆嗦。而且中间collabedit抽风
: 了几次，然后有些写的就没了，谁知道什么问题么？感觉很奇怪啊，就算断网也不该这
: 样吧。不过他说会给足时间。
: 题目好像以前见过，就是给一些不重叠的interval，然后设计一个数据结构来存储，实
: 现插入interval和find一个value两个函数，前者碰到重叠就return false，后者碰到
: 所在的interval返回。
: 分享题目和答案：https://docs.google.com/document/d/
: 1fXfv0GDKc6Uu03ZUU7iac9TcEqpv2YePDE9IAzwhPGo/edit
: 这个我记得就是用BST做的。
: 有一个bug，就是插入的时候给空指针 n = new Node(c),这么做了，被指出了，还是基
|
J*******o
发帖数: 741 | |
l*n
发帖数: 529 | 8 max/min确实不需要吧？可能是有点紧张了。
【在 s********u 的大作中提到】
: 是个国人大哥，人很nice，不过下午很冷，穿了衣服还哆嗦。而且中间collabedit抽风
: 了几次，然后有些写的就没了，谁知道什么问题么？感觉很奇怪啊，就算断网也不该这
: 样吧。不过他说会给足时间。
: 题目好像以前见过，就是给一些不重叠的interval，然后设计一个数据结构来存储，实
: 现插入interval和find一个value两个函数，前者碰到重叠就return false，后者碰到
: 所在的interval返回。
: 分享题目和答案：https://docs.google.com/document/d/
: 1fXfv0GDKc6Uu03ZUU7iac9TcEqpv2YePDE9IAzwhPGo/edit
: 这个我记得就是用BST做的。
: 有一个bug，就是插入的时候给空指针 n = new Node(c),这么做了，被指出了，还是基
|
n****e
发帖数: 678 | |
m**********g
发帖数: 153 | 10 楼主牛啊。 我的话就跪了。
另外这好像是linux vma 管理的简化版 |
|
|
s********u
发帖数: 1109 | 11 如果是超出range的数，查询的时候有min和max直接O(1)。还是有点小帮助吧。其实倒
也不紧张，就是这几天连续面试，有点累了。今天如果是阿三，可能直接就跪了。
【在 l*n 的大作中提到】
: max/min确实不需要吧？可能是有点紧张了。
|
w**t
发帖数: 893 | 12 这个是interval tree special case 吗？
【在 s********u 的大作中提到】
: 是个国人大哥，人很nice，不过下午很冷，穿了衣服还哆嗦。而且中间collabedit抽风
: 了几次，然后有些写的就没了，谁知道什么问题么？感觉很奇怪啊，就算断网也不该这
: 样吧。不过他说会给足时间。
: 题目好像以前见过，就是给一些不重叠的interval，然后设计一个数据结构来存储，实
: 现插入interval和find一个value两个函数，前者碰到重叠就return false，后者碰到
: 所在的interval返回。
: 分享题目和答案：https://docs.google.com/document/d/
: 1fXfv0GDKc6Uu03ZUU7iac9TcEqpv2YePDE9IAzwhPGo/edit
: 这个我记得就是用BST做的。
: 有一个bug，就是插入的时候给空指针 n = new Node(c),这么做了，被指出了，还是基
|
f********e
发帖数: 91 | 13 Good luck！ 肯定拿到onsite了！
【在 s********u 的大作中提到】
: 是个国人大哥，人很nice，不过下午很冷，穿了衣服还哆嗦。而且中间collabedit抽风
: 了几次，然后有些写的就没了，谁知道什么问题么？感觉很奇怪啊，就算断网也不该这
: 样吧。不过他说会给足时间。
: 题目好像以前见过，就是给一些不重叠的interval，然后设计一个数据结构来存储，实
: 现插入interval和find一个value两个函数，前者碰到重叠就return false，后者碰到
: 所在的interval返回。
: 分享题目和答案：https://docs.google.com/document/d/
: 1fXfv0GDKc6Uu03ZUU7iac9TcEqpv2YePDE9IAzwhPGo/edit
: 这个我记得就是用BST做的。
: 有一个bug，就是插入的时候给空指针 n = new Node(c),这么做了，被指出了，还是基
|
J****3
发帖数: 427 | 14 Bless 先
貌似link打不开了？ 这个应该就是你之前说过EPI上有最优解的那个题吧 |
i*******e
发帖数: 69 | |
c********p
发帖数: 1969 | |
c********e
发帖数: 186 | |
s********u
发帖数: 1109 | 18 我看了下interval tree，有点这么个意思，只不过interval tree是可以overlap，而
且一般是要搜interval。
还有就是interval tree每个节点都会维护一个max field。
【在 w**t 的大作中提到】
: 这个是interval tree special case 吗？
|
b*****c
发帖数: 1103 | 19 segment tree就行了，就是线段树。
n个插入最多有2n个点，这个树最大是6n个点吗 |
b*****c
发帖数: 1103 | 20 online算法就不能线段树。
直接上stl::map 直接就是排序的。
代码晚点写。 |
|
|
b*****c
发帖数: 1103 | 21 c++ stl就是万能啊，再加上hashmap就无敌了 |
n****e
发帖数: 678 | 22 没有看懂这句：
“有一个bug，就是插入的时候给空指针 n = new Node(c),这么做了，被指出了，还是基
础不扎实啊，可能以前都是链表或者用递归做的，就从来没发现这个问题。应该说明下
还可以用递归做的。”
能详细说说吗？
【在 s********u 的大作中提到】
: 是个国人大哥，人很nice，不过下午很冷，穿了衣服还哆嗦。而且中间collabedit抽风
: 了几次，然后有些写的就没了，谁知道什么问题么？感觉很奇怪啊，就算断网也不该这
: 样吧。不过他说会给足时间。
: 题目好像以前见过，就是给一些不重叠的interval，然后设计一个数据结构来存储，实
: 现插入interval和find一个value两个函数，前者碰到重叠就return false，后者碰到
: 所在的interval返回。
: 分享题目和答案：https://docs.google.com/document/d/
: 1fXfv0GDKc6Uu03ZUU7iac9TcEqpv2YePDE9IAzwhPGo/edit
: 这个我记得就是用BST做的。
: 有一个bug，就是插入的时候给空指针 n = new Node(c),这么做了，被指出了，还是基
|
x*****a
发帖数: 9 | 23 segment tree 是static structure, 在不知道整个区间的情况下, 你没办法做
这个interval tree就可以了, 不考虑旋转
【在 b*****c 的大作中提到】
: segment tree就行了，就是线段树。
: n个插入最多有2n个点，这个树最大是6n个点吗
|
l****o
发帖数: 315 | 24 用ArrayList， 插入时二分查找logN, insertion average O(1), worst O(n). Find
也用二分LogN. |
s********u
发帖数: 1109 | 25 是个国人大哥，人很nice，不过下午很冷，穿了衣服还哆嗦。而且中间collabedit抽风
了几次，然后有些写的就没了，谁知道什么问题么？感觉很奇怪啊，就算断网也不该这
样吧。不过他说会给足时间。
题目好像以前见过，就是给一些不重叠的interval，然后设计一个数据结构来存储，实
现插入interval和find一个value两个函数，前者碰到重叠就return false，后者碰到
所在的interval返回。
分享题目和答案：https://docs.google.com/document/d/
1fXfv0GDKc6Uu03ZUU7iac9TcEqpv2YePDE9IAzwhPGo/edit?usp=sharing
这个我记得就是用BST做的。
有一个bug，就是插入的时候给空指针 n = new Node(c),这么做了，被指出了，还是基
础不扎实啊，可能以前都是链表或者用递归做的，就从来没发现这个问题。应该说明下
还可以用递归做的。
中间讨论了一下维护min和max变量是否必要，我说主要是在val超出范围的时候直接判
断，他说那其实interval中间也有空当。我就说那就只有两端的时候，会比较有用，而
且我这个办法维护min和max每次都要做一次，应该有更好的。对average case是没有用
的。
最后问了下time cost，就是O(lgn)和o(n)，分别对应average和worst，他说怎么保证
balanced，就说就可以了，我说可以用红黑树或者AVL，或者先找中位数插入（后来一
想应该是先排序）
用sorted array行不行，与BST比较优缺点（前者没overhead，但是无法动态插入和删
除）。似乎他还挺满意。
让我问问题之后就欢快的结束了。 |
m********y
发帖数: 84 | |
P*******r
发帖数: 210 | |
b*******e
发帖数: 123 | |
u*****o
发帖数: 1224 | |
d**********x
发帖数: 4083 | 30 zhu wu yun chang long!
bless!
【在 s********u 的大作中提到】
: 是个国人大哥，人很nice，不过下午很冷，穿了衣服还哆嗦。而且中间collabedit抽风
: 了几次，然后有些写的就没了，谁知道什么问题么？感觉很奇怪啊，就算断网也不该这
: 样吧。不过他说会给足时间。
: 题目好像以前见过，就是给一些不重叠的interval，然后设计一个数据结构来存储，实
: 现插入interval和find一个value两个函数，前者碰到重叠就return false，后者碰到
: 所在的interval返回。
: 分享题目和答案：https://docs.google.com/document/d/
: 1fXfv0GDKc6Uu03ZUU7iac9TcEqpv2YePDE9IAzwhPGo/edit?usp=sharing
: 这个我记得就是用BST做的。
: 有一个bug，就是插入的时候给空指针 n = new Node(c),这么做了，被指出了，还是基
|
|
|
J*******o
发帖数: 741 | |
l*n
发帖数: 529 | 32 max/min确实不需要吧？可能是有点紧张了。
【在 s********u 的大作中提到】
: 是个国人大哥，人很nice，不过下午很冷，穿了衣服还哆嗦。而且中间collabedit抽风
: 了几次，然后有些写的就没了，谁知道什么问题么？感觉很奇怪啊，就算断网也不该这
: 样吧。不过他说会给足时间。
: 题目好像以前见过，就是给一些不重叠的interval，然后设计一个数据结构来存储，实
: 现插入interval和find一个value两个函数，前者碰到重叠就return false，后者碰到
: 所在的interval返回。
: 分享题目和答案：https://docs.google.com/document/d/
: 1fXfv0GDKc6Uu03ZUU7iac9TcEqpv2YePDE9IAzwhPGo/edit?usp=sharing
: 这个我记得就是用BST做的。
: 有一个bug，就是插入的时候给空指针 n = new Node(c),这么做了，被指出了，还是基
|
n****e
发帖数: 678 | |
m**********g
发帖数: 153 | 34 楼主牛啊。 我的话就跪了。
另外这好像是linux vma 管理的简化版 |
s********u
发帖数: 1109 | 35 如果是超出range的数，查询的时候有min和max直接O(1)。还是有点小帮助吧。其实倒
也不紧张，就是这几天连续面试，有点累了。今天如果是阿三，可能直接就跪了。
【在 l*n 的大作中提到】
: max/min确实不需要吧？可能是有点紧张了。
|
w**t
发帖数: 893 | 36 这个是interval tree special case 吗？
【在 s********u 的大作中提到】
: 是个国人大哥，人很nice，不过下午很冷，穿了衣服还哆嗦。而且中间collabedit抽风
: 了几次，然后有些写的就没了，谁知道什么问题么？感觉很奇怪啊，就算断网也不该这
: 样吧。不过他说会给足时间。
: 题目好像以前见过，就是给一些不重叠的interval，然后设计一个数据结构来存储，实
: 现插入interval和find一个value两个函数，前者碰到重叠就return false，后者碰到
: 所在的interval返回。
: 分享题目和答案：https://docs.google.com/document/d/
: 1fXfv0GDKc6Uu03ZUU7iac9TcEqpv2YePDE9IAzwhPGo/edit?usp=sharing
: 这个我记得就是用BST做的。
: 有一个bug，就是插入的时候给空指针 n = new Node(c),这么做了，被指出了，还是基
|
f********e
发帖数: 91 | 37 Good luck！ 肯定拿到onsite了！
【在 s********u 的大作中提到】
: 是个国人大哥，人很nice，不过下午很冷，穿了衣服还哆嗦。而且中间collabedit抽风
: 了几次，然后有些写的就没了，谁知道什么问题么？感觉很奇怪啊，就算断网也不该这
: 样吧。不过他说会给足时间。
: 题目好像以前见过，就是给一些不重叠的interval，然后设计一个数据结构来存储，实
: 现插入interval和find一个value两个函数，前者碰到重叠就return false，后者碰到
: 所在的interval返回。
: 分享题目和答案：https://docs.google.com/document/d/
: 1fXfv0GDKc6Uu03ZUU7iac9TcEqpv2YePDE9IAzwhPGo/edit?usp=sharing
: 这个我记得就是用BST做的。
: 有一个bug，就是插入的时候给空指针 n = new Node(c),这么做了，被指出了，还是基
|
J****3
发帖数: 427 | 38 Bless 先
貌似link打不开了？ 这个应该就是你之前说过EPI上有最优解的那个题吧 |
i*******e
发帖数: 69 | |
c********p
发帖数: 1969 | |
|
|
c********e
发帖数: 186 | |
s********u
发帖数: 1109 | 42 我看了下interval tree，有点这么个意思，只不过interval tree是可以overlap，而
且一般是要搜interval。
还有就是interval tree每个节点都会维护一个max field。
【在 w**t 的大作中提到】
: 这个是interval tree special case 吗？
|
b*****c
发帖数: 1103 | 43 segment tree就行了，就是线段树。
n个插入最多有2n个点，这个树最大是6n个点吗 |
b*****c
发帖数: 1103 | 44 online算法就不能线段树。
直接上stl::map 直接就是排序的。
代码晚点写。 |
b*****c
发帖数: 1103 | 45 c++ stl就是万能啊，再加上hashmap就无敌了 |
n****e
发帖数: 678 | 46 没有看懂这句：
“有一个bug，就是插入的时候给空指针 n = new Node(c),这么做了，被指出了，还是基
础不扎实啊，可能以前都是链表或者用递归做的，就从来没发现这个问题。应该说明下
还可以用递归做的。”
能详细说说吗？
【在 s********u 的大作中提到】
: 是个国人大哥，人很nice，不过下午很冷，穿了衣服还哆嗦。而且中间collabedit抽风
: 了几次，然后有些写的就没了，谁知道什么问题么？感觉很奇怪啊，就算断网也不该这
: 样吧。不过他说会给足时间。
: 题目好像以前见过，就是给一些不重叠的interval，然后设计一个数据结构来存储，实
: 现插入interval和find一个value两个函数，前者碰到重叠就return false，后者碰到
: 所在的interval返回。
: 分享题目和答案：https://docs.google.com/document/d/
: 1fXfv0GDKc6Uu03ZUU7iac9TcEqpv2YePDE9IAzwhPGo/edit?usp=sharing
: 这个我记得就是用BST做的。
: 有一个bug，就是插入的时候给空指针 n = new Node(c),这么做了，被指出了，还是基
|
x*****a
发帖数: 9 | 47 segment tree 是static structure, 在不知道整个区间的情况下, 你没办法做
这个interval tree就可以了, 不考虑旋转
【在 b*****c 的大作中提到】
: segment tree就行了，就是线段树。
: n个插入最多有2n个点，这个树最大是6n个点吗
|
l****o
发帖数: 315 | 48 用ArrayList， 插入时二分查找logN, insertion average O(1), worst O(n). Find
也用二分LogN. |
i***u
发帖数: 89 | 49 用BitSet 每个bit表示一个数 然后每次直接与
【在 s********u 的大作中提到】
: 是个国人大哥，人很nice，不过下午很冷，穿了衣服还哆嗦。而且中间collabedit抽风
: 了几次，然后有些写的就没了，谁知道什么问题么？感觉很奇怪啊，就算断网也不该这
: 样吧。不过他说会给足时间。
: 题目好像以前见过，就是给一些不重叠的interval，然后设计一个数据结构来存储，实
: 现插入interval和find一个value两个函数，前者碰到重叠就return false，后者碰到
: 所在的interval返回。
: 分享题目和答案：https://docs.google.com/document/d/
: 1fXfv0GDKc6Uu03ZUU7iac9TcEqpv2YePDE9IAzwhPGo/edit?usp=sharing
: 这个我记得就是用BST做的。
: 有一个bug，就是插入的时候给空指针 n = new Node(c),这么做了，被指出了，还是基
|
f******n
发帖数: 279 | |
