google电面最新挂经

lxxxxxxx 发表于 2016-10-27 00:24
没懂你说的什么意思？sum p = 1，所以需要的空间是n，这个n是不可避免的因为你要生成n个元素返回吧....然 ...

我知道你的意思，但这个题是要设计出一个按照给定的概率分布的随机生成器，所以在每次最终生成的数组中（单次实现）不一定某个值出现的次数/N就一定等于给定的概率，也就是说在单次实现中某个值的出现频率并不一定就是概率。例如 N=4, p=[0.5, 0.5], 满足条件的生成的数组不一定就是2个1和2个2的排序，因为随机数的仅仅一次实现并不一定（往往也不可能）就恰好等于概率，只是多次概率平均期望会收敛到概率。就好比是一个均匀硬币投掷10次，正面不一定就一定是5次（只是多次平均收敛到5次（大数定律））。
而且，若给 N = 2, p=[0.49999, 0.50001] (任意sum=1的double array)，就不可能某一次的实现频率恰好和概率相等了。若定义一个长度为100000的数组vector<int>a（包含49999个1和50001个2），那么a[rand()%100000]就是一个恰好为概率p=[0.49999, 0.50001]的二项分布，用这个生成器生成两个独立变量放到最终数组即可。但我的意思是这个方法（变整数倍）无法推广到任意分布p=[p1,..pm]. 时间空间无法控制，因为pi/pj的比值可以是任意有理数，这样用来做生成器的数组无法预料会有多大。

补充内容 (2016-10-27 02:53):
这又让我想到如何测试这个程序。就是要不断地增大N, 然后计算每个值出现的频率百分比的平均值，看是不是收敛到给定的p的。对于固定的N来说，这样计算的频率没有意义。

ymsf 发表于 2016-10-26 12:13
第一题可以使用最基本的产生一个(0, 1)区间均匀分布的随机数吗？如果可以的话很简单啊。

但是如果要从 ...

是的，C++中就用比值(double)rand()/RAND_MAX就可以生成一个[0, 1]均匀分布。我不熟悉Java，应该也有类似的。