我遇到的一个google面试题,现在也没有想明白,请大家帮忙# Programming - 葵花宝典
s*e
1 楼
给你一系列数N, 可能是无穷大
请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
如何做?
请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
如何做?
t*t
2 楼
数学,数学
【在 s*********e 的大作中提到】
: 给你一系列数N, 可能是无穷大
: 请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
: 如何做?
【在 s*********e 的大作中提到】
: 给你一系列数N, 可能是无穷大
: 请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
: 如何做?
c*d
3 楼
这个还真不会的说。。怎么做啊。
【在 t****t 的大作中提到】
: 数学,数学
【在 t****t 的大作中提到】
: 数学,数学
j*a
4 楼
这个题目就搞不懂到底是什么意思.
【在 s*********e 的大作中提到】
: 给你一系列数N, 可能是无穷大
: 请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
: 如何做?
【在 s*********e 的大作中提到】
: 给你一系列数N, 可能是无穷大
: 请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
: 如何做?
o*e
5 楼
remove the identical elements?
【在 s*********e 的大作中提到】
: 给你一系列数N, 可能是无穷大
: 请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
: 如何做?
【在 s*********e 的大作中提到】
: 给你一系列数N, 可能是无穷大
: 请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
: 如何做?
j*h
6 楼
我猜想是这个意思,伪代码如下:
for (i=0; i
swap(array[r], array[N-i-1]);
}
数组的最后M个数即为选出的数.
【在 s*********e 的大作中提到】
: 给你一系列数N, 可能是无穷大
: 请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
: 如何做?
for (i=0; i
swap(array[r], array[N-i-1]);
}
数组的最后M个数即为选出的数.
【在 s*********e 的大作中提到】
: 给你一系列数N, 可能是无穷大
: 请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
: 如何做?
s*e
7 楼
面试者给的提示是:
先选N个数中前M个数,
对第 (M+1)个数, 选择的概率是:???
因为选择了第 (M+1) 个数, 我们要delete 前M个数中的一个,
那么delete 第一个的数概率是 ???
那么delete 第二个的数概率是 ???
只是给大家一点思路,当时我也没有做出来
【在 s*********e 的大作中提到】
: 给你一系列数N, 可能是无穷大
: 请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
: 如何做?
先选N个数中前M个数,
对第 (M+1)个数, 选择的概率是:???
因为选择了第 (M+1) 个数, 我们要delete 前M个数中的一个,
那么delete 第一个的数概率是 ???
那么delete 第二个的数概率是 ???
只是给大家一点思路,当时我也没有做出来
【在 s*********e 的大作中提到】
: 给你一系列数N, 可能是无穷大
: 请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
: 如何做?
k*f
8 楼
这个就是相当于抽签过程，不放回的
【在 s*********e 的大作中提到】
: 给你一系列数N, 可能是无穷大
: 请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
: 如何做?
【在 s*********e 的大作中提到】
: 给你一系列数N, 可能是无穷大
: 请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
: 如何做?
P*f
9 楼
secretary problem
给你一系列数N, 可能是无穷大
请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
如何做?
【在 s*********e 的大作中提到】
: 给你一系列数N, 可能是无穷大
: 请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
: 如何做?
给你一系列数N, 可能是无穷大
请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
如何做?
【在 s*********e 的大作中提到】
: 给你一系列数N, 可能是无穷大
: 请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
: 如何做?
P*f
10 楼
btw, phone interview or on-site?
thx
secretary problem
给你一系列数N, 可能是无穷大
请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
如何做?
【在 P*****f 的大作中提到】
: secretary problem
:
: 给你一系列数N, 可能是无穷大
: 请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
: 如何做?
thx
secretary problem
给你一系列数N, 可能是无穷大
请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
如何做?
【在 P*****f 的大作中提到】
: secretary problem
:
: 给你一系列数N, 可能是无穷大
: 请你选出M个数 (M < N), 使N中每一个数被选中的概率相同.
: 如何做?
P*t
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 第二个的数概率是 ???
: 只是给大家一点思路,当时我也没有做出来
对第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
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.
就是怎么产生一个长度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
13 楼
thrust是考试中心的老师?
【在 t****t 的大作中提到】
: 其实精华区有个和这类似的题 (x->23->13)
: 就是怎么产生一个长度N的随机排列; 一个随机排列的前M个就符合原问题的要求. 这个
: 复杂度也是O(n),而且是一次扫描(也就是online). 这个N个里选M个不过是把问题简化
: 了,如果交换的位置不在前M就扔掉.
: "N是无限"不过是吓唬人的,意思就是要online(一次扫描).要学会审题!!!
:
: 在1
【在 t****t 的大作中提到】
: 其实精华区有个和这类似的题 (x->23->13)
: 就是怎么产生一个长度N的随机排列; 一个随机排列的前M个就符合原问题的要求. 这个
: 复杂度也是O(n),而且是一次扫描(也就是online). 这个N个里选M个不过是把问题简化
: 了,如果交换的位置不在前M就扔掉.
: "N是无限"不过是吓唬人的,意思就是要online(一次扫描).要学会审题!!!
:
: 在1
t*t
14 楼
...最近在网上看这些面试题,发现都很简单,可以一眼看出出题人想问啥, 所以常常暗
自得意洋洋...
对了, 快还钱!
【在 q*****g 的大作中提到】
: thrust是考试中心的老师?
自得意洋洋...
对了, 快还钱!
【在 q*****g 的大作中提到】
: thrust是考试中心的老师?
c*r
15 楼
不跳槽浪费了呀，hehe...
【在 t****t 的大作中提到】
: ...最近在网上看这些面试题,发现都很简单,可以一眼看出出题人想问啥, 所以常常暗
: 自得意洋洋...
: 对了, 快还钱!
【在 t****t 的大作中提到】
: ...最近在网上看这些面试题,发现都很简单,可以一眼看出出题人想问啥, 所以常常暗
: 自得意洋洋...
: 对了, 快还钱!
q*g
16 楼
大家一起跳...
【在 c**r 的大作中提到】
: 不跳槽浪费了呀，hehe...
【在 c**r 的大作中提到】
: 不跳槽浪费了呀，hehe...
t*t
17 楼
还是等拿到绿卡吧,sigh
【在 q*****g 的大作中提到】
: 大家一起跳...
【在 q*****g 的大作中提到】
: 大家一起跳...
j*a
18 楼
很牛的你～～～赞～～～
【在 t****t 的大作中提到】
: ...最近在网上看这些面试题,发现都很简单,可以一眼看出出题人想问啥, 所以常常暗
: 自得意洋洋...
: 对了, 快还钱!
【在 t****t 的大作中提到】
: ...最近在网上看这些面试题,发现都很简单,可以一眼看出出题人想问啥, 所以常常暗
: 自得意洋洋...
: 对了, 快还钱!
c*e
19 楼
u eb1/2?
【在 t****t 的大作中提到】
: 还是等拿到绿卡吧,sigh
【在 t****t 的大作中提到】
: 还是等拿到绿卡吧,sigh
t*t
20 楼
要是EB1那还等啥
【在 c********e 的大作中提到】
: u eb1/2?
【在 c********e 的大作中提到】
: u eb1/2?
c*e
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那还等啥
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
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
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
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
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
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
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
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
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
相关阅读
【讨论】问一道很简单的C++题。。。。 (转载)谁能说说Perl, Python, Tcl各自的优缺点？主要应用场合？create svn repositoryquestion about perl programmingHow to judge if it is a number in C++Θ(n)是什么意思？software for web developer ? Thank you!问个算法问题perl beginner question "1;" ?Garbage collection 问题请问，我怎么能简洁的证明这个Huffman tree 问题？一个哈希表问题请教一个design的问题shocking! The origin of foo() (转载)一个诡异的问题求救！！有人export class from a dll 吗？what's wrong with this C++ code?问一个关于copy constructor的菜鸟问题。。。。。 (转载)a question regarding....请教