问一道阿里的面试题如何求解

[dazhangpan]

N 年前面试阿里的时候有一道算法题不会做，后来一直念念不忘，在网络搜了一下也没找到答案，至今仍然没想出来...

题目是给一个方法 foo()，能以各 50%的概率随机返回 0 或者 1。问题是基于 foo()方法，实现一个 boo()方法，该方法能以各 10%的概率返回[0-9]中的一个数字。

感觉对受过相关训练的同仁来说应该不难，无奈本人对算法不是太在行 o(╥﹏╥)o

[ifzzzh]

@buxudashi #40 你相当于把 0 到 2^11-1 的范围分成了[0,2^0), [2^0,2^1), ..., [2^10,2^11)，明显有问题啊

[buxudashi]

@ifzzzh 当然要分了。而且是 10 个位置机会均等。
明显这是最优的。而不是明显有问题。

[ifzzzh]

@buxudashi #42 问题你这 10 个位置不均等啊。。。最高位一半的概率为 1，取 9 的概率=50%

[buxudashi]

@ifzzzh 机会均等。
第 9 位，第 8 位，第 K 位，跟第 0 位，都是均等占有最高位。所以 要先右移 1 位，再跟 0 判断。
第 t 位只有 0 和 1 这两个数字。你仔细思考下。我说最高位 1 是方便你理解。其实最高位是 1 或 0 两个占位。你想好判断条件。这东西在 c 语言里玩的多。

[wangyzj]

random.randint(0,1)
random.randint(0,9)
这样不行吗？

[ifzzzh]

@buxudashi #44 你不就说这个十位二进制数最高位是第几位就取几吗，问题是第 9 位为 1 的概率=1/2，第 8 位为 1 的概率=1/4。。。。2 楼就是标准的拉斯维加斯算法，你换各种表达方式要不结果是错的，要不跟 2 楼的没区别

[ixx]

取 9 次，返回 1 的个数

[ifzzzh]

@ifzzzh #46 更正：第 8 位为最高位且为 1 的概率=1/4

[buxudashi]

@ifzzzh 第 8 位是从 foo 取出来的，0 和 1 均等，怎么在你这变成 1/4 了

[stevesun21]

foo 方法就是一饿 bit 的产生器
0 ～ 9 的 bits 是 0000 ～ 1001
百分之十其实就是
0 = 0000
1 = 0001
2 = 0010
3 = 0011
4 = 0100
...
9 = 1001

那么接发就简单了因为是要求实现一个固定的 10%比例那么伪代码如下

1. 初始化一个记录器，记录 0 ～ 9
2. 调用四次 foo 得到 0 和 1 的一个 4 为 bits
3. 转化为一个 Integer
4. mod 这个 Integer 和 9
5. 然后看看这个 mod 后的结果是否在记录器中
6. 如果在，则从记录器中删除并返回，
7. 如果发现操作之后记录器中无数了，那么从新用第一步初始化记录器
8. 如果第 6 步的结果不再记录器中，那么从第 2 步再来一遍。

[ifzzzh]

@buxudashi #49 要想第 8 位是最高位第 9 位不得是 0 吗，上面 48 楼怕你没看懂更正过了

[hikarugo]

@ixx 瞎扯。。。

[GjriFeu]

我看见了不公

[hicdn]

@ixx 结果是正态分布
10 万次结果

{0: 182,
1: 1824,
2: 6997,
3: 16299,
4: 24808,
5: 24418,
6: 16446,
7: 7166,
8: 1668,
9: 192}

{0: 189,
1: 1737,
2: 6906,
3: 16301,
4: 24588,
5: 24732,
6: 16463,
7: 7095,
8: 1780,
9: 209}

{0: 188,
1: 1815,
2: 7083,
3: 16476,
4: 24716,
5: 24353,
6: 16213,
7: 7140,
8: 1836,
9: 180}

[hicdn]

@gaobing
@myd
1 楼和 2 楼方法，10 万次结果，分布是均等的。
{0: 9996,
1: 9950,
2: 10009,
3: 9875,
4: 9910,
5: 10112,
6: 9984,
7: 10075,
8: 10130,
9: 9959}

{0: 9955,
1: 9974,
2: 10037,
3: 10000,
4: 9928,
5: 9899,
6: 9950,
7: 10024,
8: 10002,
9: 10231}

{0: 9922,
1: 9949,
2: 10072,
3: 9922,
4: 10088,
5: 9917,
6: 9962,
7: 10206,
8: 10171,
9: 9791}

[Windsooon]

我整理了一下我的思路，欢迎大家讨论 https://v2ex.com/t/645301#reply0

[hitmanx]

@buxudashi 你这个 K 越大，概率越小，不是均匀分布的。因为 k 要求前面 k-1 个数都是 0， 且自身是 1，即 1/2^k

[wulin]

https://gist.github.com/wulinlw/b7f37207218b2973c0ba01e3f577629a
会多次递归...

[ixx]

@hicdn #54 手动点赞，发完就想到问题了，50%的概率，都是 0 和都是 1 的概率应该远远低于 4、5、6 的概率所以不满足 10%的要求

[wulin]

@wulin 太辣鸡了，10W 次测试要触发递归 6W 次
@Windsooon 正解