LinkedIn 的一道onsite题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

LinkedIn 的一道onsite题

LinkedIn 的一道onsite题# JobHunting - 待字闺中

e*82016-01-04 08:01

1 楼

从网上看来的一道面经，不知道如何解最优，求大神指点。。。
给你一个java interface, 实现两个method，一个是void add interval(int from,
int to), 另一个是int getTotalLength()返回已有interval的总时间，当然，要考虑
overlapping。比如(1,5), (2, 6)的total length 是5.
不知道用什么样的data structure 去解决。

a*12016-01-04 08:01

2 楼

segment tree.

l*32016-01-04 08:01

3 楼

考虑如何向不交的interval集合里面插入一个新的interval。
leetcode上的题。

【在 e********8 的大作中提到】

: 从网上看来的一道面经，不知道如何解最优，求大神指点。。。
: 给你一个java interface, 实现两个method，一个是void add interval(int from,
: int to), 另一个是int getTotalLength()返回已有interval的总时间，当然，要考虑
: overlapping。比如(1,5), (2, 6)的total length 是5.
: 不知道用什么样的data structure 去解决。

e*82016-01-04 08:01

4 楼

这样的话，可能需要维护一个sorted interval array，以他们的开始时间排序。每次
插入，都得O(n) 时间复杂度，会不会效率不高？

【在 l*3 的大作中提到】

: 考虑如何向不交的interval集合里面插入一个新的interval。
: leetcode上的题。

e*82016-01-04 08:01

5 楼

能不能展开介绍下。。。谢谢！

【在 a******1 的大作中提到】

: segment tree.

c*m2016-01-04 08:01

6 楼

如果https://leetcode.com/problems/insert-interval/的最好方法是O(N)的，那我觉
得也不会有Ｏ(logn)的方法了吧。不认为这题能用segment tree做，可能我对segment
tree的用法还不够了解

【在 e********8 的大作中提到】

: 这样的话，可能需要维护一个sorted interval array，以他们的开始时间排序。每次
: 插入，都得O(n) 时间复杂度，会不会效率不高？

l*32016-01-04 08:01

7 楼

也不能简单理解为O(n)，你可以用BST来存储interval，这样如果是要新添入一个
interval，就是O(log n)，如果是要修改并合并之前k个interval，那确实需要 O(k
log n)的运算量，但是好处是做完你少了k个interval。我觉得总的来说，至少粗浅的
想，是不会有更好的数据结构了（up to log complexity），因为看上去至少你总是
要维护若干个不相交的interval的，
比如如果你当前的interval是[0,1], [2,3], [4,5], [6,7] 这种，那看上去只能分别
存了，没有什么好的方法可以节省时间和空间代价。

【在 e********8 的大作中提到】

: 这样的话，可能需要维护一个sorted interval array，以他们的开始时间排序。每次
: 插入，都得O(n) 时间复杂度，会不会效率不高？

l*32016-01-04 08:01

8 楼

我也不认为这种问题适合线段树来处理
线段树处理连续区间的问题比较好，区间断断续续的话感觉搞不动。

A*s2016-01-04 08:01

9 楼

如果存在的 interval 不能合并成一个，返回的 totalLength 该怎么定义呢？
比如已有 (1,5) (6,7)

【在 e********8 的大作中提到】

r*g2016-01-04 08:01

10 楼

我觉得这题就是Merge Intervals。两个办法，一个是bst维护独立的不同的interval，
每个node是一个interval，这个缺点是无法删除interval，因为interval已经被merge
在一起了，而且插入的code不好写，好处是，可以很快的获得TotalLength。另外一个
办法当然就是interval tree了，网上有详细方法，用最基本的interval tree就可以，
好处是，插入操作非常easy，坏处是，不同node之间其实可能会overlap，所以最后
merge的时候需要注意，merge的开销应该是O(N)吧。所以理论最快的是BST tree，但是
interval tree很容易写。
不知道segment tree怎么写。

r*g2016-01-04 08:01

11 楼

如果已经sorted了，binary search就可以获得新的interval应该插入的位置，所以这
题确实可能考察的就是leetcode insert interval原题。

【在 e********8 的大作中提到】

: 这样的话，可能需要维护一个sorted interval array，以他们的开始时间排序。每次
: 插入，都得O(n) 时间复杂度，会不会效率不高？

w*d2016-01-04 08:01

12 楼

merge时用lazy delete＋pointer会快很多，否则还是O(n)

【在 r*******g 的大作中提到】

: 如果已经sorted了，binary search就可以获得新的interval应该插入的位置，所以这
: 题确实可能考察的就是leetcode insert interval原题。

s*g2016-01-04 08:01

13 楼

用bst, 每个节点存interval［low, high］。所要维护的属性是树里的父节点的low要
大于左子节点的high，父节点的high要小于右子节点的low。每次插入新节点的时候比
较路径节点上的interval，并且更新插入节点的low／high值. 比如输入节点为［1,5
］, ［7,9］, ［6,13］, ［4,7］。
插入第一个节点时，树结构为［1，5］；
插入第二个节点时，树结构为
［1， 5］
［7，9］
插入第三个节点时，树结构为
［1， 5］
［7， 9］
［6， 7］［9， 13］
[6, 13]与［7，9］比较的时候会裂变成两个节点：［6， 7］，［9， 13］。
插入第四个节点时，树结构为
［1， 5］
［7， 9］
［6， 7］［9， 13］
［5， 6］
［4，7］与［1，5］比较的时候会变成［5，7］；［5，7］与［6，7］比较的时候会变
成［5，6］
每次插入复杂度为o(logN), 最后算总长度，遍历一次树就行，复杂度为o(N). 这个解
法有点类似于skyline的bst解法， http://www.shadabahmed.com/blog/2013/04/24/skyline-algorithm-a-binary-tree-approach/. 不同的是 skyline 的线段有不同的高度，这里的险段的高度默认为1.

r*g2016-01-04 08:01

14 楼

你这个方法好，每插入一个interval时候不需要merge node, 而是把interval本身分裂
成多段。
不过用bst的问题就是不能删除interval，还是只有interval tree才能删除interval。

5

【在 s********g 的大作中提到】

: 用bst, 每个节点存interval［low, high］。所要维护的属性是树里的父节点的low要
: 大于左子节点的high，父节点的high要小于右子节点的low。每次插入新节点的时候比
: 较路径节点上的interval，并且更新插入节点的low／high值. 比如输入节点为［1,5
: ］, ［7,9］, ［6,13］, ［4,7］。
: 插入第一个节点时，树结构为［1，5］；
: 插入第二个节点时，树结构为
: ［1， 5］
: ［7，9］
: 插入第三个节点时，树结构为
: ［1， 5］