推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 3976|回复: 13
收起左侧

Amazon 2.8 9AM 面经

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

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

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

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

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)].........]-google 1point3acres
2.给一个array,找出longest consecutive subsequence, lc hard原题。
两道题目都要求说test case, time complexity.

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

. from: 1point3acres.com/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
第一题是4sum嘛。。。。感觉好难啊。。。。lz是怎么做的???
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
建造一个HashMap<Integer,List<pair>>
Integer存两个每两个元素的sum, List<pair>存满足这个sum的所有pair
class pair {
int i;. Waral 鍗氬鏈夋洿澶氭枃绔,
int j;
public pair(int i,int j){. 1point 3acres 璁哄潧
this.i = i;
this.j = j;
}
}
. from: 1point3acres.com/bbs

回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

假设现在数组是 1 到 n
那么和的取值范围就是 3 到 2n-1
和为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

回复 支持 反对

使用道具 举报

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的类型是什么

第一题: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哇?

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-20 06:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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