在一个固定时间的排序列表中是否存在数字(面试问题)

奇怪的是,问题是确定一个值的不存在,而不是存在。

这可能意味着它们指的是布卢姆过滤器( http://en.wikipedia.org/wiki/Bloom_filter ). Bloom过滤器可以告诉您元素是否:

• 不存在

因为这个问题没有说明数字是以哪种格式存储的,所以你可以告诉面试官,你将假设数字是以物理方式存储的。例如,每个号码可以写在一张卡片上,每张卡片由一个人拥有。

N大到足以跨越多个磁盘

如果没有人在N秒内回答,则数字不存在。这是假设每个人都能听到你,每个人都知道他们卡上的号码。

我对物理知之甚少(音速、空气摩擦、每个人大脑看卡片的时间等等)

如果只使用比较,我们有一个欧米茄(对数N)(最坏情况)下限(即O(1)是不可能的)。

假设你决定查看阵法中的某个位置,那么你的对手可以将元素放置在阵法中较大的部分。

因此,在每一步中,您至少有一半的元素需要考虑,所以在最坏的情况下是Omega(logn)。

因此,为了在最坏的情况下比O(logn)做得更好,您可能需要避免只使用比较。

正如其他答案所提到的,您可以进行概率常数时间搜索,以合理的概率给出正确的答案,例如使用Bloom过滤器。

根据问题的字母,他们可能正在寻找插值搜索,这是平均情况O(logn)。是的,在最坏的情况下这是O(n),但可以通过了解分布或使用插值二进制搜索来改进。

这将影响M>&燃气轮机;N提示。插值搜索的平均案例分析相当复杂,因此我甚至不会尝试在M>下进行修改&燃气轮机;N。但在M>&燃气轮机;N并且假设均匀分布,你可以假设这个值以初始搜索位置的+/-1为界,得到O(1)。

一个实际的实现可以做一次初始插值,如果搜索值没有边界,则返回到二进制搜索。

第一眼

M>&燃气轮机;我认为N不是一个提示,它只是不鼓励创建一个位图,如果有数字存在,它会在O(1)时间内直接告诉您。

我认为,一个合理的假设是N跨越多个硬盘是,你可以预期,你不会有命令magnitude更多的磁盘在您的处置。因为你需要2个 ^M O(1)性能的空间,如果N跨越多个磁盘,那么M跨越>&燃气轮机;多个磁盘和2个 ^M 跨度>&燃气轮机;磁盘不足。

此外,它还告诉您存储 数字将不会是有效的,因为从那时起,你将不得不存储X数字的地方

那就更糟了。

所以乍一看,似乎你可以证明,没有已知的更好的答案。

编辑: 我仍然站在上面的推理,这也是更好地证明了白痴的答案。然而结论是,从帕特里克的答案来看布鲁姆过滤器后,我相信面试官可能已经在看这个和其他概率算法(这应该在面试问题中注明)。

如果我们所能做的只是比较,那么正如上面的海报所指出的,我们不能做得比O(log(N))更好。

但是,如果我们对投入分配有更多的了解,我们可以做更多的事情。如果被面试官告知数字是连续的,那么O(1)解是可能的。第一个元素和我们正在寻找的元素之间的差异将给我们一个准确的位置,我们应该期望找到数字。

因为我们知道数字(M)的范围,所以我们可以执行插值二进制搜索。而不是将搜索范围平分1/2,而是将其平分N/(HI-LO)。结果仍然是O(logn),但常数较低。如果我们知道数据中没有重复项,那么这种技术效果更好,这个问题似乎暗示可能是这样,但它不是确定的。

例如,请参见以下博客: Faster than Binary Search

据我所知。在这个问题上,你可以利用两个提示。 1.数字已排序,2.N&M非常大(N>&燃气轮机;M) M跨越多个磁盘

不能

考虑到这一点,通过一系列假设,常数时间解是可能的:

• 数字是按顺序写的
• 所有磁盘的大小都相同,并且具有 准确的
• 你确切地知道有多少位可以写入磁盘

给出这些假设,只需将k乘以数字的位大小。查找该位置(O(1))+偏移量并读回正确的位数。

问题是不存在,所以不需要在磁盘中搜索。 我们可以检查数字X是否超出O(1)中所有磁盘的最小和最大范围。 (磁盘数量不变)

bool not_exists=true
for each disk_i in disks:
  not_exists &&= (X <min_element(disk_i)  || X > max_element(disk_i) )
return not_exists

否则,磁盘中的X可能是。

我认为如果你允许自己使用一些元数据,你可以得到更快的查找时间。

设置若干间接块或列表,其元素指向更多间接块/列表。重复上述步骤,直到达到所需的直接块/列表级别。其思想是使用类似于某些文件系统访问其文件数据的方式(直接、间接、双间接和三重间接块)。对于他们请求的数字范围,很可能需要三倍以上的间接寻址。

您正在查找的数字的每个部分都可以引用间接/直接表中的单独索引。最终,你将把搜索分解得足够详细,以至于你可以阅读最后一部分,其中可能包含也可能不包含数字。然后,您可以使用自己选择的算法搜索最后一个部分。

免责声明:我马上就要去吃午饭了,所以我还没有完全想清楚——这可能是不切实际的。

这很可能是一个措辞不当的问题。

如果布鲁姆过滤器是他们寻找的答案,这是最有可能的,没有必要混淆候选人与潜在的分布式/并行算法元素(多个磁盘)。

所以,是的 O(k)+1%*对数(n)。 O(k)检查布卢姆过滤器的恒定时间。

我不确定,这可以减少到常数时间摊销分析(不太精通那里)。

有一个方面还没有提到,那就是问题是没有具体的什么样的电脑,你正在使用。如果每个硬盘恰好连接到自己的CPU上,那么在固定时间内这样做就很简单了。

假设我有足够的机器来索引所有已排序的N个整数,每台机器只保存固定数量的K个文档,表示N个整数中的K个。

这样,对于任意给定的数字X,客户端查询服务器到达搜索节点的联网时间可以看作是常数时间;搜索节点查找表示数字X的文档的时间也是常数时间,因为每个搜索节点上的文档量是固定的数字K。

您可以通过检查保存数字的文件的大小来解决这个问题,然后创建一个大小大于文件大小的数字(不是abt int或lar)

我想问题清楚地表明你是 N ,例如

const int N = 15;
int xs[N] = {1, 3, 7, 9, 13, 16, 17, 19, 21, 24, 25, 26, 27, 28, 30};

单个查询 (少于 O(logN) )因此你不能真正做任何预处理。我相信在这种情况下,如果你能按摊销时间来计算,这个问题的措辞会有所不同。

N 实际上可能真的很大,所以即使是 M > N

所以,你真的不能比二进制搜索做得更好。但是,如您所知,元素的最大可能值 M (并且假设数据是均匀分布的),您可以猜测初始位置,从何处开始二进制搜索。

x / M * N ,在代码中可能是这样的:

double hint = static_cast<double>(x) / M; // between [0,1)
int m = static_cast<int>(hint * N); // guess the position in xs
// do binary search using m as initial "middle" point.

O(lgN)