【ms面试题】用不均匀的骰子掷出均匀的点数# JobHunting - 待字闺中
m*d
1 楼
怎么样用一个不均匀的筛子。比如 1/3 概率是1，1/3概率是2， 1/12 是3 ,1/12 是4.
1/12 是5,1/12 是6， 掷出均匀的点数。
问题 用这个筛子写一个ramdon函数， 返回的数字1-6 是均匀出现的 。
1/12 是5,1/12 是6， 掷出均匀的点数。
问题 用这个筛子写一个ramdon函数， 返回的数字1-6 是均匀出现的 。
r*y
2 楼
当投到1和2的时候，有1/4的概率选择，3/4的概率重投，如果是3-6，100%选择。这样
所有数字概率都一样。然后你需要一个东西能做1/4概率的，随便选三个1/12的数字加
起来就是了，所以整个过程是如果投到1和2，再投一次骰子，如果是3-5中的任意一个
就取之前的1或2，否则重投。
所有数字概率都一样。然后你需要一个东西能做1/4概率的，随便选三个1/12的数字加
起来就是了，所以整个过程是如果投到1和2，再投一次骰子，如果是3-5中的任意一个
就取之前的1或2，否则重投。
M*6
3 楼
1和2都是投出4个才打印出来是不是就可以了? 其他的摇到一个就打印一个。。
用一个arr1来保存各个数字投出几次才算投了1次。另一个array count来计数保存当前
各个数字已投出的个数。
比如 输入时 int p{1/3, 1/5, 1/5, 1/3, 1/5};
那么，int[] arr1 = {5, 3, 3, 5, 3}
int[] count = new int[arr1.length]
int num = rollDice();
count[num]++;
if(count[num] == arr1[num]){
count[num] = 0;
println(num);
}
或者自己实现一个概率函数决定当前摇出的数字要不要用。产生一个0到1之
间的随机数，如果它小与选中的概率就return true，否则就return false。
用一个arr1来保存各个数字投出几次才算投了1次。另一个array count来计数保存当前
各个数字已投出的个数。
比如 输入时 int p{1/3, 1/5, 1/5, 1/3, 1/5};
那么，int[] arr1 = {5, 3, 3, 5, 3}
int[] count = new int[arr1.length]
int num = rollDice();
count[num]++;
if(count[num] == arr1[num]){
count[num] = 0;
println(num);
}
或者自己实现一个概率函数决定当前摇出的数字要不要用。产生一个0到1之
间的随机数，如果它小与选中的概率就return true，否则就return false。
k*a
4 楼
第一次 3 or 4 ===> 3
5 or 6 ===> 5
1 then roll one more time: 1 or 3 or 4 ===> 1
2 or 5 or 6 ====> 4
2 then roll one more time: 1 or 3 or 4 ===> 2
2 or 5 or 6 ====> 6
5 or 6 ===> 5
1 then roll one more time: 1 or 3 or 4 ===> 1
2 or 5 or 6 ====> 4
2 then roll one more time: 1 or 3 or 4 ===> 2
2 or 5 or 6 ====> 6
m*d
5 楼
如果给的是一个参数呢？ 不是这个数字， 就是如果六面的概率分别是a1,a2,a3,a4,a5
,a6 那应该怎么处理？
【在 k*******a 的大作中提到】
: 第一次 3 or 4 ===> 3
: 5 or 6 ===> 5
: 1 then roll one more time: 1 or 3 or 4 ===> 1
: 2 or 5 or 6 ====> 4
: 2 then roll one more time: 1 or 3 or 4 ===> 2
: 2 or 5 or 6 ====> 6
,a6 那应该怎么处理？
【在 k*******a 的大作中提到】
: 第一次 3 or 4 ===> 3
: 5 or 6 ===> 5
: 1 then roll one more time: 1 or 3 or 4 ===> 1
: 2 or 5 or 6 ====> 4
: 2 then roll one more time: 1 or 3 or 4 ===> 2
: 2 or 5 or 6 ====> 6
g*2
6 楼
use permutations (permutations are uniformly distributed).
here you can use permutations of 3 unique numbers, which have 6 patterns.
just let each pattern to represent one number.
here you can use permutations of 3 unique numbers, which have 6 patterns.
just let each pattern to represent one number.
w*x
7 楼
想到一个方法不知道算不算耍赖。随机掷一个数，然后生成一个{0,1}^3的随机数，然
后拿点数去xor这个随机数。如果001到110就不重复以上过程，。那么现在问题就到了
一个生成PRG
上了，那样就有很多标准算法了。
后拿点数去xor这个随机数。如果001到110就不重复以上过程，。那么现在问题就到了
一个生成PRG
上了，那样就有很多标准算法了。
x*a
8 楼
还是二楼的答案最方便快速简洁易懂
e*s
9 楼
没那么复杂 投2次就投了
第一次3个uniform 1/3
第二次2个uniform 1/2
e.g.
第一次
{1, 2, {3 or 4 or 5 or 6} }
第二次
{ {1 or 3 or 4}, {2 or 5 or 6} }
【在 x*****a 的大作中提到】
: 还是二楼的答案最方便快速简洁易懂
第一次3个uniform 1/3
第二次2个uniform 1/2
e.g.
第一次
{1, 2, {3 or 4 or 5 or 6} }
第二次
{ {1 or 3 or 4}, {2 or 5 or 6} }
【在 x*****a 的大作中提到】
: 还是二楼的答案最方便快速简洁易懂
e*s
10 楼
具体怎么生成呢 持续投直到生成一个permutation?
worst case可能需要投掷接近无限次 比如一个面的概率接近0.
当然感觉可以只取其中概率较大的那几个面.
【在 g******2 的大作中提到】
: use permutations (permutations are uniformly distributed).
: here you can use permutations of 3 unique numbers, which have 6 patterns.
: just let each pattern to represent one number.
worst case可能需要投掷接近无限次 比如一个面的概率接近0.
当然感觉可以只取其中概率较大的那几个面.
【在 g******2 的大作中提到】
: use permutations (permutations are uniformly distributed).
: here you can use permutations of 3 unique numbers, which have 6 patterns.
: just let each pattern to represent one number.
g*d
11 楼
为什么 总概率 大于1
4.
【在 m**********d 的大作中提到】
: 怎么样用一个不均匀的筛子。比如 1/3 概率是1，1/3概率是2， 1/12 是3 ,1/12 是4.
: 1/12 是5,1/12 是6， 掷出均匀的点数。
: 问题 用这个筛子写一个ramdon函数， 返回的数字1-6 是均匀出现的 。
4.
【在 m**********d 的大作中提到】
: 怎么样用一个不均匀的筛子。比如 1/3 概率是1，1/3概率是2， 1/12 是3 ,1/12 是4.
: 1/12 是5,1/12 是6， 掷出均匀的点数。
: 问题 用这个筛子写一个ramdon函数， 返回的数字1-6 是均匀出现的 。
f*m
12 楼
投两次就可以
1, 1|3|4 => 1
1, 2|5|6 => 2
2, 1|3|4 => 3
2, 2|5|6 => 4
3|4, * => 5
5|6, * => 6
1, 1|3|4 => 1
1, 2|5|6 => 2
2, 1|3|4 => 3
2, 2|5|6 => 4
3|4, * => 5
5|6, * => 6
g*2
13 楼
One way is to use one fixed set, say 1,2,3 and then use all permutations of
it. Every time you roll the die 3 times, and discard any other patterns.
A better way is to use all sets (6 choose 3 -> 20). Then you can create a
map of permutation to number (1-6). Also discard any other patterns.
A more efficient way might be to create uniform 0,1 function first. Here you
can also use permutation: roll a die twice, 0 if first roll < second roll
and 1 if first roll > second roll. discard ties.
Then it's just a problem of generating random numbers from uniform {0,1}
function, which is very simple (binary number generating).
【在 e*******s 的大作中提到】
: 具体怎么生成呢 持续投直到生成一个permutation?
: worst case可能需要投掷接近无限次 比如一个面的概率接近0.
: 当然感觉可以只取其中概率较大的那几个面.
it. Every time you roll the die 3 times, and discard any other patterns.
A better way is to use all sets (6 choose 3 -> 20). Then you can create a
map of permutation to number (1-6). Also discard any other patterns.
A more efficient way might be to create uniform 0,1 function first. Here you
can also use permutation: roll a die twice, 0 if first roll < second roll
and 1 if first roll > second roll. discard ties.
Then it's just a problem of generating random numbers from uniform {0,1}
function, which is very simple (binary number generating).
【在 e*******s 的大作中提到】
: 具体怎么生成呢 持续投直到生成一个permutation?
: worst case可能需要投掷接近无限次 比如一个面的概率接近0.
: 当然感觉可以只取其中概率较大的那几个面.
相关阅读
现在还没offer如果grace period找到工作可以申请h1b么大家签了offer的还在继续投么？为啥版上几乎都是IT业的工作an intern offer and some other questions请问最近有没有人申请 export licience？amazon onsite 11:45才开始明天面MS onsite, 求祝福！background check是在什么时候？求助：拿到offer, 不能工作？？？ (转载)同学们 Opt approved 之后几天能收到卡呀？明天onsite，求祝福问个反悔offer的事情，大家表鄙视为什么拿不到面试机会请教纽约地区的工资水平请教个 interview question大家拿到的offer都给办绿卡吗？拿ME和MS有区别吗？同时多次file H1B transfer会不会有问题这个公司的电面怎么应付？H1B RFE 被拒的可能性大吗？