一亩三分地论坛

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

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

Amazon 电面 两轮 题目一起放出啦~~~

[复制链接] |试试Instant~ |关注本帖
julia1006 发表于 2015-11-24 07:06:54 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Amazon - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚刚面完amazon的二面,来把两轮的题目都发出来~~求大家的大米啊~~顺便求一下indeed oa的题目啊~~
拿到他家电面其实很不容易的,内推,自己投,拒信又内推,终于拿到店面了
一轮电面是在10月底,美国小哥,叫做josh的。问了一下简历的东西,现在做的project。然后问了数据结构的东西,hashmap是什么,时间复杂度是多少。array和linkedlist的区别,插入,提取的时间复杂度是多少。然后是coding了,coding题目我是真的没见过,跟大家分享一下,也希望能给点思路。有一个parking lot,每个车有自己的位置,input是车辆现在的位置的array和应该存放的位置的array,例如:现在位置:[A,B,C,_], 应该存放的位置[_,B,A,C],"_"代表这个位置没有车,问需要最少几步才能把车挪到他应该存放的位置,这里有一点就是如果位置上有车,不能替换,要把车先开到空地,再放,这样是两步。自己给的答案是dfs,就是找到现在这个车应该放的位置是空的好,就放,然后返回。但其实这不是正确答案,小哥可能没看出来,依然同意了我的方法,又问能不能优化,说了一种,但其实也不是正确答案。。。然后就剩十几分钟了,就问有什么问题,问了一下就挂了。. 1point 3acres 璁哄潧
但是看这题就想说好的leetcode原题呢!!!说好的简单题呢!!!真是要哭了,原以为挂了,后来过了几天来了二面通知,估计是一面面的不好吧。因为当时在外面玩,就推来推去,本来定的上周二,谁知道还被放了鸽子,最后改到了今天。是一个叫做Samir(其实应该是Samirh),recruiter省略了最后一个字母,这让我在linkedin上好找啊,以为是个三哥哥,但是接到电话发现没有口音,感觉像是美国人。whatever啦。
二面没问任何简历和project,直接题目,如下:
1.valid parenthese的变种,就是里面可能有数字和字母的,这个不难,不考虑就是了。然后是时间和空间复杂度
写完后写test case 这也不多说了. 1point3acres.com/bbs
2. 因为用到了stack,来讲一下stack是什么,有什么功能,push pop的时间复杂度。 然后是怎么去实现stack,我是用的arraylist的想法(我其实也不确定,但是觉得可以行),就跟她讲了一下怎么取implement,他表示认同
3.two sum变种,1)可能有duplicate 2)不要返回index,要数字 3)unsorted,这个跟leetcode一样 4)正负数都可能存在,这里写返回就比较麻烦了,我就说throw exception吧,throw这块不太好,只能努力写了,而且exception的名字还不太记得,估计是蒙对了,他也没说什么 5)找到就返回,这个也跟leetcode一样。 这道题因为存在duplicate,就用了hashset。
4.用了hashset就问了一下为什么用,说contains(key)的时间复杂度是多少,先开始打错了,说成o(n)了,他就问确定吗,马上改过来了。然后又问为什么是O(1),然后我就说道了hashcode(),我真是觉得自己就是把自己往圈里面带啊,其实这块不好的,只能硬着头皮上了,又问了下hashcode()怎么得到,如果你编写这个method你用什么返回,然后是说两个string object的内容一样,hashcode一样嘛,那是没有一样的,给他解释了一下,感觉还算满意。
5.问如何用刚才写的two sum的代码写出three sum,因为时间不多了,他就说快速写一下主要部分就好了。 最后十分钟就是我问问题。总体觉得今天这面试算是最rp的一次了,问了这么多原题,我真的要说,自从有技术面以来,就几乎没有问到过原题,感觉真是老天开眼了。到今天为止所有面试都结束了。希望可以拿到onsite的吧。。。

鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2015-12-9 23:27):
感恩节后催了一下,拿到了onsite了

本帖被以下淘专辑推荐:

乳大未必有奶 发表于 2015-11-24 15:50:39 | 显示全部楼层
lz 是跳槽的么?没做oa直接电面?
回复 支持 反对

使用道具 举报

 楼主| julia1006 发表于 2015-11-24 23:52:29 | 显示全部楼层
乳大未必有奶 发表于 2015-11-24 15:50.鏈枃鍘熷垱鑷1point3acres璁哄潧
lz 是跳槽的么?没做oa直接电面?

不是啊 是内推的 没做oa
回复 支持 反对

使用道具 举报

hohojoy 发表于 2015-12-9 17:30:20 | 显示全部楼层
第一题好奇怪啊。。不是只要有空缺,最少步数都是预期位置和本来位置不一样的位置数量吗。。。一个空缺和两个空缺没区别吧。。

补充内容 (2015-12-9 17:31):
请问下楼主,是不是要考虑搜索位置的时间?
.1point3acres缃
补充内容 (2015-12-9 17:33):
还有,为啥有duplicate就用hash?sort之后双指针不是一样的做吗?

补充内容 (2015-12-9 17:37):
哦,估计还要求O(n)吧~
回复 支持 反对

使用道具 举报

 楼主| julia1006 发表于 2015-12-9 23:13:06 | 显示全部楼层
hohojoy 发表于 2015-12-9 17:30
第一题好奇怪啊。。不是只要有空缺,最少步数都是预期位置和本来位置不一样的位置数量吗。。。一个空缺和两 ...

第一题,这个例子是可以,不过有的例子就不是,这也就是为什么后来我发现我的做法其实也不太可行,例子:现在位置:[A,B,C,_],原始位置:[B,C,A,_],这样子你会发现即使有空位置,但是其他车辆都变了位置了,所以不是3步到达,而是四步。 hashset那个,你可以sort,但是sort的话复杂度就要nlogn了,但是我用hashset一次遍历就好,不是不行,只是不是最优。
回复 支持 反对

使用道具 举报

hohojoy 发表于 2015-12-10 03:46:52 | 显示全部楼层
julia1006 发表于 2015-12-9 23:13. 1point3acres.com/bbs
第一题,这个例子是可以,不过有的例子就不是,这也就是为什么后来我发现我的做法其实也不太可行,例子: ...

[A,B,C,_] [B,C,A,_] 这个应该算corner case吧?
回复 支持 反对

使用道具 举报

 楼主| julia1006 发表于 2015-12-10 04:01:41 | 显示全部楼层
hohojoy 发表于 2015-12-10 03:46
[A,B,C,_]  这个应该算corner case吧?

恩 可能吧 但是我的优化方法 她就是说的这样的例子
回复 支持 反对

使用道具 举报

hison7463 发表于 2015-12-15 12:30:28 | 显示全部楼层
请问two sum那题,正负数为什么要throw exception呀?
回复 支持 反对

使用道具 举报

 楼主| julia1006 发表于 2015-12-15 15:35:45 | 显示全部楼层
hison7463 发表于 2015-12-15 12:30
请问two sum那题,正负数为什么要throw exception呀?

因为按照leetcode的话,如果没有解的话,是返回{-1,-1},但是这里返回的不是index而是数值,并且数值有可能有负数存在,这样的话你返回{-1,-1}或者任何其他答案都不能确定你这个答案是解还是说是没有找到,所以这个时候要怎么办呢?那就抛出一个异常吧,这样当你没有答案的时候,就throw an exception
回复 支持 反对

使用道具 举报

hison7463 发表于 2015-12-15 17:35:47 | 显示全部楼层
julia1006 发表于 2015-12-15 15:35
因为按照leetcode的话,如果没有解的话,是返回{-1,-1},但是这里返回的不是index而是数值,并且数值有可 ...
. from: 1point3acres.com/bbs
是诶,我犯二了,谢谢~
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-10-18 02:22:28 | 显示全部楼层
感谢楼主分享~ 不过第一题小车的这个 我有一个想法~ 不知道对不对 求大家指正~~
比如说 [A,B,C,_], 应该存放的位置[_,B,A,C],"
换成index就是
0 1 2 3 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
A B C _
_ B A C. Waral 鍗氬鏈夋洿澶氭枃绔,
记录一个变量cur 就是现在空出来的位置 不断移动需要到当前位置的车. 1point 3acres 璁哄潧
cur: 3 - > 2(c从2移动到3 2就空出来了) -> 0(下一个需要移动到2的是A, A移动出来了0就空了 ) 这时候没有车需要到位置0了
这其实可以看成linkedlist 当前node指向的是应该移动到的位置-google 1point3acres

剩下的需要检测的情况就是 [A,B,C,_] [B,C,A,_]  这样可以看成linkedlist有环 1 - > 0 - > 2 - > 1 互相指向 需要先把这个环打破 任意移动一个到空地 剩下的和上面思路一样~  
所以如果只需要返回移动的步数而不是具体过程的话 可以先检测一下有多少个这样的环 n 然后多有少个错位的位置m 结果应该就是m + n

我自己手写了几个目前没发现啥问题0.0 。。求各位指教~~.鐣欏璁哄潧-涓浜-涓夊垎鍦
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 02:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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