一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1573|回复: 16
收起左侧

Amazon Intern 新鲜面经

[复制链接] |试试Instant~ |关注本帖
111180611 发表于 2016-2-11 02:01:38 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 实习@Amazon - 网上海投 - 技术电面 |Other其他

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
刚面完,是个听起来是个印度大妈,口音把我害苦了上来就做题
1.给俩数组找intersection. 1point 3acres 璁哄潧
一开始以为全都一位的
用了个数组 发现不对. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
又用的hashmap
2.问我知不知道teli, 我说three? array?
结果是tree
给一个树, 返回一个random node, 要求所有node has equal probability.1point3acres缃
然后又问如果一个node has an extra info total = num of left children + num of right children + 1
问能不能用这个帮忙解决上面的问题



. from: 1point3acres.com/bbs

评分

1

查看全部评分

本帖被以下淘专辑推荐:

prasca 发表于 2016-2-12 22:38:33 | 显示全部楼层
你可以把整个树投射到一个连续整数组成的binary search tree-google 1point3acres
然后对root,从[1,totalNumber]random出一个整数n
如果n<left.totalNumber 去left找
如果n=left.totalNumber+1 那就是这个结点了
如果n>left.totalNumber+1 去right找
回复 支持 2 反对 0

使用道具 举报

ruokua 发表于 2016-3-3 15:50:20 | 显示全部楼层
第二题不用那么麻烦
这就是Reservoir Sampling的问题. Waral 鍗氬鏈夋洿澶氭枃绔,

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..1point3acres缃
So:
. From 1point 3acres bbs
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;. from: 1point3acres.com/bbs
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.. 1point3acres.com/bbs


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

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

使用道具 举报

spwahaha 发表于 2016-2-13 22:07:45 | 显示全部楼层
知道root孩子个数,随机一个数,然后根据这个数 = total(root.left) + 1 返回根, <(total.left) + 1在左边找,>(total。left) + 1在右边找
回复 支持 1 反对 0

使用道具 举报

 楼主| 111180611 发表于 2016-2-12 04:56:19 | 显示全部楼层
Is there anyone has any idea about the follow up of the second problem?
回复 支持 反对

使用道具 举报

aqua0717 发表于 2016-2-12 22:51:44 | 显示全部楼层
能仔细讲讲第二道题是什么意思吗。。。?
回复 支持 反对

使用道具 举报

 楼主| 111180611 发表于 2016-2-13 03:04:17 | 显示全部楼层
prasca 发表于 2016-2-12 22:38
你可以把整个树投射到一个连续整数组成的binary search tree
然后对root,从[1,totalNumber]random出一 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
你的意思是建一个跟原树结构相同的BST?
回复 支持 反对

使用道具 举报

 楼主| 111180611 发表于 2016-2-13 03:05:39 | 显示全部楼层
aqua0717 发表于 2016-2-12 22:51
能仔细讲讲第二道题是什么意思吗。。。?

就是写一个方法,返回任意一个节点,保证所有节点被选中的可能性相同
回复 支持 反对

使用道具 举报

dendi 发表于 2016-2-14 02:01:42 | 显示全部楼层
prasca 发表于 2016-2-12 22:38
你可以把整个树投射到一个连续整数组成的binary search tree
然后对root,从[1,totalNumber]random出一 ...

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

使用道具 举报

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

不是她的意思就是算法要保证每个节点都有相同的被选中的可能,这个我确定
回复 支持 反对

使用道具 举报

dendi 发表于 2016-2-14 06:29:34 | 显示全部楼层
111180611 发表于 2016-2-14 06:01. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
不是她的意思就是算法要保证每个节点都有相同的被选中的可能,这个我确定

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

使用道具 举报

 楼主| 111180611 发表于 2016-2-14 10:17:41 | 显示全部楼层
dendi 发表于 2016-2-14 06:29
我说的就是第二个问题啊,node has an extra info total = num of left children + num of right childre ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
她的意思是如果有这个信息怎么解决上面的问题
回复 支持 反对

使用道具 举报

heroic 发表于 2016-2-14 10:38:30 | 显示全部楼层
先假定选取根 然后对树进行遍历 每遍历到第k个结点 有1/k概率拿这个结点来替换选中的结点, 知道遍历整个树为止。 证明可以用数学归纳法。相当于从一个streaming的数组中等概率的随机取一个。
回复 支持 反对

使用道具 举报

dendi 发表于 2016-2-14 11:26:00 | 显示全部楼层
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。
遍历的话直接遍历就行。
回复 支持 反对

使用道具 举报

每个昨天太年轻 发表于 2016-3-3 11:34:05 | 显示全部楼层
第二题好神奇~~~~
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 01:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表