一亩三分地论坛

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

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

Amazon 3/1 intern面经,发帖攒人品

[复制链接] |试试Instant~ |关注本帖
abcde_12345 发表于 2016-3-4 00:25:15 | 显示全部楼层 |阅读模式

() @ - -  |

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

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

x
面试官,三哥(求不坑)做kindle的,上来简单聊聊project和基本的data structure,然后两道easy难度的算法。。。
1. circular queue,实现insert,remove,isFull, isEmpty, 其实就是circular buffer,记住head和tail的index或者记住head和current size就行
2. binary tree 的MaxHeight其实就是求二叉树的高度。。。没错,楼主当时也是先一愣。。。以为有个坑,但问了两遍就说是这个,于是三行递归写完。。。

评分

1

查看全部评分

mchzh 发表于 2016-3-4 00:32:55 | 显示全部楼层
答这么好,三哥也没理由坑,稳拿啊
回复 支持 反对

使用道具 举报

mchzh 发表于 2016-3-4 00:33:02 | 显示全部楼层
答这么好,三哥也没理由坑,稳拿啊
回复 支持 反对

使用道具 举报

 楼主| abcde_12345 发表于 2016-3-4 22:45:14 | 显示全部楼层
楼主已经收到thank u letter,虽然一开始有点想不通,但想不通也得想通是不是。。。move on吧,祝大家offer多多,事后想想interview里的确犯了些错,可能楼主在交流方面不是那么娴熟自信,还是继续学习充实自己吧。。。
回复 支持 反对

使用道具 举报

 楼主| abcde_12345 发表于 2016-3-4 22:49:50 | 显示全部楼层
补发一下lz事后发现的不足,1.三哥问我unordered_map是不是更节省空间,我当时以为他说的是an ordered_map,所以就说了yes,可能有点年轻。。。2.写代码的时候交流不多,基本属于埋头写那种,讲道理应该和他互动一下(虽然lz想说求个树的高度你让我如何互动,哈哈)。。。希望地里的朋友能够吸取我的经验,面试慢一点,多问问面试官
回复 支持 反对

使用道具 举报

Firechaser 发表于 2016-3-4 23:14:53 | 显示全部楼层
请问一下楼主第一题有要求用什么数据结构实现吗
回复 支持 反对

使用道具 举报

 楼主| abcde_12345 发表于 2016-3-5 00:14:28 | 显示全部楼层
Firechaser 发表于 2016-3-4 23:14
请问一下楼主第一题有要求用什么数据结构实现吗
. visit 1point3acres.com for more.
没有,我用的fixed size vector
回复 支持 反对

使用道具 举报

chao_uva 发表于 2016-3-5 00:56:13 | 显示全部楼层
abcde_12345 发表于 2016-3-5 00:14
没有,我用的fixed size vector

第一题用double linked list会不会要好一点?
时间复杂度似乎要比vector要好一些
回复 支持 反对

使用道具 举报

 楼主| abcde_12345 发表于 2016-3-5 01:22:49 | 显示全部楼层
chao_uva 发表于 2016-3-5 00:56. more info on 1point3acres.com
第一题用double linked list会不会要好一点?
时间复杂度似乎要比vector要好一些

记录head和tail的index,所以insert和update时间都是constant,vector其实就是array,只是在构造函数的时候方便dynamic allocation。。。都是用index访问元素
回复 支持 反对

使用道具 举报

chao_uva 发表于 2016-3-5 01:32:07 | 显示全部楼层
abcde_12345 发表于 2016-3-5 01:22
记录head和tail的index,所以insert和update时间都是constant,vector其实就是array,只是在构造函数的时 ...

array的insert可是O(n)
我刚查了一下,vector的insert也是O(n),除非你insert在尾巴上。对于circular queue,可以保证每次都insert在尾巴上吗?如果可以的话,delete的时候需要重组array吗?
回复 支持 反对

使用道具 举报

 楼主| abcde_12345 发表于 2016-3-5 01:36:57 | 显示全部楼层
chao_uva 发表于 2016-3-5 01:32
array的insert可是O(n)
我刚查了一下,vector的insert也是O(n),除非你insert在尾巴上。对于circular qu ...

可能是我说的不清楚啊,是实现circular buffer,也就是说vector的长度固定,这里只是记录数据。。。
vector insert(n)是指变长的时候

比如buffer size 等于5, . 鍥磋鎴戜滑@1point 3 acres
0 0 0 0 0. from: 1point3acres.com/bbs
insert(1)
1 0 0 0 0
insert(2)
1 2 0 0 0
。。。
0 2 3 4 5
head = 1, tail = 4
insert(1)
1 2 3 4 5
就是说会回到queue的头部
回复 支持 反对

使用道具 举报

chao_uva 发表于 2016-3-5 01:56:23 | 显示全部楼层
abcde_12345 发表于 2016-3-5 01:36
可能是我说的不清楚啊,是实现circular buffer,也就是说vector的长度固定,这里只是记录数据。。。.1point3acres缃
vec ...

了解了。这样说的话的确是用vector最省时间和空间。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 23:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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