b*****3
发帖数: 39 | 1 刚电面完，上来发面经，面试的是一个国人nice大哥，看linkedin简历秒我一百条街。
。。：
题目是：
Given an array or list of N elements. Return an array of K elements, with
each element in N has the exactly same chance to appear in the result, and
at certain position in the result. K<=N.
可以使用Math.Random()
Follow up是问时间和空间复杂度，然后问如果不是list，是一个stream list的话该怎
么做，时间和空间复杂度又是什么。 |
r*g
发帖数: 186 | 2 没读懂题
第一个是uniform的choose index from 1~N吗?
第二个是不是要求distribution?
【在 b*****3 的大作中提到】
: 刚电面完，上来发面经，面试的是一个国人nice大哥，看linkedin简历秒我一百条街。
: 。。：
: 题目是：
: Given an array or list of N elements. Return an array of K elements, with
: each element in N has the exactly same chance to appear in the result, and
: at certain position in the result. K<=N.
: 可以使用Math.Random()
: Follow up是问时间和空间复杂度，然后问如果不是list，是一个stream list的话该怎
: 么做，时间和空间复杂度又是什么。
|
h*******0
发帖数: 270 | |
a**y
发帖数: 335 | 4 http://en.wikipedia.org/wiki/Reservoir_sampling
【在 b*****3 的大作中提到】
: 刚电面完，上来发面经，面试的是一个国人nice大哥，看linkedin简历秒我一百条街。
: 。。：
: 题目是：
: Given an array or list of N elements. Return an array of K elements, with
: each element in N has the exactly same chance to appear in the result, and
: at certain position in the result. K<=N.
: 可以使用Math.Random()
: Follow up是问时间和空间复杂度，然后问如果不是list，是一个stream list的话该怎
: 么做，时间和空间复杂度又是什么。
|
c******g
发帖数: 238 | 5 取N大数组的subset 小数组K size两个数组的关于小数组的每个元素probability一致
？解的唯一性有要求么？比如说N中的每个元素必须在小数组K中出现？还是出题人随便
给一个K返回一个valid的解就可以呢？ |
h*******0
发帖数: 270 | |
c****8
发帖数: 76 | |
h****5
发帖数: 35 | 8 第二道题应该是基于贝叶斯公式吧，不存储data，只保留distribution，每新添一个观
测值就更新distribution. |
G*****m
发帖数: 5395 | 9 reservoir 算法吧 考这个有一点无聊
【在 b*****3 的大作中提到】
: 刚电面完，上来发面经，面试的是一个国人nice大哥，看linkedin简历秒我一百条街。
: 。。：
: 题目是：
: Given an array or list of N elements. Return an array of K elements, with
: each element in N has the exactly same chance to appear in the result, and
: at certain position in the result. K<=N.
: 可以使用Math.Random()
: Follow up是问时间和空间复杂度，然后问如果不是list，是一个stream list的话该怎
: 么做，时间和空间复杂度又是什么。
|
S*******C
发帖数: 822 | 10 mark
【在 b*****3 的大作中提到】
: 刚电面完，上来发面经，面试的是一个国人nice大哥，看linkedin简历秒我一百条街。
: 。。：
: 题目是：
: Given an array or list of N elements. Return an array of K elements, with
: each element in N has the exactly same chance to appear in the result, and
: at certain position in the result. K<=N.
: 可以使用Math.Random()
: Follow up是问时间和空间复杂度，然后问如果不是list，是一个stream list的话该怎
: 么做，时间和空间复杂度又是什么。
|
