我是如何肉身翻墙,从国内直接来美国工作的?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
查看: 2806|回复: 16
收起左侧

Amazon Intern 新鲜面经

[复制链接] |试试Instant~ |关注本帖
我的人缘0
111180611 发表于 2016-2-11 02:01:38 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

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

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

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

x
刚面完,是个听起来是个印度大妈,口音把我害苦了上来就做题
1.给俩数组找intersection.本文原创自1point3acres论坛
一开始以为全都一位的
用了个数组 发现不对
又用的hashmap
2.问我知不知道teli, 我说three? array?
结果是tree. From 1point 3acres bbs
给一个树, 返回一个random node, 要求所有node has equal probability
然后又问如果一个node has an extra info total = num of left children + num of right children + 1
问能不能用这个帮忙解决上面的问题



. 1point3acres

评分

1

查看全部评分


上一篇:FaceBook 一面求过
下一篇:Facebook - Production Engineer, 第三轮system. 被血虐

本帖被以下淘专辑推荐:

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

使用道具 举报

我的人缘0
ruokua 发表于 2016-3-3 15:50:20 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
第二题不用那么麻烦
这就是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;. 围观我们@1point 3 acres
with probability 1-1/i, keep the current item and discard the new item.. from: 1point3acres
So:

when there is only one item, it is kept with probability 1;. visit 1point3acres for more.
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 就好
回复 支持 1 反对 0

使用道具 举报

我的人缘0
spwahaha 发表于 2016-2-13 22:07:45 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
知道root孩子个数,随机一个数,然后根据这个数 = total(root.left) + 1 返回根, <(total.left) + 1在左边找,>(total。left) + 1在右边找
回复 支持 1 反对 0

使用道具 举报

我的人缘0
 楼主| 111180611 发表于 2016-2-12 04:56:19 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
Is there anyone has any idea about the follow up of the second problem?
回复 支持 反对

使用道具 举报

我的人缘0
aqua0717 发表于 2016-2-12 22:51:44 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
能仔细讲讲第二道题是什么意思吗。。。?
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| 111180611 发表于 2016-2-13 03:04:17 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
prasca 发表于 2016-2-12 22:38
你可以把整个树投射到一个连续整数组成的binary search tree
然后对root,从[1,totalNumber]random出一 ...
.1point3acres网
你的意思是建一个跟原树结构相同的BST?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| 111180611 发表于 2016-2-13 03:05:39 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
aqua0717 发表于 2016-2-12 22:51. 留学申请论坛-一亩三分地
能仔细讲讲第二道题是什么意思吗。。。?
. 一亩-三分-地,独家发布
就是写一个方法,返回任意一个节点,保证所有节点被选中的可能性相同
回复 支持 反对

使用道具 举报

我的人缘0
dendi 发表于 2016-2-14 02:01:42 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
prasca 发表于 2016-2-12 22:38
你可以把整个树投射到一个连续整数组成的binary search tree
然后对root,从[1,totalNumber]random出一 ...

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

使用道具 举报

我的人缘0
 楼主| 111180611 发表于 2016-2-14 06:01:28 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
dendi 发表于 2016-2-14 02:01
其实这道题应该用不着建立一个BST.直接遍历完找到这个value就行。三姐其实是问你这个为何是 equal probab ...

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

使用道具 举报

我的人缘0
dendi 发表于 2016-2-14 06:29:34 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
111180611 发表于 2016-2-14 06:01
不是她的意思就是算法要保证每个节点都有相同的被选中的可能,这个我确定

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

使用道具 举报

我的人缘0
 楼主| 111180611 发表于 2016-2-14 10:17:41 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
dendi 发表于 2016-2-14 06:29
我说的就是第二个问题啊,node has an extra info total = num of left children + num of right childre ...

她的意思是如果有这个信息怎么解决上面的问题
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
dendi 发表于 2016-2-14 11:26:00 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
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。
遍历的话直接遍历就行。
回复 支持 反对

使用道具 举报

我的人缘0
每个昨天太年轻 发表于 2016-3-3 11:34:05 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
第二题好神奇~~~~
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-28 17:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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