一亩三分地论坛

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

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

amazon 1/22 onsite

[复制链接] |试试Instant~ |关注本帖
zhangqianqian 发表于 2015-1-23 09:34:31 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Amazon - 网上海投 - Onsite |Other

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

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

x
四轮都是印度小哥,个别口音有点重,不过都很耐心,很nice

第一轮:设计一个truck tracking system,要求实现查询truck的地点,每天的行程之类的。一开始写了一个truck class,然后在引导下一点一点的增加功能,然后问了下database 的table 应该有哪些东西。之后问了个算法题 给一个array 找出里面出现奇数次的数字。我先用hashmap, 后来用int[],最后小哥说 no extra space,卡住,然后就结束了。
.1point3acres缃
第二轮:linkedlist 每个节点多一个random pointer,问怎么复制,hashmap,很简单,没让写代码。给一个平方数,求平方根。就/2 /2 /2。。。 log(n)的复杂度

第三轮:问了个循环列表,删除指定节点,写完让想一些edge case 测试一下代码正确性,很快就结束了,但是没到时间,之后就一直聊天,聊project。感觉这个小哥不是很健谈。

第四轮:给你一个array,不用循环把所有元素复制到另一个array里,用recursive,然后问了个火箭打彗星,火箭每次发射之后需要五分钟准备时间,雷达会监控彗星出现的距离,每个火箭只能打最近的一个彗星,问用什么data structure 记录彗星的情况,要求时间复杂度O(1)的,不会,然后他说换一个题吧,就让写了个quick sort伪代码,写完一起举了两个例子测试了一下。然后结束。离开大楼的时候旁敲侧击地问表现怎么样,最后他说了个 you did good,哈哈。是对女生要求低吗
. 1point 3acres 璁哄潧
还有一题不记得哪一轮了,给了一个tree 说这是一个parking lot,每个节点是一个spot,你在root,要把每个spot的灯泡换一下,每次只能移到相邻的节点,换完以后不用回到root,怎样跑的距离最短。n是node个数,2n-2-depth。.鏈枃鍘熷垱鑷1point3acres璁哄潧

. 鍥磋鎴戜滑@1point 3 acres

评分

1

查看全部评分

CrossTheWall 发表于 2015-1-23 12:25:06 | 显示全部楼层
Array找出奇数次的数,不让用计数法的话, 估计就得用异或之后再分治的思路,他说出现奇数次的数有几个了没?
火箭打彗星这个,ambiguity有点多,O(1)时间找最近的Node总觉得不太可能
回复 支持 反对

使用道具 举报

 楼主| zhangqianqian 发表于 2015-1-23 12:29:27 | 显示全部楼层
CrossTheWall 发表于 2015-1-23 12:25. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
Array找出奇数次的数,不让用计数法的话, 估计就得用异或之后再分治的思路,他说出现奇数次的数有几个了 ...

Array 他没说有几个 但是肯定不是只有一个 只说跟用 int[]差不多 可以在原来的数组上改 给了数字范围0-n
火箭打彗星 提了下heap 不过我不会 就跳过了
回复 支持 反对

使用道具 举报

ran784388220 发表于 2015-1-23 13:04:39 | 显示全部楼层
第二道题能说说解法么,题懂了solution还是没get到。最后一个parking lot是用bfs么
回复 支持 反对

使用道具 举报

 楼主| zhangqianqian 发表于 2015-1-23 13:23:05 | 显示全部楼层
第二题就是先普通复制linkedlist,读一个节点,创建一个新节点,并且把原节点和复制节点存到hashmap里面,key是原节点,value 是复制节点,这样一遍完成就是复制了普通的linked list,random pointer 都是null,然后再从头开始,读每个节点和它的random,在hashmap里找到它们新链表里的对应节点,把random关系复制过去。

parking lot不是bfs,因为每个分支到头了还是要回到父节点,然后访问另一条分支,所以每个edge要经过两次,除了最后访问的一条分支,只需要一次,因为访问完不用回root,就把深度最大的那条分支留到最后访问就可以了
回复 支持 反对

使用道具 举报

CrossTheWall 发表于 2015-1-23 14:56:35 | 显示全部楼层
zhangqianqian 发表于 2015-1-23 12:29
Array 他没说有几个 但是肯定不是只有一个 只说跟用 int[]差不多 可以在原来的数组上改 给了数字范围0-n  ...

噢,他的意思是用位向量作映射啊(因为给了数值范围)。。。还不如用Hashmap科学呢。不过看这架势你拿到offer应该挺有戏的
回复 支持 反对

使用道具 举报

wyni18 发表于 2015-2-25 09:09:47 | 显示全部楼层
最后那个换灯泡的不是很会诶,能详细解释下吗?
回复 支持 反对

使用道具 举报

applepie11 发表于 2015-4-1 06:20:18 | 显示全部楼层
第一轮那个,inplace排序然后再数?其实不用排序也行,反正得把一样的数搞在一起,排序最直接了反正
回复 支持 反对

使用道具 举报

juliusjun 发表于 2015-7-20 11:16:06 | 显示全部楼层
zhangqianqian 发表于 2015-1-23 13:23
第二题就是先普通复制linkedlist,读一个节点,创建一个新节点,并且把原节点和复制节点存到hashmap里面,k ...

这也不是最优方法啊!果然有性别优势
回复 支持 反对

使用道具 举报

会编程的猪先生 发表于 2015-7-26 04:25:04 | 显示全部楼层
第一题那个遍历数组,把数组中的array[array[i]]*-1,最后看哪些index里面的是负数
回复 支持 反对

使用道具 举报

269644943 发表于 2016-2-19 09:01:36 | 显示全部楼层
会编程的猪先生 发表于 2015-7-26 04:25
第一题那个遍历数组,把数组中的array[array]*-1,最后看哪些index里面的是负数

你好,能解释下这题吗? 不太懂
回复 支持 反对

使用道具 举报

269644943 发表于 2016-2-19 09:05:01 | 显示全部楼层
269644943 发表于 2016-2-19 09:01. more info on 1point3acres.com
你好,能解释下这题吗? 不太懂

如果是这个数组, {1, 2, 100, 100, 1, 3,5}, 你这方法不对的, a[2] = 100, a[a[2]] 不就出界了吗?
回复 支持 反对

使用道具 举报

会编程的猪先生 发表于 2016-6-21 11:38:27 | 显示全部楼层
269644943 发表于 2016-2-19 09:05
如果是这个数组, {1, 2, 100, 100, 1, 3,5}, 你这方法不对的, a[2] = 100, a[a[2]] 不就出界 ...

你说的有道理 不过不知道楼主有没有把条件说清楚
回复 支持 反对

使用道具 举报

facao 发表于 2016-7-7 06:29:33 | 显示全部楼层
269644943 发表于 2016-2-19 09:05. more info on 1point3acres.com
如果是这个数组, {1, 2, 100, 100, 1, 3,5}, 你这方法不对的, a[2] = 100, a[a[2]] 不就出界 ...

有一个条件是说数介于 0 - n。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 03:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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