楼主: oneshot
跳转到指定楼层
上一主题 下一主题
收起左侧

Wayfair Labs全程面经

🔗
nevermor 2015-12-23 09:16:20 | 只看该作者
全局:
yjtwm 发表于 2015-12-23 09:07
https://en.wikipedia.org/wiki/Reservoir_sampling
第一个算法,你也是最近要面吗?

已经拒了他家了…懂你的这个算法了,只是有一个问题,这个水塘取样的时间复杂度是O(n-k),我提到的那个是O(k)
回复

使用道具 举报

🔗
nevermor 2015-12-23 09:21:37 | 只看该作者
全局:
yjtwm 发表于 2015-12-23 09:08
你这样是完全随机的吗?照你这样取得话第一个int一定会被取到的吧,还是我理解错了

是随机的,而且也是等概率的
回复

使用道具 举报

🔗
nevermor 2015-12-23 09:59:59 | 只看该作者
全局:
yjtwm 发表于 2015-12-23 09:08
你这样是完全随机的吗?照你这样取得话第一个int一定会被取到的吧,还是我理解错了

比如1到10十个数,想选3个数,先随机一个1到10的数,假如是7,把7放到结果里,并且把7和10交换个位置,原数组变成1,2,3,4,5,6,10,8,9,7,这时候随机一个1到9的数,假设是3,把3放到结果里,并且把3和9交换位置,数组变成1,2,9,4,5,6,10,8,3,7,再随机一个1到8的数,比如还是7,这时候把第7个数就是10放到结果里,然后把10和8交换,数组变成1,2,9,4,5,6,8,10,3,7. 如果还有后面的话就继续随机1到7的数,其实原数组的最后k位也是最后想要的结果

补充内容 (2015-12-23 10:03):
而且是等概率的,比如上面这个例子,对某一个数来说,第一次被选中的概率是1/10,第二次中的概率是9/10 *1/9 = 1/10,第三次中的概率是9/10 * 8/9 * 1/8 = 1/10,总体被抽中的概率是3/10,所以这个算法是对的
回复

使用道具 举报

🔗
yjtwm 2015-12-23 10:19:54 | 只看该作者
全局:
nevermor 发表于 2015-12-23 09:59
比如1到10十个数,想选3个数,先随机一个1到10的数,假如是7,把7放到结果里,并且把7和10交换个位置,原 ...

多谢详解,太感动了~~
回复

使用道具 举报

🔗
eamon_felix4213 2015-12-23 11:40:26 | 只看该作者
全局:
nevermor 发表于 2015-12-22 20:59
比如1到10十个数,想选3个数,先随机一个1到10的数,假如是7,把7放到结果里,并且把7和10交换个位置,原 ...

有一个疑问 每次 random 比如 第一次 random 取数的时候 你们是用的 比如如果java的话 Random 方法吗 还是别的呢 感谢
回复

使用道具 举报

🔗
yjtwm 2015-12-23 11:54:02 | 只看该作者
全局:
eamon_felix4213 发表于 2015-12-23 11:40
有一个疑问 每次 random 比如 第一次 random 取数的时候 你们是用的 比如如果java的话 Random 方法吗 还 ...

对,应该是,你最近也要面吗?
回复

使用道具 举报

🔗
eamon_felix4213 2015-12-23 11:59:35 | 只看该作者
全局:
yjtwm 发表于 2015-12-22 22:54
对,应该是,你最近也要面吗?

没有 但是想做做面经题 你是几号面呢 已经约好时间了吗
回复

使用道具 举报

🔗
yjtwm 2015-12-23 12:05:41 | 只看该作者
全局:
eamon_felix4213 发表于 2015-12-23 11:59
没有 但是想做做面经题 你是几号面呢 已经约好时间了吗

嗯,我最近面,不过还没约好
回复

使用道具 举报

🔗
eamon_felix4213 2015-12-23 12:07:36 | 只看该作者
全局:
yjtwm 发表于 2015-12-22 23:05
嗯,我最近面,不过还没约好

明天面?后天平安夜不放假吗
回复

使用道具 举报

🔗
yjtwm 2015-12-23 12:35:33 | 只看该作者
全局:
eamon_felix4213 发表于 2015-12-23 12:07
明天面?后天平安夜不放假吗

不是,得过段时间
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表