阿里的随机数面试题思路分享

[Windsooon]

题目在这里：问一道阿里的面试题如何求解

我觉得这是个挺有趣的题目，回复里面讨论了几点方法，可惜大部分都有些缺陷或者需要调用多次 foo 函数。我想说下我的想法。在此之前，我们需要回顾一下二进制的基础，

无符号的二进制 4 位 可以表达 0000 到 1111 也就是十进制的 0 到 15
无符号的二进制 5 位 可以表达 00000 到 11111 也就是十进制的 0 到 31

回复中一开始 @gaobing 提出了：

那 0 或 1 拼数字 ，2 位的 数字 共 4 种排列，3 位的 8 种排列，4 位的 16 种排列 ， 拿出 10 种排列指代 [ 0 -9] 这几个数字，剩下的 6 种排列不返回，重新计算随机数，直到出现 另外 10 种情况。

这是正确的解法，其实 Python 就是这样实现的，（源码在这里），不过在这个问题里，我们可以发现这种解法的弊端在于，有 6/16 也就是超过三分之一的的情况下需要重新计算随机数，平均来说我们需要运行多少次 foo 函数才能得到结果呢？我们可以计算一下：有 10/16 的情况我们只需要运行 4 次 foo 函数，剩下的 6/10 的情况我们需要重新计算随机数，但是，重新计算随机数还是可能超过区间，要一直计算直到小于区间。我不会讨论计算的细节，不过我们可以计算出平均需要运行 6.4 次 foo 函数。（读者可以自行推导）

有没有更好的方法呢？试想一下 random 函数是怎么实现的，随机生成一个很大的数字，然后在我们需要的范围内取模，回复也有提到这类解法：

1. 我们可以首先生成一串 32 位 的二进制序列并转换成整数，既然 foo 函数的 0 和 1 是随机的，那么这个二进制序列也就随机代表了 0 - 2 的 32 次方减 1 里面所有整数的值，
2. 把整数对 10 取模即可。

这个算法问题在于，他需要多次调用 32 次 foo 函数，并且需要模运算，而且不是严格意义上的 10% 的概率（因为所有数字的出现并不能被 10 整除）。更好的方法是什么呢？我们结合两种方法，

1. 我们运行 5 次 foo 函数得到一个二进制序列并将其转成整数（十进制范围 0 - 31 ）
2. 如果这个整数是 30 或者 31 的话，我们重新计算随机数，如果在 0 到 29 之间的话，那么我们将其对 10 取模。

为什么是运行 5 次 呢，因为 5 位 二进制能表示 0 到 31，而 31 是最小的最接近能被 10 整除的数字。（ 0 到 29 这 30 个 数字刚好能被 10 整除）。同样可以计算出计算平均运行 foo 函数 5.33 次。时间复杂度为 O(5.33 * foo) 。欢迎大家留下自己的观点。

Python 代码如下

import random
import collections

def get_result():
    binary_lst = []
    for i in range(5):
        binary_lst.append(foo())
    binary_str = ''.join(binary_lst)
    return int(binary_str, 2)

def foo():
    return random.choice(['0', '1'])

def bar():
    res = get_result()
    while res == 30 or res == 31:
        res = get_result()
    return res % 10

count = collections.defaultdict(int)

for i in range(100000):
    count[bar()] += 1

print(count)

稍微详细的解法我发在了这里： https://zhuanlan.zhihu.com/p/107471257

[slgz]

马克一下

[wangfenjin]

你说的对

[xloger]

赞一个，这种优化思路很值得学习

[IntFloat]

可以一开始用个 foo() 把 10 个数字分成左右两组 这样就只用处理 5 个数据 3 位就行了 相当于 4 次多

[IntFloat]

忽略我这个还是 6 次多

[Melyn]

@IntFloat 在你的基础上可以在分组后使用 4 位来取模，因为 16 个结果中有 15 个可直接返回结果，最终调用 foo 的人平均次数为 5 + 4/15 ；而直接使用 5 位取模时，调用 foo 的平均次数为 5 + 5/15，因此是可以带来一些提升的

[IntFloat]

@Melyn 厉害 学习到了

[soy]

int cal() {
int ret = foo() + foo() * 2 + foo() * 4 + foo() * 8;
if (ret < 10) {
return ret;
}
if (ret < 15) {
return (ret - 10) * 2 + foo();
}
return cal();
}

这样期望是 4.6 次

[Melyn]

@soy 赞，我验证了一下 0-9 的最终概率和平均调用次数都是正确的

[Melyn]

1. 在值数量为 10，直接使用 m 位二进制数(2 的 m 次方不小于 10)模拟求解的条件下，平均调用 foo 的次数为 m+m*p/(1-p)，最优解 m=5，平均调用 5+1/3 次 foo ；
2. 使用“二分法”减小问题规模时，当数值总量为奇数时就不能继续再往下了，只能利用 1 中的思路直接求解了

[hicdn]

def foo():
return random.randint(0,1)

def bar32():
n = 0
for i in range(5):
n *= 2
n += foo()
if n > 29:
return bar32()
return n % 10

def bar32_2():
n = 0
for i in range(5):
n *= 2
n += foo()
if i == 3 and n == 15: # 1111 - > 1111x
return bar32_2()
return n % 10

可以再优化下，平均 foo 函数调用从 5.33 次下降到 5.27 次。

[Windsooon]

@soy 这个解法很聪明，让我想想在什么时候能应用在更一般的情况。

[aguesuka]

import random
from collections import Counter

foo_count = 0


def foo() -> int:
global foo_count
foo_count += 1
return random.choice([0, 1])


def bar(i):
return do_bar(i, 0, 1)


def do_bar(i: int, remaining: int, size: int) -> int:
size = size << 1
remaining = remaining << 1 | foo()

if size == i:
return remaining
elif size < i:
return do_bar(i, remaining, size)
size -= i
if remaining >= i:
remaining -= i
return do_bar(i, remaining, size)
else:
return remaining


random_count = 1000000
print(Counter([bar(10) for i in range(random_count)]))
print(foo_count / random_count)
"""
Counter({4: 100691, 8: 100638, 9: 100209, 6: 99923, 0: 99874, 3: 99838, 1: 99820, 7: 99745, 5: 99715, 2: 99547})
4.600133
"""

[lawmil]

插眼学习下