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

[dazhangpan]

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

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

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

[gaobing]

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

[myd]

楼上说的对。foo 方法其实相当于“抛硬币”。

连续抛四次硬币，所有的可能性一共有 16 种。如下：
```
'0000', '0001', '0010', '0011',
'0100', '0101', '0110', '0111',
'1000', '1001', '1010', '1011',
'1100', '1101', '1110', '1111'
```

bar()方法只需连续抛 4 次硬币，如果结果是上面 16 种可能中的前 10 种，就返回 0~9 对应的数字。如果结果是后 6 种，则抛弃结果并重新抛 4 次硬币。

[stackexplode]

想了一下
arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
用 foo()做二分查找

[keith1126]

@stackexplode #3

二分查找是不对的：如果 array 的长度为奇数，那么二分查找会导致左右两侧的不平衡。

[slgz]

马克

[stackexplode]

@keith1126
那就用[0-15]做二分。。

[keith1126]

@stackexplode #6

那你的做法其实就是#1 的做法了。#1 用二进制来表示数字，可能会比你的更加直观。

[zhaorunze]

@stackexplode 这跟二分没啥关系吧

[learnshare]

foo -> 0/1
boo -> 四位二进制转十进制

#1 #2 已经讲明白了

[stackexplode]

@zhaorunze 1 分钟想个解法而已，只要概率是对的，没有什么有没有关系的

[jixiangqd]

@gaobing 然而 感觉这种方式破坏了概率分布啊

[zhaorunze]

@stackexplode 问题是这解法没用到二分的思想啊，就是 9 楼说的进制转换

[zhaorunze]

@jixiangqd 十种之外的重新抛，十种之内的概率就一样了啊

[churchmice]

2 楼说的方法没毛病，这是好久之前的题目了，十年前找工作的时候我就看过

[jixiangqd]

@zhaorunze 对对对，我想通了

[stackexplode]

@zhaorunze 解决问题不一定要那么僵化的一定要用标准答案吧铁子，问题本质就是把 1/2 转换到 10%，二分绕了一圈，其实对 1-16 做二分恰好就是 0000-1111 的二分，确实不是完美答案，但也只是想的时候绕了一下而已
哪里有什么二分思想，二分思想就是概率思想

[haha370104]

要求有限步的话，其实知乎有一个类似于这个问题的讨论，做不到

不要求有限步的话 2 楼答案就对

[JerryCha]

1 楼的方法真是好
我净想条件概率去了

[zhaorunze]

@stackexplode 二分跟概率有啥关系，你说之前可以百度一下什么是二分查找。 这问题也不是概率转换的问题，1/2 怎么能转成百分之十？

[freakxx]

套路大概是这样, 先构建结果集，然后在结果集里面去构建。
[
[0, 1, 2, 3],
[4, 5, 6, 7],
[8, 9, x, x],
[x, x, x, x],
]

抽象看成 rand(x) --> rand(y)

2 - 4 - 16


rand(3) --> rand(10)
3 - 9 - 81
去掉[9][9]那么概率是一样的。

[ytmsdy]

@stackexplode 二分不对的，永远都无法得到 10%这个概率。

[yiqunz]

@gaobing 用 5 位来排列组合比 4 位平均调用频率小，
5 位的平均调用次数是 5/(30/32)≈5.33 ，4 位平均调用次数是 4/(10/16)=6.4 /doge

@zhaorunze @ytmsdy
foo()本身就是二分一种表现 #1 结果导向 #3 过程导向 其实一样的，
看他二分的取值区间和摒弃区间都是一样的
[0-9] 每个数都是 10%，不要应该关注 10%，而是 [0-9] 每个数概率均等，想要概率均等那么区间就要满足 2 的 n 次方
摒弃一部分数字不影响目标数字的概率均等问题，产生了浪费罢了，这是不是和二进制很像 /doge

[zhw2590582]

得到的经验就是，凡是看到 0 和 1 出现的题目，就要联想到二进制解法

[suiterchik]

背后的数学原理是舍弃采样（或者其他的蒙特卡洛方法也行），给你一个硬币，别说均匀分布，高斯分布都能给你采出来

[momocraft]

假想有一个区间从[0,1)开始

每掷一次 foo()为 0 则取左一半，为 1 则取右一半，直到这个区间已经是某个 [0.1*n, 0.1*(n+1)) 的子集时，返回 n

从计算的形状上看也是一种二分。

全用浮点数计算时一定在有限步内结束，在这一点来说比需要重掷的稳定，不过不是严格等概率

[shilyx]

function foo() {
return Math.random() < 0.5;
}

function foo2() {
for (;;) {
let n = 0;
for (let i = 0; i < 4; ++i) {
n *= 2;
if (foo()) {
n += 1;
}
}
if (n <= 9) {
return n;
}
}
}

!function foo2_test(times) {
let res = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ];

for (var i = 0; i < times; i++) {
res[foo2()] += 1;
}

for (let i = 0; i < res.length; ++i) {
console.log(times + "次调用中" + i + "的次数： " + res[i]);
}
} (10000);

[st2523684]

类似加权调度算法

[Mohanson]

硬币连续抛掷 32 次得到一个随机 u32 数字，然后取余 10 即可.

[wsssss]

//随机 return 0 到 3
foo0_3(){
return foo() + foo()*2;
}

//随机 return 0 到 15
foo0_15{
return foo0_3() + foo0_3()*4;
}

main(){
//随机给 a 赋值，范围是 0 到 15，超过 9，再重新给 a 赋值；
int a = foo0_15;
while( 9 < a ){
a = foo0_15;
}
return a;
}

[myd]

@Mohanson 这么说也能换成 u16 或 u8 ？

[wsssss]

//随机 return 0 到 3
foo0_3 () {
return foo() + foo() * 2;
}

//随机 return 0 到 15
foo0_15 () {
return foo0_3() + foo0_3() * 4;
}

main () {
//随机给 a 赋值，范围是 0 到 15，超过 9，再重新给 a 赋值；
int a = foo0_15;
while ( 9 < a ) {
a = foo0_15();
}
return a;
}

[lxy42]

leetcode 有一道类似的题目, 使用 rand7 实现 rand10: https://leetcode.com/problems/implement-rand10-using-rand7/

解决方法是拒绝-接受采样: https://en.wikipedia.org/wiki/Rejection_sampling

[Mohanson]

@myd u8 太小了，0-5 数字出现几率会比其他会多一点

[hitmanx]

@Mohanson u32 和 u8 的问题依然一样啊，只是更趋近于 10%而已，依然不是严格意义上的 10%

[mahone3297]

@gaobing
@myd
这种舍弃 6 种，不返回，重新计算 的做法，从数学上讲，是否符合概率？最后得出的，真是是 10% 么？

[wutiantong]

1 楼（&2 楼）的解法是正确且本质的，这里分享一些额外的思考：

1. 不可能存在一个有限步的解法（证明略）
2. 不一定要每组 4 次，也可以每组 5 次，每组 6 次，，，
3. 如果我们关注调用 foo() 方法的次数，那么每组 4 次的期望值是 6.4 次，而每组 5 次的期望值是 5.33333333 次
4. 每组 5 次的方案是调用 foo()方法次数（期望值）最少的方案

[buxudashi]

思考了一下，给个最优解吧。
有十个位置，每个位置被 0 或 1 占位。于是就有了 0000000000-1111111111 （即 0-9 共 10 个位置）得到一个数字 x
这个数字每右移 1 位，只要大于 0，接着右移，而右移的次数称为 k
这个 k 就是 0-9 中的一个数字。所以 foo( )随机取 10 次，这 10 次组成的 x 所取的 k，就是答案。
2 楼给的答案有个极端最差，就是无穷次运行 foo 都会在后面 6 个数字里，取不到数字的。

[epicnoob]

@buxudashi 明显不对，k=0 的概率是 1/1024

[buxudashi]

@epicnoob k 为 0，再右移，右移后 k+1 ；

这个 K 就是 x 最高位所在的位置。当位置在第 0 位时，经过上一次操作，k 变成 1.
答案是 k-1 呀，就是 0.
因为是右移，它就不是 1/1024，而是 1/10，因为一共才移 10 次

[buxudashi]

10 个位置，这题就变向的变成 了：
最高位为 1 为位置 t 的地方。t 为 0-9 中的某一个数字。求 t

[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 楼怕你没看懂更正过了

[fyxtc]

@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 正解

[willhunger]

Knuth 算法？

[loryyang]

上面楼太多了，不知道是否提到一个问题，这些方案从理论上都无法控制最差 case 下的时间。比如 16 中组合，拿 10 组，那么 6/16=37.5%的概率会重试，那么重试两次有 0.375^2，重试 10 次有 0.375^10 的概率，虽然很低，但是理论上依然存在。你无法控制这个最差 case。
另外我在想是不是做排列的时候，可以再多做一次，变成 32 种组合，选 30，那么有 2/30 的概率重试，重试概率大大降低了，虽然每次多计算一次 foo，但是相比较于重试的概率，应该不会亏
简单算一下（默认就算前两次），排列四次，期望 4*10/16 + 8*6/16 = 5.5， 排列五次：5 * 30/32 + 10 * 2/32 = 5.3。第二种期望的计算会少一些

[loryyang]

哦，我看到我的想法 @Windsooon 已经提到了，整理的还是挺完整的。我查了些资料，应该这就是最好的解了。看起来面试官也是准备了后手的，你提出 16 组合解之后，他应该会追问你：你觉得这个方案还有什么问题吗？

[soy]

算 4 次得到二进制数 x，(0<=x<16)
如果 x<10 返回 x
如果 10<=x<15 可以将(x-10)*2 再运算一个奇偶位返回
如果 x=15 重新计算
期望值
exp = 4*10/16 + 5*5/16 + (exp+5)*1/16
exp = 4.6

[ic2y]

@dazhangpan

可以换一个思路，我认为这个题目，考察的内容，非常接近 RC4 的流式加密算法，有个文章链接：
https://www.cnblogs.com/gambler/p/9075415.html

题目中给出的 foo()函数 [产生 0-1 随机数] ，我们可以用来初始化 流式加密的 init 映射状态。随后的 随机数产生，可以完全不依赖 foo()函数，完全依靠流式加密的方式，产生概率 10%的 [0-9]

==============Java 代码如下==================

package com.ic2y;

public class RandomNumber {
private static int MAPPING_LEN = 10;
//映射 0-9 的 关系
private int[] mapping = new int[MAPPING_LEN];
private int i = 0;
private int j = 0;
public RandomNumber(){
//初始化 mapping,再进行打乱
for(int i = 0;i < 10;++i){
mapping[i] = i;
}
//shuffle 算法，
for ( int i = MAPPING_LEN; i > 0; i-- ){
swap(getRandomLessTen(), i - 1);
}
}

private int getRandomLessTen(){
int val;
do {
val = doGetRandomLessTen();
if(val < 10){
return val;
}
}while (true);
}

private int doGetRandomLessTen(){
int val = 0;
for(int i = 0;i <4;++i){
val = val * 2 + foo();
}
return val;
}

//已知的产生 0 1 随机数的 函数
private int foo(){
return (int)System.currentTimeMillis() % 2;
}

//外界调用 boo 产生 0-9 随机数
public int boo(){
i = (i + 1) % MAPPING_LEN;
j = (j + mapping[i]) % MAPPING_LEN;
swap(i,j);
return mapping[(mapping[i] + mapping[j]) % MAPPING_LEN];
}

private void swap(int l,int r){
int tmp = mapping[l];
mapping[l] = mapping[r];
mapping[r] = tmp;
}


public static void main(String[] args){
RandomNumber r = new RandomNumber();
int testNumber = 100000;
int[] f = new int[10];
for(int i = 0;i < testNumber;++i){
++f[r.boo()];
}

float fTestNumber = (float)testNumber;
for(int i = 0; i < 10;++i){
System.out.println(String.format("Num:%d Probability:%.2f count:%d",i,f[i] / fTestNumber,f[i]));
}

}
}

=======结果=======

Num:0 Probability:0.10 count:9863
Num:1 Probability:0.10 count:10051
Num:2 Probability:0.10 count:10054
Num:3 Probability:0.10 count:10024
Num:4 Probability:0.10 count:10031
Num:5 Probability:0.10 count:9942
Num:6 Probability:0.10 count:10007
Num:7 Probability:0.10 count:9877
Num:8 Probability:0.10 count:10083
Num:9 Probability:0.10 count:10068

[wizardoz]

@learnshare 你这算法还没做到 10%的概率

[wizardoz]

@learnshare 好吧我错了，没细看 1#答案