一亩三分地论坛

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

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

amazon 面经

[复制链接] |试试Instant~ |关注本帖
l0ngc0ng 发表于 2013-11-26 01:22:31 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Amazon - 内推 - 在线笔试 |Other

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

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

x
[size=14.44444465637207px]1.check whether there is a loop in the linked list. (it is the same with leetcode. very easy) . 鍥磋鎴戜滑@1point 3 acres
[size=14.44444465637207px]2.Find the K closest points to the origin in 2D plane, given an array containing N points. . from: 1point3acres.com/bbs
[size=14.44444465637207px]这一题的基本思想肯定是使用一个大小为K的bomK(大顶堆). 遍历所有N个点,如果当前点到原点的距离小于堆顶的值,则入堆,最后输出堆里面的元素即可..1point3acres缃
[size=14.44444465637207px]由于N远大于K,而此时最费时的工作是计算x2 + y2, 所有要找到一个herious,大概的确定范围然后在对这个范围里面的元素做复杂计算。
[size=14.44444465637207px]herious的方法有很多,可以用欧拉distance(x + y),或者 max(x, y)。
[size=14.44444465637207px]想法是这样的,先使用max(x, y) 来排序最开始所有的点,sort array。
[size=14.44444465637207px]然后 使用大顶堆来做。. Waral 鍗氬鏈夋洿澶氭枃绔,
[size=14.44444465637207px]当最后发现大顶堆的堆顶的元素的x2 + y2 <= 来到的元素的max(x, y)要小的话就停止。此时堆里面的元素即结果。

评分

1

查看全部评分

 楼主| l0ngc0ng 发表于 2013-11-26 01:35:32 | 显示全部楼层
还有一问:
Given two lists of integers, write a function that returns a list that contains only the intersection (elements that occur in both lists) of the two lists.
The returned list should only contain unique integers, no duplicates.
使用hashmap来做,key为array的element的值。 对第一个array使用hashmap。然后遍历第二个,如果element is in hashmap, add it to result list。
最后返回result即可。

感觉amazon的online coding,不是那么难, 基本上都是leetcode上面的原题。
但是第二题比较tricky。 可以放到最后再做,先做其他两题。
回复 支持 反对

使用道具 举报

GUIXIANG 发表于 2013-12-27 10:45:55 | 显示全部楼层
赞楼主。顺便问一下,amazon的online coding要求多长时间?
回复 支持 反对

使用道具 举报

zeyu 发表于 2013-12-30 04:40:31 | 显示全部楼层
回复 支持 反对

使用道具 举报

GUIXIANG 发表于 2013-12-30 06:41:36 | 显示全部楼层
zeyu 发表于 2013-12-30 04:40
应该是3题共90min, 时间自由分配。

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴谢谢~关于第二题,还想请教一下,使用大顶堆,是需要自己另写一个堆的类自己实现吗?
回复 支持 反对

使用道具 举报

zeyu 发表于 2013-12-30 07:24:48 | 显示全部楼层
GUIXIANG 发表于 2013-12-30 06:41
谢谢~关于第二题,还想请教一下,使用大顶堆,是需要自己另写一个堆的类自己实现吗?

我用的java, 建一个heap. override compartor就好了。网上找找好像有很多解法
回复 支持 反对

使用道具 举报

readman 发表于 2013-12-30 07:49:59 | 显示全部楼层
为毛你是2D 第三题我怎么拿到过是3D...

补充内容 (2013-12-30 07:50):
第二题

补充内容 (2013-12-30 07:50):
而且不是原点, 是任意given点
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 15:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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