问一道google的面经题

实现一个class，有两个function （1）insert an interval （2）che

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

分。
看坛子里有人说可以用bst 想问下是怎么实现的
多谢

先根据start 排序interval 然后找最右边的那个start 小于等于number 的interval 看他的end 是否大于等于number

补充内容 (2017-1-3 05:29):
发现自己看错了楼主的问题，移动设备害死人啊，我的理解就是BST就是一种便于Binary Search的数据结构，你把所有interval按照start建立一棵平衡的BST树，去这个树里检索基本等效于二分查找

楼主说的是可以的， interval插入以后要维护成不相交的 interval， 然后查询用二分.

WhatsFLAG 发表于 2017-1-3 04:26
先根据start 排序interval 然后找最右边的那个start 小于等于number 的interval 看他的end 是否大于等于num ...

如果是建BST的话， 我的想法是用treeset<start, interval>，但是在insert的时候，worse case也是O(n), 比如本来treeset里有这些interval：1 - 2，3 - 4， 5- 6， 6- 8,这时候我们要insert 1 - 10.我们还是要遍历treeset中的所有元素。那还不如不建bst，直接就把interval存成一个list。 不知道我的想法对不对

wsrrzxl 发表于 2017-1-3 05:42
如果是建BST的话， 我的想法是用treeset，但是在insert的时候，worse case也是O(n), 比如本来treeset里有 ...

我感觉如果希望通过BST给出比binary search O(n) add O(lgn) search更优化的解好像有点儿难？我只是把BST看做一个Binary Search的替代法，如果有什么办法能比Binary Search更快，那应该是从node里携带一些信息入手？然而目前为止并没有想到更好的办法……，你对BST能够达到的效率预期是多少啊？

WhatsFLAG 发表于 2017-1-3 06:11
我感觉如果希望通过BST给出比binary search O(n) add O(lgn) search更优化的解好像有点儿难？我只是把BST ...

我不确定add 能不能也log（n），我是觉得BST不能达到add也log（n）的话就还不如存成一个list

感觉应该使用 Interval search tree这个数据结构， http://www.geeksforgeeks.org/interval-tree/

如果用binary search tree的话，就是将interval的start，end存在Tree Map中吧，key 是start，建map的时候注意remove overlap，search的时候，可以直接利用map.floorKey(x) 找到可能的range，然后判断x是否在这个range当中。

这题也可以不用tree Map，直接将Interval存在list里面（sorted by start，and remove overlap)，查找的时候用 binary search 来做

两种方法的时间空间复杂度是完全一样的，第一步建map或list的time cost都是O(nlogn), 第二步search的time cost是O(logn); Java TreeMap 用的implementation是red-black binary search tree, 保证tree是balanced，不会出现worst case O(n）的情况。

用第一种方法的好处就是用到了现成的data structure
但是如果面试官有意考查Binary search 的implementation，应该会要求用第二种方法，然后手动实验binary search。

Self_Learner 发表于 2018-11-22 06:59
如果用binary search tree的话，就是将interval的start，end存在Tree Map中吧，key 是start，建map的时候注 ...

不用TreeMap的用list的话 add是O(n) 用TreeMap的话 add是log(n)