要回国了,写个简单的总结吧。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 4393|回复: 13
收起左侧

Amazon 2.8 9AM 面经

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

2016(7-9月) 码农类General 本科 实习@Amazon - 内推 - 技术电面  | Other | 其他

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

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

x
2月98号大年初一早上9点的面经,烙印面的(有一个人shadow),没有问到OOD和任何data structure,上来直接让自我介绍,说project,说challenge。两道coding题目:
1. 给一个array,找出任何满足a+b = c+d的pair,比如[1,2,3,4,5,6,7]就可以输出[[(1,7),(2,6)],[(2,6),(3,5)].........]
2.给一个array,找出longest consecutive subsequence, lc hard原题。
两道题目都要求说test case, time complexity.

欢迎大家讨论题目,提供更多思路~
求rp,求offer~~~




补充内容 (2016-2-27 09:07):
2.26拿到offer。大家加油^_^

评分

3

查看全部评分




上一篇:新的GOOGLE的OA截图,题目有小改动
下一篇:Google onsite 面经
猪小乐 发表于 2016-2-10 14:22:33 | 显示全部楼层
autumnhu 发表于 2016-2-10 13:52
我想讨论一下时间复杂度。我觉得找出相同的sum的组合之后要两两匹配,所以是O(n^3)。数组没有重复元素。

我也觉得是n^3,输出的复杂度就是立方级的,时间复杂度不可能比输出复杂度小。
回复 支持 1 反对 0

使用道具 举报

aangel 发表于 2016-2-10 10:38:24 | 显示全部楼层
第一题用HashMap来hash sum吧,两个for loop, 时间复杂度O(N^2),空间复杂度O(N^2). more info on 1point3acres
数组里有重复元素吗,有重复的元素的先排序吧
回复 支持 反对

使用道具 举报

 楼主| autumnhu 发表于 2016-2-10 13:52:48 | 显示全部楼层
aangel 发表于 2016-2-10 10:38
第一题用HashMap来hash sum吧,两个for loop, 时间复杂度O(N^2),空间复杂度O(N^2)
数组里有重复元素吗,有 ...

我想讨论一下时间复杂度。我觉得找出相同的sum的组合之后要两两匹配,所以是O(n^3)。数组没有重复元素。
回复 支持 反对

使用道具 举报

yrfzh 发表于 2016-2-11 10:02:50 | 显示全部楼层
第一题是4sum嘛。。。。感觉好难啊。。。。lz是怎么做的???
回复 支持 反对

使用道具 举报

aangel 发表于 2016-2-11 10:20:16 | 显示全部楼层
yrfzh 发表于 2016-2-11 10:02
第一题是4sum嘛。。。。感觉好难啊。。。。lz是怎么做的???

建造一个HashMap<Integer,List<pair>>
Integer存两个每两个元素的sum, List<pair>存满足这个sum的所有pair
class pair {
int i;
int j;
public pair(int i,int j){
this.i = i;
this.j = j;
}
}. 牛人云集,一亩三分地
. 1point 3acres 论坛

.1point3acres网
回复 支持 反对

使用道具 举报

yrfzh 发表于 2016-2-11 11:24:17 | 显示全部楼层
aangel 发表于 2016-2-11 10:20
建造一个HashMap
Integer存两个每两个元素的sum, List存满足这个sum的所有pair
class pair {

诺!!!明白了!!!这个方法应该是O(n^2)的!!!
回复 支持 反对

使用道具 举报

猪小乐 发表于 2016-2-13 16:21:17 | 显示全部楼层
aangel 发表于 2016-2-11 10:20. from: 1point3acres
建造一个HashMap. Waral 博客有更多文章,
Integer存两个每两个元素的sum, List存满足这个sum的所有pair
class pair {

假设现在数组是 1 到 n. more info on 1point3acres
那么和的取值范围就是 3 到 2n-1
和为3的有一个,不输出。
和为5的有两个,输出C(2,2)个pair<pair,pair>
和为7的有三个,输出C(3,2)个. 1point3acres
和为9的有四个,输出C(4,2)个
和为n+1的有n/2个,输出C(n/2,2)个
。。。
c(2,2)+c(3,2)+c(4,2)+c(5,2)+c(n/2,2)约等于 1^2+2^2+3^2+4^2+..(n/2)^2约等于(n^3)/6. 围观我们@1point 3 acres
. Waral 博客有更多文章,
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

pepero 发表于 2016-2-13 17:44:00 | 显示全部楼层
如果用hash,光输出就是立方级的, 怎么是n^2
回复 支持 反对

使用道具 举报

处川 发表于 2016-2-15 05:16:41 | 显示全部楼层
yrfzh 发表于 2016-2-11 11:24
诺!!!明白了!!!这个方法应该是O(n^2)的!!!
. 留学申请论坛-一亩三分地
这样还需要override equals()这个函数,不然会分别不出
回复 支持 反对

使用道具 举报

处川 发表于 2016-2-15 05:17:19 | 显示全部楼层
求问楼主return的类型是什么
回复 支持 反对

使用道具 举报

 楼主| autumnhu 发表于 2016-2-16 03:15:13 | 显示全部楼层
处川 发表于 2016-2-15 05:17
求问楼主return的类型是什么
. 1point 3acres 论坛
第一题:return的是类似这样的[[(a,b),(c,d)], []...]我面试的时候面试官感觉也不是特别清楚然后我就问能否这样返回他说好我就这样的
第二题:length of the longest consecutive sequence
回复 支持 反对

使用道具 举报

处川 发表于 2016-2-16 06:04:19 | 显示全部楼层
autumnhu 发表于 2016-2-16 03:15 来源一亩.三分地论坛.
第一题:return的是类似这样的[[(a,b),(c,d)], []...]我面试的时候面试官感觉也不是特别清楚然后我就问能 ...

那里面这个(a,b)是个String,还是pair哇?
回复 支持 反对

使用道具 举报

 楼主| autumnhu 发表于 2016-2-17 02:17:48 | 显示全部楼层
处川 发表于 2016-2-16 06:04. 1point3acres
那里面这个(a,b)是个String,还是pair哇?

a,b代表的都是数字,我用的python里面tuple表示的
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-27 08:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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