一亩三分地论坛

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

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

Amazon Onsite面经

[复制链接] |试试Instant~ |关注本帖
ki87uj 发表于 2015-1-12 05:18:57 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Amazon - 网上海投 - Onsite |Fail

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

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

x
今年投Amazon,很不幸,我做OA第二部分的时候还有9道题没做的情况下系统没有响应,后来不得不退出了系统。
所以没有拿到video。
. 1point 3acres 璁哄潧之后hr给了onsite面试,悲剧也就是这样发生了。
说实话,4轮面试我自我感觉不错,除了部分地方有些bug,面试官指出以后就改正了。但是最后还是挂了。

Amazon Onsite 12/4/2014

Round 1  印度面试官,说刚从印度调来2个月,口音很重。态度冷漠,对我任何问题的回答都不苟言笑,没有feedback。最后我做完题目,竟然发现他一脸不高兴的走了。

社交网络,一个房间里有很多人,有一个host,所有人都认识host,但是host不认识任何人。
你走进房间,你可以问任何一个人,你是否认识他  isKnow(A,B)
得到的回答是true 或者false
怎么样最快找出来谁是host

回答: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
Divid and Conqure
每次问两个人,如果是true,那么A肯定不是host,如果是false,那么B肯定不是host

每一次遍历,去掉一半人

写代码
-google 1point3acres

Round 2  美国老头,nice

游泳池放水问题
给了一个游泳池,要求出多少时间水池放满水。
有以下参数
size  泳池的容量
pipe[]  放水的水管,里面每个元素是注水速度,每分钟多少升水。比如pipet[3] = 20 就说明第3根管子每分钟20L水
events[]  events又是一个新的class,在下面。
. visit 1point3acres.com for more.

class events{
        enum(start,end) ev;
        time;
        pipeID;.1point3acres缃
}

一个events array比如:. 1point 3acres 璁哄潧
Action   Time    PipiID
start    10      1.鐣欏璁哄潧-涓浜-涓夊垎鍦
start    30          2
end          110         1
start    150     3
end      200     2
.......鏈枃鍘熷垱鑷1point3acres璁哄潧

要求写一个function, get_time_fillup_pool.鏈枃鍘熷垱鑷1point3acres璁哄潧

返回注满水池的时间。

我维护了两个array,一个用来判断哪些pipes当前是开着的,boolean pipe_open[]. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
一个是int sum[] 用来维护到目前为止已经注了多少水。(后来review的时候面试官认为这里只需要一个变量就行了,没必要用array)
写一个for loop,每一次循环检查一下当前的sum是不是已经超过size,如果是就return当前时间减去开始时间。
在面试官提醒下,补了到最后也未能注满水池的情况。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
.鐣欏璁哄潧-涓浜-涓夊垎鍦
Round 3  我猜是bar rasier,是一个微软跳过来的老头,职位比较高。人也nice。不过一开始理解他说的电话系统费了一些时间。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

电话系统,组pair. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

ID  Skill_ID
1   7
2   10
3   69
1   8
3   90
1   70
. Waral 鍗氬鏈夋洿澶氭枃绔,
那么有以下的pairs。
7,8. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
8,70
69,90
就是同一个id的连续相邻的两个skillid组合
要统计这一天所有的电话系统pair出现的次数,输出类似于.鐣欏璁哄潧-涓浜-涓夊垎鍦
pairs   count
7,8    500. Waral 鍗氬鏈夋洿澶氭枃绔,
8,70   100
69,90  300

我用了两个hashmap,
第一个用来记录最近一次这个id的skillid,比如如果我们在处理第4行之前,我有
Hashmap 1
1  7
2  10
3  69

那么第4行出现Id=1,查map1,就知道我应该组成pair  7,8

第二个hashmap用来存储pair和count
这里pair我用HastSet,后来讨论面试官觉得可以用"7,8"这样更节省空间
.1point3acres缃

Round 4  印度人带一个中国shadow,沟通还可以

LRU实现
要求写出. 1point 3acres 璁哄潧
add();
get();
讲一下delete()的实现

double-linkedlist需要注意更新prev和next


祝大家早日拿到满意offer


评分

6

查看全部评分

落落落 发表于 2015-1-12 07:00:46 | 显示全部楼层
楼主遇到的题不是很简单啊,没事的,还可以继续准备去其他公司
回复 支持 反对

使用道具 举报

xytan123 发表于 2015-1-12 07:42:05 | 显示全部楼层
第一题可不可以用有向图,然后toplogical sort?
回复 支持 反对

使用道具 举报

三吉 发表于 2015-1-12 07:59:18 | 显示全部楼层
觉得那个印度人是故意的呢,板着脸不说话最不爽了
回复 支持 反对

使用道具 举报

yuruofeifei 发表于 2015-1-12 08:47:21 | 显示全部楼层
....楼主考得够难的啊。。。。 难道说amazon onsite 难度也这么随机?
回复 支持 反对

使用道具 举报

everending 发表于 2015-1-17 15:34:48 | 显示全部楼层
第三题的hashmap的key应该是个list吧
回复 支持 反对

使用道具 举报

l955382 发表于 2015-1-18 05:19:47 | 显示全部楼层
LZ 你的問題不簡單啊 你已經很厲害了! 整理一下心情 知道自己哪裡沒做好 下次一定會發揮得更得!!!! 加油
回复 支持 反对

使用道具 举报

cvfox4fun 发表于 2015-1-21 12:07:35 | 显示全部楼层
我也觉得楼主很厉害了。
第一题,我只能给出O(n^2)的解答
回复 支持 反对

使用道具 举报

xiaoxin213 发表于 2015-1-22 01:59:45 | 显示全部楼层
第一题,楼主解法的时间复杂度是多少啊?
回复 支持 反对

使用道具 举报

flyaway25 发表于 2015-1-22 02:21:52 | 显示全部楼层
xytan123 发表于 2015-1-12 07:42
第一题可不可以用有向图,然后toplogical sort?

里面可能有cycle吧,lz第一题那个答案感觉就已经挺好的了。
回复 支持 反对

使用道具 举报

姑爷圈 发表于 2015-1-22 02:28:43 | 显示全部楼层
亚马逊的onsite 要怎么样啊。。。这么难
回复 支持 反对

使用道具 举报

 楼主| ki87uj 发表于 2015-1-22 15:36:05 | 显示全部楼层
第一题他问了一个问题,就是最少要问多少次才能找出host
我开始说接近于n,但是面试官坚持要我给出准确的数字,我最后回答n-1
我自己举例比如一共4个人,那就问3次可以确定,所以我觉得是n-1,但是不知道怎么证明。
所以这个题目最后的算法应该是O(n)级别的。
回复 支持 反对

使用道具 举报

落落落 发表于 2015-1-23 08:27:00 | 显示全部楼层
第一题相当于merge sort,时间复杂度应该是O(n lg n)吧
回复 支持 反对

使用道具 举报

落落落 发表于 2015-1-23 08:32:39 | 显示全部楼层
啊,不是。。。是 n(1/2 + 1/4 + 1/8 + ... 1/n),最后是O(n)...
回复 支持 反对

使用道具 举报

shinichish 发表于 2015-1-27 01:16:13 | 显示全部楼层
第一题名人算法,楼主加油!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 19:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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