一亩三分地论坛

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

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

Amazon Onsite最后一面

[复制链接] |试试Instant~ |关注本帖
海拔2纳米 发表于 2014-12-10 07:21:47 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Amazon - 内推 - Onsite |Fail

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

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

x
昨天把onsite缺的那一面用电话补上了,然后今天说我挂了,完全不知道为什么。

题目一道是valid parentheses,一道是polite number.
polite number的意思是一个正整数可以表示为几个连续的正整数的和。
3 = 1 + 2
5 =     2 + 3
6 = 1 + 2 + 3
.
.
.
15 = 1 + 2 + 3 + 4 + 5
                 4 + 5 + 6
                            7 + 8
.鐣欏璁哄潧-涓浜-涓夊垎鍦
给你一个正整数,让你求出一共有多少种表示的可能性,比如3就返回1,15就返回3.
.鐣欏璁哄潧-涓浜-涓夊垎鍦
每一面我都答得挺好的,有两个面试官在我面完了都说 i think you did well. 昨天这个电面第二题稍微给了一点提示我才写出了最优解,其他的都是直接写完没有任何bug。从头到尾就一道设计题,我也答得还可以。完全不能理解自己挂在了哪里,奇葩的bar。

另外补上之前onsite遇到的一道非算法题:
一个cloud里有N台server,比如里面存了一个变量叫x=3,和这个变量同时存储在server里的还有这个变量的version。进行了一次写操作改成了x=5,同是将相应的version+1.由于写操作比较耗费资源因此每次写并不是把所有N台server的数据全改写了,只写了W台。现在另外一个client要读出x的数据。为了保证consistency,必须得到x=5而不是x=3。假设需要读取R次(在已知N和W的情况下)我才能保证我得到的是最新的数据。那么N,W,R有一个什么样的关系?

评分

2

查看全部评分

yuruofeifei 发表于 2014-12-10 09:44:21 | 显示全部楼层
楼主加油,面了这么多家肯定有满意的offer的! 感觉他们家的bar确实挺奇怪的。。
回复 支持 反对

使用道具 举报

Adeath 发表于 2014-12-10 09:54:04 | 显示全部楼层
我靠  这么快就出结果  
没事你还有fb  加油拿下  比Amazon爽多了
回复 支持 反对

使用道具 举报

haoranliu1990 发表于 2014-12-10 10:56:02 | 显示全部楼层
楼主补的那道非算法题好像是他家dynamo 论文上讨论的一个topic,好像是 R + W > N 就可以。话说面的这么好都不给offer,太丧心病狂了吧。。。
回复 支持 反对

使用道具 举报

titan312 发表于 2014-12-10 11:27:44 | 显示全部楼层
楼主的非算法题应该是考Quorum Consistency。 要满足两个条件: 1. R + W > N  2. W > N/2
回复 支持 反对

使用道具 举报

nibuxing 发表于 2014-12-10 11:50:08 | 显示全部楼层
不是吧,我看楼主好像面的不错,怎么就fail了。。
回复 支持 反对

使用道具 举报

 楼主| 海拔2纳米 发表于 2014-12-10 14:49:17 | 显示全部楼层
是的那道非算法题我当时说的是N=W+R-1,面试官表示就是这样
回复 支持 反对

使用道具 举报

 楼主| 海拔2纳米 发表于 2014-12-10 14:51:34 | 显示全部楼层
nibuxing 发表于 2014-12-10 11:50
不是吧,我看楼主好像面的不错,怎么就fail了。。

我也不能理解,amazon说不能给feedback
回复 支持 反对

使用道具 举报

 楼主| 海拔2纳米 发表于 2014-12-10 14:52:00 | 显示全部楼层
Adeath 发表于 2014-12-10 09:54
我靠  这么快就出结果  
没事你还有fb  加油拿下  比Amazon爽多了

这回FB是必须得拿下了
回复 支持 反对

使用道具 举报

nibuxing 发表于 2014-12-10 23:05:38 | 显示全部楼层
海拔2纳米 发表于 2014-12-10 14:51
我也不能理解,amazon说不能给feedback

看来录取还挺看运气,不过可能的确大神众多,拿offer也不那么简单。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
FB加油!
回复 支持 反对

使用道具 举报

skip2myloucn 发表于 2014-12-10 23:38:12 | 显示全部楼层
请问楼主polite number这个题是怎么解的?没有太想明白,感觉肯定应该用dp,但是没太想清楚。谢谢!
祝楼主顺利拿下FB!
回复 支持 反对

使用道具 举报

 楼主| 海拔2纳米 发表于 2014-12-11 02:03:47 | 显示全部楼层
skip2myloucn 发表于 2014-12-10 23:38
请问楼主polite number这个题是怎么解的?没有太想明白,感觉肯定应该用dp,但是没太想清楚。谢谢!
祝楼 ...
. more info on 1point3acres.com
从1+2+3+4+...开始逐个试,直到当前结果大于等于target为止。这个sum值要保留着,下次你需要试的是2+3+4+...,所以只要把当前的sum减去1就行了。在下一次是把当前sum减去2,以此类推。
要维护当前的sum值以及本次累加开始的起点
回复 支持 反对

使用道具 举报

broccoli 发表于 2014-12-11 02:51:53 | 显示全部楼层
海拔2纳米 发表于 2014-12-11 02:03
-google 1point3acres从1+2+3+4+...开始逐个试,直到当前结果大于等于target为止。这个sum值要保留着,下次你需要试的是2+3+4+ ...

楼主的意思是不是就是记录一下头和尾,i和j,每次这个(i+...+j)比target大就去个头,比target小就加个尾,跟target相等就保存结果,然后再加个尾。。。复杂度是O(n)?.鐣欏璁哄潧-涓浜-涓夊垎鍦
回复 支持 反对

使用道具 举报

broccoli 发表于 2014-12-11 03:10:37 | 显示全部楼层
我感觉还有种方法。要求的就是满足((i+j)(j-i+1)/2==target)的(i,j)对的个数,(i+j)和(j-i+1)奇偶性不同,并且(i+j)>(j-i+1)。那就把target乘以2,然后看能拆成多少组“奇数x偶数”,就是答案了。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| 海拔2纳米 发表于 2014-12-11 03:11:56 | 显示全部楼层
broccoli 发表于 2014-12-11 02:51
楼主的意思是不是就是记录一下头和尾,i和j,每次这个(i+...+j)比target大就去个头,比target小就加个尾 ...

我没有记录尾,只记了头。一个循环i从1到n/2+1, 每个循环把sum加上当前的i,如果当前sum小于n就i++进入下一个循环。如果大于等于n就用sum减去头元素,进入下一个循环(这里i不increment,进入下一个循环以后当前sum也不再加上i)
回复 支持 反对

使用道具 举报

broccoli 发表于 2014-12-11 04:52:45 | 显示全部楼层
海拔2纳米 发表于 2014-12-11 03:11
我没有记录尾,只记了头。一个循环i从1到n/2+1, 每个循环把sum加上当前的i,如果当前sum小于n就i++进入 ...

哦对,一个意思,你这里的i就是尾咯,如果小于n就increment。
楼主加油,一起去fb
回复 支持 反对

使用道具 举报

guoshuheng 发表于 2014-12-11 10:01:34 | 显示全部楼层
broccoli 发表于 2014-12-11 03:10
我感觉还有种方法。要求的就是满足((i+j)(j-i+1)/2==target)的(i,j)对的个数,(i+j)和(j-i+1)奇偶性不同 ...

这个方法好
回复 支持 反对

使用道具 举报

alex2013 发表于 2014-12-11 10:27:30 | 显示全部楼层
请问LZ你Amazon也是只面了3轮然后又要求补一轮电话面?我是上周三onsite的,也是schedule问题导致第二面没有面,三面搞完了,但是没有人通知说要补面额。。
回复 支持 反对

使用道具 举报

nibuxing 发表于 2014-12-11 11:04:32 | 显示全部楼层
alex2013 发表于 2014-12-11 10:27
请问LZ你Amazon也是只面了3轮然后又要求补一轮电话面?我是上周三onsite的,也是schedule问题导致第二面没 ...
. 1point 3acres 璁哄潧
我就是上周三晚上到你房间来请教的那位同学。。。
请问大概多久会出结果啊。。。
回复 支持 反对

使用道具 举报

alex2013 发表于 2014-12-11 11:24:49 | 显示全部楼层
nibuxing 发表于 2014-12-11 11:04
我就是上周三晚上到你房间来请教的那位同学。。。
请问大概多久会出结果啊。。。

竟然被你发现了哈哈。我现在还没有结果额,但是跟我一起去面的一个同学已经收到拒信。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 13:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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