我得到了这个面试问题,需要为它编写一个函数.我失败了.
因为这是一个电话采访问题,我不认为我应该编码的代码真的需要是完美的随机测试人员.
有任何想法吗？
在面试过程中如何在30分钟内编写一些合理的随机性测试代码？
编辑
这个问题的分布是均匀分布的
由于这是一个面试问题,我认为面试官希望以两种方式进行评估:
在某些情况下,这可能是一个非常好的面试问题,特别是如果面试官愿意在必要时提示候选人提出问题.
在理解问题的要求方面,如果您知道这是一个非常困难的问题,那么有助于见证pjs 答案中提到的Diehard测试.从根本上说,我认为候选人需要表现出两件事:
(a)数字的总体分布应该与期望的分布相匹配(我假设在这种情况下它是统一的,但正如@pjs在评论中指出的那样,这个假设应该是明确的).
(b)绘制的每个数字应独立于先前绘制的数字.
在电话采访中花半个小时编写代码,你不能走得太远.如果我回答这个问题,我会尝试建议:
(a)为了测试分布,为浮点数提出一组相等大小的二进制数,并计算落入每个二进制数的数字.绘制直方图和眼球(绘制数据总是一个好主意).为了扩展这个,你可以使用卡方检验,如amit的答案所述.
然而,由于在评论中讨论,并在这里
卡方检验的主要问题是间隔的数量和大小的选择.虽然经验法则可以帮助产生好的结果,但是对于各种应用来说都没有灵丹妙药.
为此,可以使用Kolmogorov-Smirnov检验.这个测试背后的想法是,如果你有序数据的图应该是一个很好的拟合完美的有序数据(称为累积分布).对于均匀分布,完美有序数据是一条直线:您希望数据的第10个百分位数是整个范围的10%,第20个百分比是整个范围的20%,依此类推.因此,通过编程方式,您可以对数据进行排序,将其与理想值进行对比,然后您应该得到一条直线.您还可以应用正式的定量统计测试,该测试基于实际值和理想值之间的差异.
(b)为了测试独立性,有多种方法.在不同时间滞后的自相关是一个相当明显的自相关:例如,在时间t的值与时间t + 1的值相似的程度.该游程检验是另一个很好的一个:你将所有的号码为1或0,这取决于它们是否属于高于或低于中位数,然后运行长度的分布可以用来构建一个统计检验.运行测试也可用于测试一个方向或另一个方向的运行,如此处和此处所述(这可能在您的情况下更有用).只要你有公式可以实现,这两个都有相当简单的实现!
除了死硬测试之外,其他讨论随机数生成器的好资源包括这里和这里.