我正在为即将到来的面试而学习,并且多次遇到过这个问题(逐字逐句)
在N个数字的排序列表中查找或确定数字不存在,其中数字的范围超过M,M >> N和N足够大以跨越多个磁盘.击败O(log n)的算法; 恒定时间算法的奖励积分.
首先,我不确定这是否是一个真正解决方案的问题.我和我的同事已经对这个问题进行了数周的思考,似乎形成了不良(当然,只是因为我们无法想到解决方案并不意味着没有解决方案).我问过面试官的一些问题是:
我考虑的一种方法是二进制搜索每个磁盘的最小值/最大值,以确定应该保存该号码的磁盘(如果存在),然后在磁盘本身上进行二进制搜索.当然,如果磁盘数量很大并且您还有一个已排序的磁盘列表,这只是一个数量级的加速.我认为这会产生某种O(log log n)时间.
至于M >> N提示,也许如果你知道磁盘上有多少个数字以及范围是什么,你可以使用鸽子原则在某些时候排除某些情况,但我无法弄清楚数量级的改进.
此外,"恒定时间算法的奖励积分"让我有点怀疑.
有关此问题的任何想法,解决方案或相关历史记录？
algorithm ×1