Wayfair Labs全程面经

yjtwm 发表于 2015-12-23 09:07
https://en.wikipedia.org/wiki/Reservoir_sampling
第一个算法，你也是最近要面吗？

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

yjtwm 发表于 2015-12-23 09:08
你这样是完全随机的吗？照你这样取得话第一个int一定会被取到的吧，还是我理解错了

是随机的，而且也是等概率的

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，所以这个算法是对的

nevermor 发表于 2015-12-23 09:59
比如1到10十个数，想选3个数，先随机一个1到10的数，假如是7，把7放到结果里，并且把7和10交换个位置，原 ...

多谢详解，太感动了～～

nevermor 发表于 2015-12-22 20:59
比如1到10十个数，想选3个数，先随机一个1到10的数，假如是7，把7放到结果里，并且把7和10交换个位置，原 ...

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

eamon_felix4213 发表于 2015-12-23 11:40
有一个疑问 每次 random 比如 第一次 random 取数的时候 你们是用的 比如如果java的话 Random 方法吗 还 ...

对，应该是，你最近也要面吗？

yjtwm 发表于 2015-12-22 22:54
对，应该是，你最近也要面吗？

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

eamon_felix4213 发表于 2015-12-23 11:59
没有 但是想做做面经题 你是几号面呢 已经约好时间了吗

嗯，我最近面，不过还没约好

yjtwm 发表于 2015-12-22 23:05
嗯，我最近面，不过还没约好

明天面？后天平安夜不放假吗

eamon_felix4213 发表于 2015-12-23 12:07
明天面？后天平安夜不放假吗

不是，得过段时间