s*********e
发帖数: 17 | 1 给你一系列数N, 可能是无穷大
请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
如何做? |
t****t
发帖数: 6806 | 2 数学,数学
【在 s*********e 的大作中提到】
: 给你一系列数N, 可能是无穷大
: 请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
: 如何做?
|
c***d
发帖数: 996 | 3 这个还真不会的说。。怎么做啊。
【在 t****t 的大作中提到】
: 数学,数学
|
j*******a
发帖数: 101 | 4 这个题目就搞不懂到底是什么意思.
【在 s*********e 的大作中提到】
: 给你一系列数N, 可能是无穷大
: 请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
: 如何做?
|
o*****e
发帖数: 48 | 5 remove the identical elements?
【在 s*********e 的大作中提到】
: 给你一系列数N, 可能是无穷大
: 请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
: 如何做?
|
j*****h
发帖数: 62 | 6 我猜想是这个意思,伪代码如下:
for (i=0; i
int r = rand(N-i);
swap(array[r], array[N-i-1]);
}
数组的最后M个数即为选出的数.
【在 s*********e 的大作中提到】
: 给你一系列数N, 可能是无穷大
: 请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
: 如何做?
|
s*********e
发帖数: 17 | 7 面试者给的提示是:
先选N个数中前M个数,
对第 (M+1)个数, 选择的概率是:???
因为选择了第 (M+1) 个数, 我们要delete 前M个数中的一个,
那么delete 第一个的数概率是 ???
那么delete 第二个的数概率是 ???
只是给大家一点思路,当时我也没有做出来
【在 s*********e 的大作中提到】
: 给你一系列数N, 可能是无穷大
: 请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
: 如何做?
|
k****f
发帖数: 3794 | 8 这个就是相当于抽签过程，不放回的
【在 s*********e 的大作中提到】
: 给你一系列数N, 可能是无穷大
: 请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
: 如何做?
|
P*****f
发帖数: 2272 | 9 secretary problem
给你一系列数N, 可能是无穷大
请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
如何做?
【在 s*********e 的大作中提到】
: 给你一系列数N, 可能是无穷大
: 请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
: 如何做?
|
P*****f
发帖数: 2272 | 10 btw, phone interview or on-site?
thx
secretary problem
给你一系列数N, 可能是无穷大
请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
如何做?
【在 P*****f 的大作中提到】
: secretary problem
:
: 给你一系列数N, 可能是无穷大
: 请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
: 如何做?
|
|
|
P***t
发帖数: 1006 | 11 YEAH, 貌似要一个ONLINE ALOGRITHM.
对第M+1及以后的数，SUPPOSE 序号是 X, 产生一个RANDOM NUMBER R 从 1-X, 如果在1
-M之内，与选中的第R个数互换；否则DISCARD.
可以用归纳法证明不管X为多少，前X个数被选中的可能性始终是 M/X.
【在 s*********e 的大作中提到】
: 面试者给的提示是:
: 先选N个数中前M个数,
: 对第 (M+1)个数, 选择的概率是:???
: 因为选择了第 (M+1) 个数, 我们要delete 前M个数中的一个,
: 那么delete 第一个的数概率是 ???
: 那么delete 第二个的数概率是 ???
: 只是给大家一点思路,当时我也没有做出来
|
t****t
发帖数: 6806 | 12 其实精华区有个和这类似的题 (x->23->13)
就是怎么产生一个长度N的随机排列; 一个随机排列的前M个就符合原问题的要求. 这个
复杂度也是O(n),而且是一次扫描(也就是online). 这个N个里选M个不过是把问题简化
了,如果交换的位置不在前M就扔掉.
"N是无限"不过是吓唬人的,意思就是要online(一次扫描).要学会审题!!!
在1
【在 P***t 的大作中提到】
: YEAH, 貌似要一个ONLINE ALOGRITHM.
: 对第M+1及以后的数，SUPPOSE 序号是 X, 产生一个RANDOM NUMBER R 从 1-X, 如果在1
: -M之内，与选中的第R个数互换；否则DISCARD.
: 可以用归纳法证明不管X为多少，前X个数被选中的可能性始终是 M/X.
|
q*****g
发帖数: 72 | 13 thrust是考试中心的老师?
【在 t****t 的大作中提到】
: 其实精华区有个和这类似的题 (x->23->13)
: 就是怎么产生一个长度N的随机排列; 一个随机排列的前M个就符合原问题的要求. 这个
: 复杂度也是O(n),而且是一次扫描(也就是online). 这个N个里选M个不过是把问题简化
: 了,如果交换的位置不在前M就扔掉.
: "N是无限"不过是吓唬人的,意思就是要online(一次扫描).要学会审题!!!
:
: 在1
|
t****t
发帖数: 6806 | 14 ...最近在网上看这些面试题,发现都很简单,可以一眼看出出题人想问啥, 所以常常暗
自得意洋洋...
对了, 快还钱!
【在 q*****g 的大作中提到】
: thrust是考试中心的老师?
|
c**r
发帖数: 10001 | 15 不跳槽浪费了呀，hehe...
【在 t****t 的大作中提到】
: ...最近在网上看这些面试题,发现都很简单,可以一眼看出出题人想问啥, 所以常常暗
: 自得意洋洋...
: 对了, 快还钱!
|
q*****g
发帖数: 72 | 16 大家一起跳...
【在 c**r 的大作中提到】
: 不跳槽浪费了呀，hehe...
|
t****t
发帖数: 6806 | 17 还是等拿到绿卡吧,sigh
【在 q*****g 的大作中提到】
: 大家一起跳...
|
j*******a
发帖数: 101 | 18 很牛的你～～～赞～～～
【在 t****t 的大作中提到】
: ...最近在网上看这些面试题,发现都很简单,可以一眼看出出题人想问啥, 所以常常暗
: 自得意洋洋...
: 对了, 快还钱!
|
c********e
发帖数: 383 | 19 u eb1/2?
【在 t****t 的大作中提到】
: 还是等拿到绿卡吧,sigh
|
t****t
发帖数: 6806 | 20 要是EB1那还等啥
【在 c********e 的大作中提到】
: u eb1/2?
|
|
|
c********e
发帖数: 383 | 21 ft...then go find a new job bah.
just learned that u can retain ur priority date once ur i140 is approved. th
en u can switch job and keep ur earlier PD
【在 t****t 的大作中提到】
: 要是EB1那还等啥
|
m***t
发帖数: 254 | 22 after 180 days of 140 approval, right?
th
【在 c********e 的大作中提到】
: ft...then go find a new job bah.
: just learned that u can retain ur priority date once ur i140 is approved. th
: en u can switch job and keep ur earlier PD
|
c********e
发帖数: 383 | 23 not 180, that 180 is for ur 485. for 140, once it is approved u fixed ur PD
for life under certain restrictions.
http://www.uscis.gov/files/pressrelease/afm_ch22_091206R.pdf
page 27 and 28
【在 m***t 的大作中提到】
: after 180 days of 140 approval, right?
:
: th
|
t****t
发帖数: 6806 | 24 条件是原来的公司不撤回吧
PD
【在 c********e 的大作中提到】
: not 180, that 180 is for ur 485. for 140, once it is approved u fixed ur PD
: for life under certain restrictions.
: http://www.uscis.gov/files/pressrelease/afm_ch22_091206R.pdf
: page 27 and 28
|
c********e
发帖数: 383 | 25 ft, read it ur self bah,
unless the previously approved Form I-140 petition has been revoked because
of fraud or willful misrepresentation.
will ur company revoke ur 140 saying its a fraud?
ang*** is not that bad bah
【在 t****t 的大作中提到】
: 条件是原来的公司不撤回吧
:
: PD
|
