uber的一道电面题，求讨论

后边一个是个数而非尾数？

直接比是O(n)，排序是O(nlgn)

jiayi411 发表于 2017-10-31 10:14
直接比是O(n)，排序是O(nlgn)

恩 是啊 脑抽脑抽，感觉做array不排个序就不会了

为什么5就返回{3,6},{2,4}？

感觉是leetcode 刺破气球那道题改编

1.用hashmap 存。。。key是所有可能的number。。。value是list of interval。。。Pros: time complexity O(1)....Cons: space complexity (k*n) k is average size of one interval, n is number of intervals...

2.预先 根据start sort 存下来， 根据end sort 存下来。。。然后分别取start <= target, end>=target 在两个cache的list， 然后做interval。。。。time complexity 是O(lgn+k), k is potential output number...最坏情况下并没比直接搜要快。。。

请问一下楼主的timelne是怎样的

cx00001 发表于 2017-11-13 09:03
1.用hashmap 存。。。key是所有可能的number。。。value是list of interval。。。Pros: time complexity O( ...

正解

cx00001 发表于 2017-11-13 09:03
1.用hashmap 存。。。key是所有可能的number。。。value是list of interval。。。Pros: time complexity O( ...

正解

或者弄个interval tree? 感觉面试的时候要写出来也是挺难的