我正在为即将到来的面试学习并且遇到过几次这个问题(逐字记录)
Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M >> N and N large enough to span multiple disks. Algorithm to beat O(log n); bonus points for constant time algorithm.
首先，我不确定这是否是一个具有真正解决方案的问题。我和我的同事们已经对这个问题思考了几个星期，但它似乎不合时宜(当然，我们想不出解决方案并不意味着没有解决方案)。我会问面试官的几个问题是:
- 排序后的列表是否有重复？
- 盘数和N有什么关系？
我考虑过的一种方法是对每个磁盘的最小值/最大值进行二进制搜索，以确定应该保存该数字的磁盘(如果存在)，然后对磁盘本身进行二进制搜索。当然，如果磁盘数量很大并且您还有一个排序的磁盘列表，这只是一个数量级的加速。我认为这会产生某种 O(log log n) 时间。
至于M >> N的提示，也许如果你知道一个圆盘上有多少个数字和范围是多少，你可以在某些时候使用鸽巢原理来排除一些情况，但我不能找出一个数量级的改进。
此外，“恒定时间算法的奖励积分”让我有点怀疑。
关于此问题的任何想法、解决方案或相关历史记录？
最佳答案
由于问题没有说明数字以何种格式存储，您可以告诉面试官您将假设数字以物理方式存储。例如，每个数字都可以写在一张卡片上，而每张卡片都属于一个人。
N large enough to span multiple disks
现在，如果您想查找或确定某个号码不存在，您只需询问这些人您要查找的号码是否在他们持有的卡上。
如果 N 秒内没有人回答，则该号码不存在。这是假设每个人都能听到您的声音，并且每个人都知道他们的卡上有多少号码。
我不太了解物理(音速、空气摩擦、每个人的大脑看卡片的时间等)
关于algorithm - 在常数时间内找到排序列表中数字的存在？ (采访问题)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3054381/