由于这是一个面试问题,我认为面试官会通过两种方式进行评估:
- 能够理解问题的真正要求是什么。
- 能够想到一些可以满足这些要求的代码。
在某些情况下,这可能是一个非常好的面试问题,特别是如果面试官愿意在必要时向候选人提出问题的话。
在理解问题的要求方面,如果您知道这是一个非常困难的问题,那么会有所帮助,见证顽固测试 http://en.wikipedia.org/wiki/Diehard_tests中提到的睡衣的答案 https://stackoverflow.com/a/22917301/834521。从根本上来说,我认为候选人需要表现出对两件事的欣赏:
(a)整体分配数字应该与所需的分布相匹配(我假设在这种情况下它是统一的,但正如 @pjs 在评论中指出的那样,这个假设应该明确)。
(b)每个抽出的号码应该是独立的从之前抽出的数字中。
在电话面试中花半个小时编写一些代码,你不可能走得太远。如果我回答这个问题,我会尝试提出以下建议:
(a)要测试分布,请为浮点数提供一组相同大小的箱,并计算落入每个箱的数字。绘制直方图并观察它(绘制数据总是一个好主意)。为了扩展这一点,您可以使用卡方检验,如中所述阿米特的回答 https://stackoverflow.com/a/22916643/834521.
然而,正如评论中所讨论的,并且here http://www.cs.indiana.edu/~kapadia/project2/node14.html
卡方检验的主要问题是区间数量和大小的选择。尽管经验法则可以帮助产生良好的结果,但并没有适用于所有类型应用的灵丹妙药。
为此,柯尔莫哥洛夫-斯米尔诺夫 http://en.wikipedia.org/wiki/Kolmogorov%E2%80%93Smirnov_test可以使用测试。这个测试背后的想法是,如果你绘制了ordered数据应该非常适合完美有序的数据(称为累积分布)。对于均匀分布,完美的有序数据是一条直线:您期望数据的第 10 个百分位数为该范围的 10%,第 20 个百分位数为该范围的 20%,依此类推。因此,以编程方式,您可以对数据进行排序,根据理想值绘制它,您应该得到一条直线。您还可以应用正式的定量统计测试,该测试基于实际值和理想值之间的差异。
(b)为了测试独立性,有多种方法。自相关 http://en.wikipedia.org/wiki/Autocorrelation在不同的时间滞后是一个相当明显的问题:当时的价值有多大?t与当时的值相似t+1, 例如。这运行测试 http://en.wikipedia.org/wiki/Wald%E2%80%93Wolfowitz_runs_test另一个不错的方法是:根据所有数字是否高于或低于中位数,将它们转换为 1 或 0,然后可以使用游程长度的分布来构建统计检验。游程测试还可用于测试一个方向或另一个方向的游程,如所述here http://www.cs.indiana.edu/~kapadia/project2/node17.html and here http://www.cs.indiana.edu/~kapadia/project2/node17.html(这对于您的情况可能更有用)。只要您手头有公式,这两种方法都有相当简单的实现!
除了顽固测试之外,讨论随机数生成器的其他好来源包括here http://www.cs.indiana.edu/~kapadia/project2/node12.html and here http://www.eg.bucknell.edu/~xmeng/Course/CS6337/Note/master/node42.html.