一亩三分地论坛

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

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

Amazon实习面经2.20

[复制链接] |试试Instant~ |关注本帖
momosmith 发表于 2015-2-26 12:13:36 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 实习@Amazon - 内推 - 技术电面 |Other

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

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

x
1月底内推,三天后回复…oa和电面隔了不到两周…速战速决
上周五下午电面,白人小哥,名字叫Travis.
1. 双方自我介绍,聊简历和project
2. 有一些customer的数据,每个customer都有一个rate,给两个sorted customer list
     我说写个comparator,新建个list,放进去就自动排好了(想得美),小哥说不不不直接sort,可以arraylist,可以linkedlist,然后写代码
     (Leetcode:   Merge two linked list)
     追问:时空复杂度。如果数据是immutable的,时空复杂度还一样么?
3. OO题. 有个Shape父类,设计Circle, Rectangle, Square…子类. 畅所欲言就好了,主要考继承和多态.
4. 什么是Balanced Binary Search Tree? 为什么要Balanced的?应用有哪些?
5. 又有一些customer的数据,你想要怎么存?
    在给答案之前问了: 数据有多少?(多)  
    我给了两个:BST(方便插入,排序)和TreeSet(进一步方便遍历,打印名单这类…).  其实这类问题应该多问些具体要求的,比如quick insert?quick search? traversal?
    小哥追加了要求:不要求排序,只要求快速插入
     给了arraylist. 追问:run out of space怎么办? 我说拆成几个arraylist,组成个arraylist<arraylist>
     追问:还是有run out of space的问题…最后磨蹭了半天,讨论了一会儿,给了linkedlist,因为只用存reference…
6. 问问题环节…小哥说这周二或周三出结果…已经周三了还没信…发面经攒点人品先…
   自我感觉面的题挺简单的,但答得不太好…还是求offer吧…再求点面试…


补充内容 (2015-3-7 04:13):
3.5 收到offer

评分

4

查看全部评分

本帖被以下淘专辑推荐:

hopeisfree 发表于 2015-2-27 10:41:24 | 显示全部楼层
求教一下,arraylist的insert应该不快吧,arraylist底层用数组实现,虽然寻址O(1),但是插入的话(不在头尾)要把插入之后的数据都依次复制到下一个,应该不快吧,如果只是考虑insert不考虑寻址的话感觉还是linkedlist快,O(1)的复杂度。
回复 支持 0 反对 1

使用道具 举报

aifer 发表于 2015-2-26 12:26:03 | 显示全部楼层
放心吧,基本周三周四没结果就直接offer了
回复 支持 反对

使用道具 举报

 楼主| momosmith 发表于 2015-2-26 12:36:52 | 显示全部楼层
aifer 发表于 2015-2-26 12:26
放心吧,基本周三周四没结果就直接offer了

是么…那就求明天不要收到任何消息了…
回复 支持 反对

使用道具 举报

laonawuli 发表于 2015-2-26 13:22:36 | 显示全部楼层
momosmith 发表于 2015-2-26 12:36. visit 1point3acres.com for more.
是么…那就求明天不要收到任何消息了…

我也希望明天没有消息。。。但是事实是,有的人offer是周二周三出,也有拒信是周五出,所以没有啥代表性啊...
回复 支持 反对

使用道具 举报

 楼主| momosmith 发表于 2015-2-26 14:09:18 | 显示全部楼层
laonawuli 发表于 2015-2-26 13:22
我也希望明天没有消息。。。但是事实是,有的人offer是周二周三出,也有拒信是周五出,所以没有啥代表性 ...

那就一边等一边面别家……
回复 支持 反对

使用道具 举报

brian8759 发表于 2015-2-27 06:44:59 | 显示全部楼层
追问:时空复杂度。如果数据是immutable的,时空复杂度还一样么?

这个追问,楼主怎么回答的?
回复 支持 反对

使用道具 举报

 楼主| momosmith 发表于 2015-2-27 06:55:59 | 显示全部楼层
brian8759 发表于 2015-2-27 06:44.鏈枃鍘熷垱鑷1point3acres璁哄潧
追问:时空复杂度。如果数据是immutable的,时空复杂度还一样么?
.1point3acres缃
这个追问,楼主怎么回答的?

我猜他是想问arraylist的情况吧…immutable的话merge的时候只能创建新对象,所以空间复杂度会变O(n)
回复 支持 反对

使用道具 举报

baiyan_305 发表于 2015-2-27 07:50:42 | 显示全部楼层
刚面完,问题和你一模一样~~也是这个小哥
回复 支持 反对

使用道具 举报

 楼主| momosmith 发表于 2015-2-27 10:45:40 | 显示全部楼层
hopeisfree 发表于 2015-2-27 10:41
求教一下,arraylist的insert应该不快吧,arraylist底层用数组实现,虽然寻址O(1),但是插入的话(不在头尾) ...

arraylist是动态扩容的,不是每次插入都需要复制
回复 支持 反对

使用道具 举报

 楼主| momosmith 发表于 2015-2-27 10:45:50 | 显示全部楼层
baiyan_305 发表于 2015-2-27 07:50
刚面完,问题和你一模一样~~也是这个小哥
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
祝你好运~!
回复 支持 反对

使用道具 举报

hopeisfree 发表于 2015-2-27 10:53:41 | 显示全部楼层
momosmith 发表于 2015-2-27 10:45
arraylist是动态扩容的,不是每次插入都需要复制
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
和动态扩容无关吧。动态数组的插入复杂度也是O(n)吧。比如 1 2 3 4 5 null null null null 这样一个arraylist, 你在3 和 4 之间插入6, 那么操作应该是5 向后复制到null,4复制到5,原来4的地方存6。 但是用linkedlist的话就不需要有4和5的那两步复制,单纯断链插入就可以了。如果是一个1000个数据的list,你在第10与11各数之间插入一个数,arraylist复制的开销是惊人的啊。还是我对arraylist的动态扩容理解有问题?
回复 支持 反对

使用道具 举报

 楼主| momosmith 发表于 2015-2-27 12:05:04 | 显示全部楼层
hopeisfree 发表于 2015-2-27 10:53
和动态扩容无关吧。动态数组的插入复杂度也是O(n)吧。比如 1 2 3 4 5 null null null null 这样一个array ...

不要求排序嘛…就插末尾呗…没有需要插到中间的情况
回复 支持 反对

使用道具 举报

 楼主| momosmith 发表于 2015-2-27 12:05:43 | 显示全部楼层
hopeisfree 发表于 2015-2-27 10:53
和动态扩容无关吧。动态数组的插入复杂度也是O(n)吧。比如 1 2 3 4 5 null null null null 这样一个array ...

不过这位同学,你说的没错~
回复 支持 反对

使用道具 举报

NicklX 发表于 2015-3-10 23:05:44 | 显示全部楼层
话说为何要在中间插入?中间插入 n 个 runtime 怎么说都是n^2吧 如果 list
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴如果是 add 的话两个 list 表现差不多,但如果space 吃紧可以选 linkedlist
之前玩这两个 list (自制)的时候发现很难判断谁比较适合大量数据 根据插入1MILLION 次东西的 runtime 来看- -
回复 支持 反对

使用道具 举报

 楼主| momosmith 发表于 2015-3-11 04:03:23 | 显示全部楼层
NicklX 发表于 2015-3-10 23:05. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
话说为何要在中间插入?中间插入 n 个 runtime 怎么说都是n^2吧 如果 list
如果是 add 的话两个 list 表现 ...
. 鍥磋鎴戜滑@1point 3 acres
开放性讨论,你的想法都可以跟面试官讲
回复 支持 反对

使用道具 举报

fornever7 发表于 2015-3-11 08:59:52 | 显示全部楼层
lz,不太明白你的最后一道题...为啥linkedlist比较省空间呢?
回复 支持 反对

使用道具 举报

007rf 发表于 2015-3-23 21:10:04 | 显示全部楼层
渣渣跟着学习了
回复 支持 反对

使用道具 举报

i1777274 发表于 2015-12-2 07:24:56 | 显示全部楼层
ding ding dinga
回复 支持 反对

使用道具 举报

i1777274 发表于 2015-12-2 07:25:47 | 显示全部楼层
626-523-5468
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 12:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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