谁还记得这道面试题吗？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

谁还记得这道面试题吗？

谁还记得这道面试题吗？# JobHunting - 待字闺中

M*n2012-10-29 07:10

1 楼

板上兄弟贴出来过，大概是这样的，
用一个随机数generateor产生另一个随机数，基本思想是reject sampling，但reject
的概率太大，要找更有效的方法。

e*s2012-10-29 07:10

2 楼

把能accept的数放到一个数组里面，random这个数组的index。

M*n2012-10-29 07:10

3 楼

有链接吗？就是前几天的帖子。

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

: 把能accept的数放到一个数组里面，random这个数组的index。

e*s2012-10-29 07:10

4 楼

忘了，但是我自己reword了一下写到笔记里了
Given Rand(int n), return a random number from 0 ~ n
Now design a Rand(int n, int[] except) which output number should not in
except array

C*U2012-10-29 07:10

5 楼

假设except有k个数
那么就是把0~n - except影射到0~(n-k)
中间只要用到binary search 所以应该时间上还算可以把？

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

: 忘了，但是我自己reword了一下写到笔记里了
: Given Rand(int n), return a random number from 0 ~ n
: Now design a Rand(int n, int[] except) which output number should not in
: except array

M*n2012-10-29 07:10

6 楼

对，就是这个，问题是except太大了怎么办？比如n是1000，excep里面有980个数。

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

e*s2012-10-29 07:10

7 楼

我不是很懂你的方法，binary search用在哪里？
我的方法是，
Sort except array O(nlogn)
create new 0 ~ (n-k) array O(n)
Get random number in new array O(1)
整个算法 O(nlogn)

【在 C***U 的大作中提到】

: 假设except有k个数
: 那么就是把0~n - except影射到0~(n-k)
: 中间只要用到binary search 所以应该时间上还算可以把？

h*n2012-10-29 07:10

8 楼

how can you get random number from the new created array with size n-k given
the n size random generator?
I don't think n mod n-k will give you uniform distribution.

我不是很懂你的方法，binary search用在哪里？我的方法是，Sort except array O(
nlogn)create new 0 ~ (n-k) array O........
★ Sent from iPhone App: iReader Mitbbs Lite 7.56

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

: 我不是很懂你的方法，binary search用在哪里？
: 我的方法是，
: Sort except array O(nlogn)
: create new 0 ~ (n-k) array O(n)
: Get random number in new array O(1)
: 整个算法 O(nlogn)

e*s2012-10-29 07:10

9 楼

newArray[Rand（n-k)]

given

【在 h****n 的大作中提到】

: how can you get random number from the new created array with size n-k given
: the n size random generator?
: I don't think n mod n-k will give you uniform distribution.
:
: 我不是很懂你的方法，binary search用在哪里？我的方法是，Sort except array O(
: nlogn)create new 0 ~ (n-k) array O........
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.56

h*n2012-10-29 07:10

10 楼

you are not given the rand(n-k) that is my question . Rand(n)mod n-k will
not work since the resulted distribution is not uniform

newArray[Rand（n-k)]
★ Sent from iPhone App: iReader Mitbbs Lite 7.56

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

: newArray[Rand（n-k)]
:
: given

e*s2012-10-29 07:10

11 楼

他给Rand(n)，n 不是应该随你输入什么吗？不是规定了一定要input的那个n啊！

【在 h****n 的大作中提到】

: you are not given the rand(n-k) that is my question . Rand(n)mod n-k will
: not work since the resulted distribution is not uniform
:
: newArray[Rand（n-k)]
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.56

h*n2012-10-29 07:10

12 楼

酱紫。。。Got it，不过你这方法需要额外空间啊
如果要求不使用额外空间怎么搞

h*n2012-10-29 07:10

13 楼

先选range再在range里面选。

reject

【在 M*********n 的大作中提到】

: 板上兄弟贴出来过，大概是这样的，
: 用一个随机数generateor产生另一个随机数，基本思想是reject sampling，但reject
: 的概率太大，要找更有效的方法。