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

[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]那么概率是一样的。