二进制搜索 - 有人可以清除这个面试算法吗？

Question

我最近接受了一次面试，面试官给了我以下场景，并问我我将使用什么数据结构来实现它：

您有 100 个弹珠，每个弹珠都是红色、蓝色或绿色。弹珠被扔进一个袋子里，你需要有一些机制来取回随机颜色的弹珠（有替换）。

好的，很简单。问了一些关于约束的问题后，我告诉他我会使用一个简单的数组，其中每个桶代表一个弹珠。可以使用随机数函数对数组进行索引，从而生成随机彩色弹珠。

那个解决方案很好，但后来他问 "what if you have many different colors, each with <= 1,000,000,000 marbles?" 最初我建议使用散列 table，其中每个键代表一种颜色，每个值代表该颜色的弹珠数量。面试官告诉我这是对 space 约束的一个很好的修复，但现在产生 n 种颜色之一的概率是 1/n，而不是大理石总数给出的实际概率。我需要一些方法来保持概率相同而不将它们全部存储在内存中。结果我什么都没想，他给我的解决办法是这样的：

找出每种颜色的总数（这将是 O(n)，这对于设置来说很好）并设置一个数组，其中每个桶代表每种颜色的累积总数。例如，如果您的弹珠总数为 R：3，B：5，G：1,000,000,000，则数组看起来像 [3] [8] [1,000,000,008]。然后他说你现在可以使用带有随机索引的二分搜索来获得随机颜色的大理石，同时仍然保持正确的概率。谁能向我解释为什么会这样？这只是一个修改后的二进制搜索，returns 第一个值高于你的随机索引？

Answer 1

如果您有一个介于 1 和 N 之间的随机索引来选择大理石颜色，则获得特定颜色的概率为 k / N，其中 k 是分配给该颜色的数字的数量。你的面试官只是把颜色按顺序排列，这样每种颜色都有正确的编号 k 分配给它的索引（其中 k 是该颜色的原始弹珠的数量），然后注意到给定一个介于 1 和 N 之间的随机索引，你可以使用二进制搜索来查找随机索引所在的颜色范围。假设 1 和 N 之间的随机索引是均匀随机的，这将为您提供正确的概率 k / N 当有 k 个具有该颜色的弹珠时获得该颜色。

Answer 2

诀窍在于您查看二分搜索结束的索引而不是该位置的值。我还不知道这个算法。谢谢你的描述。我在 python 中为您实现了它 :)

import random
import bisect

# 10 red, 20 blue, 70 green
counts = [10, 20, 70]
sums   = [10, 30, 100]

# count how often some color occurs to verify later that the algorithm works correctly
bins = [0, 0, 0]
# randomly select 10000 colors
for _ in range(100000):
    random_index = random.randint(0, sums[-1]) # sums[-1] is the last value in array (100)
    # do binary search in sums array
    result = bisect.bisect_left(sums, random_index)
    bins[result] += 1

print(bins) # example output: [10875, 19732, 69393]

二进制搜索 - 有人可以清除这个面试算法吗？

Binary search - Can someone clear up this interview algorithm?

arrays

algorithm

binary-search