一亩三分地论坛

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

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

Amazon 2.8 9AM 面经

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

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

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

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

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~~~. From 1point 3acres bbs

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷


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

评分

3

查看全部评分

猪小乐 发表于 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)
数组里有重复元素吗,有重复的元素的先排序吧
回复 支持 反对

使用道具 举报

 楼主| 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.1point3acres缃
第一题是4sum嘛。。。。感觉好难啊。。。。lz是怎么做的???

建造一个HashMap<Integer,List<pair>>
Integer存两个每两个元素的sum, List<pair>存满足这个sum的所有pair. From 1point 3acres bbs
class pair {
int i;
int j;
public pair(int i,int j){
this.i = i;
this.j = j;. Waral 鍗氬鏈夋洿澶氭枃绔,
}
}

. 鍥磋鎴戜滑@1point 3 acres
回复 支持 反对

使用道具 举报

yrfzh 发表于 2016-2-11 11:24:17 | 显示全部楼层
aangel 发表于 2016-2-11 10:20. 1point3acres.com/bbs
建造一个HashMap
Integer存两个每两个元素的sum, List存满足这个sum的所有pair
class pair {
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
诺!!!明白了!!!这个方法应该是O(n^2)的!!!
回复 支持 反对

使用道具 举报

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

假设现在数组是 1 到 n.鏈枃鍘熷垱鑷1point3acres璁哄潧
那么和的取值范围就是 3 到 2n-1. 1point 3acres 璁哄潧
和为3的有一个,不输出。
和为5的有两个,输出C(2,2)个pair<pair,pair>
和为7的有三个,输出C(3,2)个
和为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 3acres 璁哄潧
回复 支持 反对

使用道具 举报

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

使用道具 举报

处川 发表于 2016-2-15 05:16:41 | 显示全部楼层
yrfzh 发表于 2016-2-11 11:24.鏈枃鍘熷垱鑷1point3acres璁哄潧
诺!!!明白了!!!这个方法应该是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的类型是什么
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第一题: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
那里面这个(a,b)是个String,还是pair哇?
. From 1point 3acres bbs
a,b代表的都是数字,我用的python里面tuple表示的
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 21:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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