问一道微软面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一道微软面试题

问一道微软面试题# JobHunting - 待字闺中

r*92011-09-20 07:09

1 楼

测试一个产生随机数的函数
该随机函数可能会出现这样的结果
a1 a2 ... an a1 a2 ...
其中n可能为数十百万级别
请问如何测试出这种情况？

f*t2011-09-20 07:09

2 楼

数十百万级别大概是几十几百M空间，能存在内存里
用个list存结果好了，如果不等于第一个值就加在后边，如果函数值与第一个相等就依
次往后比

p*22011-09-20 07:09

3 楼

一段一段的去hash。

s*12011-09-20 07:09

4 楼

没看明白题目什么意思，ms提供了一个函数叫你测试？为什么随机数会在an以后重复？

【在 r********9 的大作中提到】

: 测试一个产生随机数的函数
: 该随机函数可能会出现这样的结果
: a1 a2 ... an a1 a2 ...
: 其中n可能为数十百万级别
: 请问如何测试出这种情况？

p*22011-09-20 07:09

5 楼

说明这个RNG有问题呀。

【在 s*******1 的大作中提到】

: 没看明白题目什么意思，ms提供了一个函数叫你测试？为什么随机数会在an以后重复？

e*l2011-09-20 07:09

6 楼

所有的RNG都是伪随机，如果下一个随机数只依赖于上一个的话，一个重复的就会导致
后面的都重复，所以我猜检查到一个重复的就行了？

r*92011-09-20 07:09

7 楼

这个恐怕不行吧，你如何保证取到的两个段是位置对齐的？

【在 p*****2 的大作中提到】

: 一段一段的去hash。

W*22011-09-20 07:09

8 楼

这个是让你测随机数产生器的周期么？

s*c2011-09-20 07:09

9 楼

没看懂题目的意思。。。。。。。。

p*22011-09-20 07:09

10 楼

可以。
每次碰到a1的时候比hash，如果一样就一直比下去。不一样就继续hash。

【在 r********9 的大作中提到】

: 这个恐怕不行吧，你如何保证取到的两个段是位置对齐的？

p*22011-09-20 07:09

11 楼

不行。
RNG依赖于seed。

【在 e***l 的大作中提到】

: 所有的RNG都是伪随机，如果下一个随机数只依赖于上一个的话，一个重复的就会导致
: 后面的都重复，所以我猜检查到一个重复的就行了？

s*f2011-09-20 07:09

12 楼

static const int MAX_LEN = 10000000;//max size, if we cannot find
deplication within MAX_LEN, the random function is good.
//return where it begin duplicate
int TestRandomFun(int (*f)()){
static const int INIT_LEN = 100000;
static const int SUBARR_LEN = 10; //find 10-len substr first then
keep comparing,
static const int DUP_THRESHHOD = 1000; //if it keep equalling to
1000, we say then random function produce duplications.
vector v(INIT_LEN);
int c = 0;
while (v.size() < MAX_LEN){
for (int i = 0; i < INIT_LEN; ++i){
v.push_back((*f)());
}
vector::iterator search_start;
if (0 == c){
search_start = v.begin() + SUBARR_LEN;
}else{
search_start = v.begin() + INIT_LEN * c -
SUBARR_LEN;
}
++c;
vector::iterator it = search(search_start, v.end(),
v.begin(), v.begin() + SUBARR_LEN);
while (it != v.end()){
vector::iterator jt = v.begin() + SUBARR_LEN;
vector::iterator kt = it + SUBARR_LEN;
if (v.end() - kt < DUP_THRESHHOD){
for (int i = 0; i < DUP_THRESHHOD; ++i){
v.push_back((*f)());
}
}
int count = 0;
while (jt != it && kt != v.end()){
if (*jt != *kt){
break;
}
++jt;
++kt;
if (++count >= DUP_THRESHHOD){
return (it - v.begin());
}
}
if (jt == it){
return (it - v.begin());
}
it = search(it + 1, v.end(), v.begin(), v.begin() +
SUBARR_LEN);
}
}
return 0;
}