请教一道有关随机函数的面试问题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教一道有关随机函数的面试问题

请教一道有关随机函数的面试问题# JobHunting - 待字闺中

g*s2013-05-26 07:05

1 楼

(1) Write a program that would randomly populate the area of a square, with
even distribution.
(2) Then change the program to populate a circle within that square,
主要是这个2D even distribution怎么理解呢？就是相当于分成很多小正方形么？

z*32013-05-26 07:05

2 楼

像素点啊

z*32013-05-26 07:05

3 楼

这题跟其他random题一样，需要给一个随机函数
否则必死，你要能写出伪随机函数，那就是图灵奖的水平
然后就是x和y坐标
第一题好办
第二题是考点
计算所得到的x和y离圆心的距离
大于半径的抛掉重算
这样就可以保证平均分布了
cs的统计题考来考去就考丢掉重算
很简单粗暴的说

d*e2013-05-26 07:05

4 楼

第二题不需要扔掉重算，使用极坐标，用0到360的均匀分布来生称角度。
半径先用0到1的均匀分布生成，但是需要额外开个方就搞定了。
用暴力来做只能说明这个candidate没什么统计的sense。

【在 z*******3 的大作中提到】

: 这题跟其他random题一样，需要给一个随机函数
: 否则必死，你要能写出伪随机函数，那就是图灵奖的水平
: 然后就是x和y坐标
: 第一题好办
: 第二题是考点
: 计算所得到的x和y离圆心的距离
: 大于半径的抛掉重算
: 这样就可以保证平均分布了
: cs的统计题考来考去就考丢掉重算
: 很简单粗暴的说

z*32013-05-26 07:05

5 楼

用极坐标代码写起来太麻烦
这个需要编程的sense

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

: 第二题不需要扔掉重算，使用极坐标，用0到360的均匀分布来生称角度。
: 半径先用0到1的均匀分布生成，但是需要额外开个方就搞定了。
: 用暴力来做只能说明这个candidate没什么统计的sense。

d*e2013-05-26 07:05

6 楼

极坐标变化有毛难写的，多一步sin和cos变换就搞定了。
说你不知道怎么做得了，屁编程sense。
连点基本的概率都玩不明白，还敢号称学CS的？

【在 z*******3 的大作中提到】

: 用极坐标代码写起来太麻烦
: 这个需要编程的sense

l*82013-05-26 07:05

7 楼

极坐标+半径开方是正解！

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

P*t2013-05-26 07:05

8 楼

极坐标不一定能够做到均匀分布，相对于像素点。
去除法并不增加算法复杂度。

f*w2013-05-26 07:05

9 楼

极坐标，角度均匀分布，半径均匀分布开方，肯定是在圆内均匀分布啊，什么叫不一定？

【在 P***t 的大作中提到】

: 极坐标不一定能够做到均匀分布，相对于像素点。
: 去除法并不增加算法复杂度。

P*t2013-05-26 07:05

10 楼

你给个具体的计算公式，然后不用RANDOM数，就直接 Go through 0-360度，半径0->R
，试试看有没有重复GENERATE的点。
当然这道题也要看出题人到底想要什么样的结果。
另外从计算的角度看，SIN/COS 效率多半没有直接平方高。所以总的复杂度差不多。

定？

【在 f*******w 的大作中提到】

:
: 极坐标，角度均匀分布，半径均匀分布开方，肯定是在圆内均匀分布啊，什么叫不一定？

l*82013-05-26 07:05

11 楼

what is "重复GENERATE的点"?
you'll never generate identical points. there are infinitely many points in
a circle.

R

【在 P***t 的大作中提到】

: 你给个具体的计算公式，然后不用RANDOM数，就直接 Go through 0-360度，半径0->R
: ，试试看有没有重复GENERATE的点。
: 当然这道题也要看出题人到底想要什么样的结果。
: 另外从计算的角度看，SIN/COS 效率多半没有直接平方高。所以总的复杂度差不多。
:
: 定？

P*t2013-05-26 07:05

12 楼

I said it depends on what the interviewer wants. If he wants to fill a
square/circle, it's mostly some pixel grids in Computer Science. This is a
CS interview, not a math interview, right?

in

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

: what is "重复GENERATE的点"?
: you'll never generate identical points. there are infinitely many points in
: a circle.
:
: R