Re: 暨南大学是个什么水平的大学啊? (转载)# Joke - 肚皮舞运动
s*u
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，但是无法动态插入和删
除）。似乎他还挺满意。
让我问问题之后就欢快的结束了。
了几次，然后有些写的就没了，谁知道什么问题么？感觉很奇怪啊，就算断网也不该这
样吧。不过他说会给足时间。
题目好像以前见过，就是给一些不重叠的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，但是无法动态插入和删
除）。似乎他还挺满意。
让我问问题之后就欢快的结束了。
