avatar
这道google面经体咋做# JobHunting - 待字闺中
y*d
1
一个set里面有a,b,c等若干个char,设计random函数,得到某个char的概率和它
的出现次数成正比。
avatar
i*t
2
编程题还是统计概率题。。。

【在 y*******d 的大作中提到】
: 一个set里面有a,b,c等若干个char,设计random函数,得到某个char的概率和它
: 的出现次数成正比。

avatar
y*d
3
编程
估计是design

【在 i******t 的大作中提到】
: 编程题还是统计概率题。。。
avatar
i*t
4
Dirichlet-multinomial distribution?

【在 y*******d 的大作中提到】
: 编程
: 估计是design

avatar
y*d
5
不懂 这是啥啊
有code么

【在 i******t 的大作中提到】
: Dirichlet-multinomial distribution?
avatar
e*s
6
weighted reservoir sampling?

【在 y*******d 的大作中提到】
: 一个set里面有a,b,c等若干个char,设计random函数,得到某个char的概率和它
: 的出现次数成正比。

avatar
m*n
7
虽然算法垃圾一点,但是work的。
def test(data):
dataset = [[n, data.count(n)] for n in set(data)]
for i in xrange(2):
copydataset = copy.deepcopy(dataset)
print list(generator(copydataset))
print '\n'

def generator(dataset):
size = len(dataset)
while dataset:
index = int(random.random()*size)
dataset[index][1] -= 1
char = dataset[index][0]
if not dataset[index][1]:
dataset.pop(index)
size = size - 1
yield char
avatar
m*a
8
Add data to array, return a random index.
public char randomChar(){
List data = new ArrayList<>();
data.add('a');data.add('b');data.add('a')....
return data.get(new Random().nextInt(data.size()));
}

【在 y*******d 的大作中提到】
: 一个set里面有a,b,c等若干个char,设计random函数,得到某个char的概率和它
: 的出现次数成正比。

avatar
M*x
9
Reservoir Sampling?
avatar
z*6
10
freq总和,random(0,freq)之后得数字map回char就好了啊。reservoir sampling是
用于linkedlist而不知道总长度用的
avatar
m*n
11
要是追问,数据太大内存放不下怎么办。Google会出这么简单的题?其实这是一个云计
算题。
avatar
r*y
12
这个解法一旦被问有billion怎么办就成屎了,提示input是char不是string,一共就
256个char

【在 m*********a 的大作中提到】
: Add data to array, return a random index.
: public char randomChar(){
: List data = new ArrayList<>();
: data.add('a');data.add('b');data.add('a')....
: return data.get(new Random().nextInt(data.size()));
: }

avatar
c*t
13
同意,因为char数量有限,数字map回char的时候可以iterate chars one by one

【在 z*****6 的大作中提到】
: freq总和,random(0,freq)之后得数字map回char就好了啊。reservoir sampling是
: 用于linkedlist而不知道总长度用的

avatar
h*c
14
一开始出现次数是0,概率是0,啥也不出现,成正比,概率返回条件是0.
avatar
h*c
15
觉得这是个behav题。
avatar
k*a
16
扫描set,将字符出现频率排序, 然后做一个frequency data的数组,
[{0.0, 0.3, a}, {0.3, 0.5, b}, {0.5, 0.6, c}, {0.6, 0.7, d}, ....]
然后随机产生0-1的浮点数,然后找个数组扫。数组最大是256个items
有点无脑?
不知道follow up是什么样子
avatar
r*t
17
这不是 uniform sample with replacement 就行了?大数据的话用 metropolis 算法
吧最多。

【在 i******t 的大作中提到】
: Dirichlet-multinomial distribution?
avatar
b*y
18
为什么不是reservoir sampling?
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。