Amazon Intern 新鲜面经

刚面完，是个听起来是个印度大妈，口音把我害苦了上来就做题
1.给俩数组找intersection
一开始以为全都一位的
用了个数组 发现不对
又用的

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ht children + 1
问能不能用这个帮忙解决上面的问题

你可以把整个树投射到一个连续整数组成的binary search tree
然后对root，从［1，totalNumber］random出一个整数n
如果n<left.totalNumber 去left找
如果n=left.totalNumber+1 那就是这个结点了
如果n>left.totalNumber+1 去right找

第二题不用那么麻烦
这就是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 就好

知道root孩子个数，随机一个数，然后根据这个数 = total(root.left) + 1 返回根， <(total.left) + 1在左边找，>(total。left) + 1在右边找

感谢分享！！

Is there anyone has any idea about the follow up of the second problem?

23333 teli...

能仔细讲讲第二道题是什么意思吗。。。？

prasca 发表于 2016-2-12 22:38
你可以把整个树投射到一个连续整数组成的binary search tree
然后对root，从［1，totalNumber］random出一 ...

你的意思是建一个跟原树结构相同的BST？

aqua0717 发表于 2016-2-12 22:51
能仔细讲讲第二道题是什么意思吗。。。？

就是写一个方法，返回任意一个节点，保证所有节点被选中的可能性相同

prasca 发表于 2016-2-12 22:38
你可以把整个树投射到一个连续整数组成的binary search tree
然后对root，从［1，totalNumber］random出一 ...

其实这道题应该用不着建立一个BST.直接遍历完找到这个value就行。三姐其实是问你这个为何是 equal probablity 的。
其实证明的话感觉可以用Bayesian:
P(this)=P(this|this.val)P(this.val|toal) = 1/total。