Amazon Intern 新鲜面经

dendi 发表于 2016-2-14 02:01
其实这道题应该用不着建立一个BST.直接遍历完找到这个value就行。三姐其实是问你这个为何是 equal probab ...

不是她的意思就是算法要保证每个节点都有相同的被选中的可能，这个我确定

111180611 发表于 2016-2-14 06:01
不是她的意思就是算法要保证每个节点都有相同的被选中的可能，这个我确定

我说的就是第二个问题啊，node has an extra info total = num of left children + num of right children + 1 可以保证等概率, 但她问你能不能所以需要证明这点。 然后search(random) 返回那个节点就行。

dendi 发表于 2016-2-14 06:29
我说的就是第二个问题啊，node has an extra info total = num of left children + num of right childre ...

她的意思是如果有这个信息怎么解决上面的问题

先假定选取根 然后对树进行遍历 每遍历到第k个结点 有1/k概率拿这个结点来替换选中的结点， 知道遍历整个树为止。 证明可以用数学归纳法。相当于从一个streaming的数组中等概率的随机取一个。

heroic 发表于 2016-2-14 10:38
先假定选取根 然后对树进行遍历 每遍历到第k个结点 有1/k概率拿这个结点来替换选中的结点， 知道遍历整个树 ...

这样的吧：
if (random(1 , node.val)==node.val && random(1,root.val)==node.val)  return node
证明的话感觉可以用Bayesian:
P(this)=P(this|this.val)P(this.val|toal) = 1/total。
遍历的话直接遍历就行。

第二题好神奇~~~~

第二题不用那么麻烦
这就是Reservoir Sampling的问题

Keep the first item in memory.
When the i-th item arrives (for i>1):
with probability 1/i, keep the new item instead of the current item;
with probability 1-1/i, keep the current item and discard the new item.
So:

when there is only one item, it is kept with probability 1;
when there are 2 items, each of them is kept with probability 1/2;
when there are 3 items, the third item is kept with probability 1/3, and each of the previous 2 items is also kept with probability (1/2)(1-1/3) = (1/2)(2/3) = 1/3;
by induction, it is easy to prove that when there are n items, each item is kept with probability 1/n.


补充内容 (2016-3-3 15:57):
以上是第一问

第2问上面说的应该很对了
但如果这个method 经常call
但其实可以把tree 变进array
之后random index 就好