在恒定时间内查找排序列表中的数字是否存在？(面试问题)
我正在为即将到来的面试而学习,并且多次遇到过这个问题(逐字逐句)
在N个数字的排序列表中查找或确定数字不存在,其中数字的范围超过M,M >> N和N足够大以跨越多个磁盘.击败O(log n)的算法; 恒定时间算法的奖励积分.
首先,我不确定这是否是一个真正解决方案的问题.我和我的同事已经对这个问题进行了数周的思考,似乎形成了不良(当然,只是因为我们无法想到解决方案并不意味着没有解决方案).我问过面试官的一些问题是:
- 排序列表中是否有重复？
- 与磁盘数量和N的关系是什么？
我考虑的一种方法是二进制搜索每个磁盘的最小值/最大值,以确定应该保存该号码的磁盘(如果存在),然后在磁盘本身上进行二进制搜索.当然,如果磁盘数量很大并且您还有一个已排序的磁盘列表,这只是一个数量级的加速.我认为这会产生某种O(log log n)时间.
至于M >> N提示,也许如果你知道磁盘上有多少个数字以及范围是什么,你可以使用鸽子原则在某些时候排除某些情况,但我无法弄清楚数量级的改进.
此外,"恒定时间算法的奖励积分"让我有点怀疑.
有关此问题的任何想法,解决方案或相关历史记录？
Enr*_*que 26
由于问题没有说明数字存储的格式,您可以告诉采访者您将假设数字以物理方式存储.例如,每个号码可以写在卡上,每张卡由一个人拥有.
N足够大以跨越多个磁盘
现在,如果您想查找或确定不存在号码,您可以询问这些人您所查找的号码是否在他们持有的卡上.
如果没有人在N秒内回答,则数字不存在.这假设每个人都可以听到你,每个人都知道他们的卡上有多少号码.
我对物理学知之甚少(声速,空气摩擦,每个人大脑看卡片的时间等)
- 这需要O(n)工作 - 来自每个人的O(1). (2认同)
- @NickJohnson - 是的,但这是努力的复杂性.通过并行运行任务,时间复杂度已降低到O(1). (2认同)
Pat*_*ick 15
奇怪的是,问题是确定一个值的非存在性,而不是存在性.
这可能意味着它们引用了Bloom过滤器(http://en.wikipedia.org/wiki/Bloom_filter).Bloom过滤器可以告诉您元素是否:
- 不存在
- 或者可能存在
- 是不是构建了Bloom过滤器O(n)？ (3认同)
- 布隆过滤器是概率性的.此外,问题是"找到或确定不存在",所以它不仅仅是不存在.即使它只是不存在,也可能存在误报(即它不存在,但我们说它确实存在). (2认同)
小智 12
如果仅使用比较,我们有一个Omega(log N)(最差情况)下限(即O(1)是不可能的).
假设您决定查看数组中的某个位置,那么您的对手可以将该元素放置在更大的数组部分中.
因此,在每个步骤中,至少有一半的元素需要考虑,因此在最坏的情况下需要Omega(logn).
因此,在最坏的情况下,您可能需要远离仅使用比较以便比O(log N)做得更好.
正如其他一些答案所提到的那样,您可以进行概率恒定时间搜索,以合理的概率为您提供正确的答案,例如使用布隆过滤器.
通过问题的字母,他们可能正在寻找插值搜索,这是平均情况O(log log n).是的,在最坏的情况下这是O(n),但可以通过分布知识或使用插值二分搜索来改进.
这起到M >> N提示.插值搜索的平均情况分析非常复杂,所以我甚至不会尝试在M >> N下进行修改.但是概念上,在M >> N下并假设均匀分布,你可以假设该值将受限于初始搜索位置的+/- 1,产生O(1).
实际的实现可以进行一次初始插值,如果搜索值没有限制,则回退到二进制搜索.
不知道在这种方法中如何使用多个磁盘,但......