c********g
发帖数: 42 | 1 上次面试被面到的，感觉跟概率比较相关
题目要求从n个input中random sample k个数 （k<=n)
其中n是未知的，input是以online的形式获得的。即给定一个function getInput(),
调用这个function每次可以获得一个数，取完为止，但是你不知道一共有多少个数。
要求：
1. 返回 k个数，保证randomness
2. 可用的memory只有k，即最多只能存k个数，所以不能把n个数都存下来，再random
sample
不知道描述清楚了没有。。。 |
y*****e
发帖数: 712 | 2 这应该就是reservior sampling吧 |
w******n
发帖数: 61 | 3 +1
[在 yuxrose (鱼香肉丝) 的大作中提到：]
：这应该就是reservior sampling吧
：
：........... |
c*******7
发帖数: 438 | 4 设置一个size为k的set，每次随机替换一个如何？ |
c********g
发帖数: 42 | 5 我去。。。
这道题竟然也在题库里啊 。。。
刷leetcode的时候好像没有刷到啊
顺便求问刷完leetcode 和 crakingcode interview
还可以刷什么
【在 y*****e 的大作中提到】
: 这应该就是reservior sampling吧
|
g***s
发帖数: 3811 | 6 这不是题库，是基本算法之一。
不过，现场要能自己做出来有点难。一般把k改成1比较适合做面试题。做出来以后再引
申到k
【在 c********g 的大作中提到】
: 我去。。。
: 这道题竟然也在题库里啊 。。。
: 刷leetcode的时候好像没有刷到啊
: 顺便求问刷完leetcode 和 crakingcode interview
: 还可以刷什么
|
v****a
发帖数: 236 | 7 虽然很多题不是题库，不过这道的确是cracking the coding interview里的原题。。
第五版
3年前就在面经里出现过了。。 |
s******s
发帖数: 2721 | 8 随即替换的想法挺直接的啊，如果要证明的话有点麻烦就是了。
【在 g***s 的大作中提到】
: 这不是题库，是基本算法之一。
: 不过，现场要能自己做出来有点难。一般把k改成1比较适合做面试题。做出来以后再引
: 申到k
|
c********g
发帖数: 42 | 9 看来我看的那本书可能是旧版 刷了一遍 没有这道题啊
不过我还是做出来了 哈哈 clever me
【在 v****a 的大作中提到】
: 虽然很多题不是题库，不过这道的确是cracking the coding interview里的原题。。
: 第五版
: 3年前就在面经里出现过了。。
|
B**********2
发帖数: 923 | 10 用一个n记着getInput()多少次
getInput没满k之前，都存下。
满了k之后，rand() mod n, 如果在0到k-1范围就替换那个，超范围就不管了
【在 c********g 的大作中提到】
: 上次面试被面到的，感觉跟概率比较相关
: 题目要求从n个input中random sample k个数 （k<=n)
: 其中n是未知的，input是以online的形式获得的。即给定一个function getInput(),
: 调用这个function每次可以获得一个数，取完为止，但是你不知道一共有多少个数。
: 要求：
: 1. 返回 k个数，保证randomness
: 2. 可用的memory只有k，即最多只能存k个数，所以不能把n个数都存下来，再random
: sample
: 不知道描述清楚了没有。。。
|
|
|
s*****7
发帖数: 20 | 11 证明用归纳法的话也不麻烦
【在 s******s 的大作中提到】
: 随即替换的想法挺直接的啊，如果要证明的话有点麻烦就是了。
|
r****7
发帖数: 2282 | 12 这题我09年面百度的时候就有了...不过当时听过同学面google的面经，他面的是k = 1
，所以我面的时候就有思路
【在 c********g 的大作中提到】
: 上次面试被面到的，感觉跟概率比较相关
: 题目要求从n个input中random sample k个数 （k<=n)
: 其中n是未知的，input是以online的形式获得的。即给定一个function getInput(),
: 调用这个function每次可以获得一个数，取完为止，但是你不知道一共有多少个数。
: 要求：
: 1. 返回 k个数，保证randomness
: 2. 可用的memory只有k，即最多只能存k个数，所以不能把n个数都存下来，再random
: sample
: 不知道描述清楚了没有。。。
|
r****7
发帖数: 2282 | 13 我靠，牛，居然有专门的名词
【在 y*****e 的大作中提到】
: 这应该就是reservior sampling吧
|
d******w
发帖数: 2213 | 14 不知道N
【在 B**********2 的大作中提到】
: 用一个n记着getInput()多少次
: getInput没满k之前，都存下。
: 满了k之后，rand() mod n, 如果在0到k-1范围就替换那个，超范围就不管了
|
o**********5
发帖数: 53 | 15 minor typo???
"满了k之后，rand() mod n" should be "满了k之后，rand() mod *i*", where i is
the round number. "n" might be unknown, right?
【在 B**********2 的大作中提到】
: 用一个n记着getInput()多少次
: getInput没满k之前，都存下。
: 满了k之后，rand() mod n, 如果在0到k-1范围就替换那个，超范围就不管了
|
l***h
发帖数: 678 | 16 假设已经取到第m数，下一个要取m+1数，存下的k数是完全平均的。这意味着
m个数，平均每个数出现 k/m 次， 下面要加一个新数字。那么以前存的数
以概率为 (k/m)/((k^2/m)+1) 删除，新加的数 以概率为 1/((k^2/m)+1) 删除， 就能
保证
剩下的 k 个数再次均匀了。 |
c*******e
发帖数: 373 | 17 int i;
int b[k];
// All numbers are 100% sure to be chosen, if n=k
for (i = 0; i < k; i ++)
b[i] = getInput();
// Or if n > k, let's keep trying until no more input
while (stillHaveMoreInput() == true) {
int t = getInput();
i ++;
// The new number has k / i chance to be chosen
if (rand(i) < k) {
// OK, now we hit the k/i chance
// Current number is chosen
// But which old one should be replaced?
// Each of the old one has equal chance 1/k
b[rand(k)] = t;
}
} |
c*******e
发帖数: 373 | 18 讲上面代码中得两次rand调用合并为一次，逻辑是等价的，速度更快（rand是一个昂贵
的操作）
int s = rand(i);
if (s < k) // The new number t is chosen
b[s] = t; // Old number b[s] need be kicked out
|
f****l
发帖数: 8042 | |
s***f
发帖数: 457 | 20 发信人: svcef (svcef), 信区: JobHunting
标 题: 你是否愿意通过自学转行成为一个软件工程师
发信站: BBS 未名空间站
(这个机会仅仅适用于位于硅谷南湾的人, 谢谢。 Our office is on Walsh Ave,
Santa Clara. CA, 95050 )
这个帖子， 前一阵子， 发过一次， 由于大家反馈非常好， 就再发一次， 希望对更
多的朋友有帮助。绝对不收任何费用， 我们提供完全免费的转行软件工程师的机会。
这个帖子是写给那些朋友， 以前由于各种原因， 没能够成为计算机专业学
生，现在愿意通过自学成为一个软件工程师.
这可以做到嘛 ？
实际上， 任何人通过自学成为一个软件编程的高手都不是什么难的事情。只要肯花许
多时间学习和练习， 加上有人可以指导答疑, 每个愿意成为软件工程师的人都可以通
过一段时间的学习成为一个不错的软件工程师。
如果你正想成为一个软件工程师， 请联系我们。 我们能够提供机会帮助你成为一个软
件工程师。绝对不收任何费用。
我们提供一个边工作， 边学习的机会。
只有一个要求， 希望你现在还有努力学习的动力和勤奋精神。
注1: 许多软件编程的高手都不是计算机专业学生. 举例来说， 微软的Bill Gates，
Facebook的Mark Zuckerberg, 都是软件编程的高手，但都不是学计算机专业的. Bill
Gates本来大概要学法律， Mark Zuckerberg本来是心理学专业的。
只要你有真材实料， 转行到软件， 是不需要一个CS的学位的。
注2: 如果您本身是一个软件工程师， 读到这个帖子， 请您手下留情， 请不要为
“码工”这个职业泼冷水。您也许不知道， 有许多人羡慕你的职业呢 ？ 正想成为一
个软件工程师 ？ 软件工程师, 工作有挑战性， 收入也不错。我们就是希望提供机会
给这样的朋友。
注3: 我们不承诺给任何人办H-1B, 但如果优秀的， 我们团队愿意自己留下来的，
我们可以帮助办H-1B.
注4: 我们这个项目绝对不收任何费用。
注5： 我们和硅谷任何别的软件培训，职业培训， bootcamp没有任何关系。
我们也不是这样的一个软件培训，职业培训， bootcamp机构。 我们提供的学习
机会
是完全免费的。
如果你正在考虑下一个工作方向, 如果你正想成为一个软件工程师， 有许多时间可以
用来学习， 站内请联系我们。 我们能够提供机会帮助你成为一个软件工程师。
关于我们这个项目的说明：
我们是一家初创startup Internet software 公司， 这个项目为我们自己公司培养人
才。公司还在创业阶段，已有少量客户， 但收入很少，发不了工资， 但我们这个创业
团队对公司未来充满信心。 希望你可以用来学习工作的时间不少于一周至25小时,来我
们位于硅谷南湾的办公室工作。对于有意和我们共同长期把公司做成功的，
公司会发原始股。
我们主要开发Internet software for Enterprise Application， 用的语言是：
Python, Java, PHP, MySQL. (不要求你有相关语言和背景， 只要求你有强烈意愿学
习)。
技术工作主要做网站server端的开发 （包括， Python, Java, PHP, Django, etc)，
也有客户端的开发。 客户端的开发包括
web front end 以及手机App和Facebook Apps.
详情, 请站内联系。
请给我们一个机会， 也给你自己一个机会。也许这就是你长久等待的一个机会。
(This opportunity is 仅仅限于硅谷南湾, 谢谢, Our office is on Walsh Ave,
Santa Clara. CA, 95050.
如果你不在硅谷南湾， 很对不起， 我们这个项目不合适你。)
如果您对这个项目不感兴趣， 请不要给别人泼冷水。
已经有多人从我们这个项目受益。
【在 c********g 的大作中提到】
: 上次面试被面到的，感觉跟概率比较相关
: 题目要求从n个input中random sample k个数 （k<=n)
: 其中n是未知的，input是以online的形式获得的。即给定一个function getInput(),
: 调用这个function每次可以获得一个数，取完为止，但是你不知道一共有多少个数。
: 要求：
: 1. 返回 k个数，保证randomness
: 2. 可用的memory只有k，即最多只能存k个数，所以不能把n个数都存下来，再random
: sample
: 不知道描述清楚了没有。。。
|
