uber的一道电面题，求讨论

给一堆interval，比如{3,6},{2,4}，

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

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

只返回{2,4}

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...最坏情况下并没比直接搜要快。。。

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

复杂度什么要求。。？ 还是有比check 每个interval更快方法么。。

Corey_Lancer 发表于 2017-10-31 07:26
复杂度什么要求。。？ 还是有比check 每个interval更快方法么。。

预处理一下，应该是有机会到O(1)的吧，不然就遍历一下太简单了。。。

同求预处理方法，我遇到的是给一堆interval，再给一堆数，算每个interval包含了哪些数

interval排个序， 然后跟二分跟start比？

vae371 发表于 2017-10-31 07:30
预处理一下，应该是有机会到O(1)的吧，不然就遍历一下太简单了。。。

怎么做到O(1)？

请问 楼主是什么时候内推的？

segment tree?

ld_xixi 发表于 2017-10-31 08:25
interval排个序， 然后跟二分跟start比？

恩，但这个还不是最优解

vae371 发表于 2017-10-31 08:43
恩，但这个还不是最优解

求指教， 怎么招也得排一把序吧