一亩三分地论坛

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

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

Amazon 热辣辣的面经~

[复制链接] |试试Instant~ |关注本帖
sam2015 发表于 2016-1-15 03:13:20 | 显示全部楼层 |阅读模式

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

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

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

x
今天中午面亚麻 发现是个三哥,听力捉急一上来问我之前做的项目,还选了个最水的项目。。。只能发挥想象力跟他解释了
然后就是编程题,是返回非排序n个元素数组里面所有k个最大的元素。。。
还好昨天特意看了一下两种解法。。。.1point3acres缃
对于quick selection的解法,上次面linkedin自告奋勇说还有第二种解法,结果面试官不知道还有这种解法,就跪了。。。-google 1point3acres
于是这次就更小心啦。。。
没想到三哥一上来说两种解法,让我说两种的复杂度。。。
然后让我选一个。。。是个坑吗。。。
我推回去让面试官选。。他说用heap。。。简单呀
. from: 1point3acres.com/bbs 写完后,他说让我implement priorityqueue,这。。。还有这种玩法。。。我也醉了。。。让我重写一个heap嘛!!!
时间明显不够,他让我写个最简单的poll()。。。
这。。。之前算法课写过,但是没真正写过呀。。。于是只好硬着头皮写啦。。。
虽然中间有几个bug,最后时刻还是写出来了。。。. From 1point 3acres bbs
最后问了几个小问题结束啦。。。

求实习求RP~

评分

2

查看全部评分

本帖被以下淘专辑推荐:

leixiang5 发表于 2016-1-15 03:16:36 | 显示全部楼层
祝楼主拿到offer。。如果去amazon 实习的话。欢迎加我们2016 summer群。
回复 支持 反对

使用道具 举报

 楼主| sam2015 发表于 2016-1-15 03:19:01 | 显示全部楼层
leixiang5 发表于 2016-1-15 03:16
祝楼主拿到offer。。如果去amazon 实习的话。欢迎加我们2016 summer群。
-google 1point3acres
你已经定了去亚麻了吗?恭喜恭喜呀!
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-1-15 03:20:53 | 显示全部楼层
sam2015 发表于 2016-1-15 03:19
你已经定了去亚麻了吗?恭喜恭喜呀!

是的。希望楼主能一起。
回复 支持 反对

使用道具 举报

WilliamShi1 发表于 2016-1-15 04:01:33 | 显示全部楼层
k个 还是k th呢 谢谢楼主
回复 支持 反对

使用道具 举报

 楼主| sam2015 发表于 2016-1-15 05:45:32 | 显示全部楼层
WilliamShi1 发表于 2016-1-15 04:01
k个 还是k th呢 谢谢楼主

是k个~
回复 支持 反对

使用道具 举报

linweihua0 发表于 2016-1-15 06:16:54 | 显示全部楼层
这个priorityqueue 要写generic的吗 就是像这个 PriorityQueue.java
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-15 06:26:17 | 显示全部楼层
Implements priority queue??????
还是写个comparator就好了
回复 支持 反对

使用道具 举报

 楼主| sam2015 发表于 2016-1-15 06:26:36 | 显示全部楼层
linweihua0 发表于 2016-1-15 06:16. from: 1point3acres.com/bbs
这个priorityqueue 要写generic的吗 就是像这个 PriorityQueue.java

重写heap那部分我没写 怕写多错多了。。。
回复 支持 反对

使用道具 举报

 楼主| sam2015 发表于 2016-1-15 06:36:23 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-15 06:26
Implements priority queue??????
还是写个comparator就好了

是implement priorityqueue。。。
这道题用最小堆,priorityqueue默认最小堆,不用重写comparator呀。。。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-15 06:37:47 | 显示全部楼层
sam2015 发表于 2016-1-15 06:36. from: 1point3acres.com/bbs
是implement priorityqueue。。。
这道题用最小堆,priorityqueue默认最小堆,不用重写comparator呀。。 ...
. 1point3acres.com/bbs
我知道阿。。有人让写priorityqueue..好奇怪阿。
lz能分享下,你大概都写的什么么。感觉这玩意,写个完整的,要很长时间。
quick selection怎么维护k个大的?
回复 支持 反对

使用道具 举报

 楼主| sam2015 发表于 2016-1-15 07:08:07 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-15 06:37
我知道阿。。有人让写priorityqueue..好奇怪阿。. Waral 鍗氬鏈夋洿澶氭枃绔,
lz能分享下,你大概都写的什么么。感觉这玩意,写个完 ...

重写heap的我也就写了poll()函数额。。。其他的没写
至于quick selection,他没让我实现,但是我的大概想法是当pivot大于等于n - k的时候,就输出这个数到数组里。。。
回复 支持 反对

使用道具 举报

lpx1989 发表于 2016-1-15 08:52:28 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-14 18:26
Implements priority queue??????
还是写个comparator就好了

我有点好奇你们每次说的用heap解题简单,是要写个heapsort么,还是指什么别的?
回复 支持 反对

使用道具 举报

leilater 发表于 2016-1-16 00:04:35 | 显示全部楼层
sam2015 发表于 2016-1-15 06:36
是implement priorityqueue。。。
这道题用最小堆,priorityqueue默认最小堆,不用重写comparator呀。。 ...
. from: 1point3acres.com/bbs
priority queue默认是最大堆吧?

用最大堆的方法:用priority_queue默认的刚好就是最大堆。建大小为N的堆,弹出的第K个值就是第K大的。时间复杂度:O(N) + O(KlogN)

用最小堆的方法: 用前K个元素建大小为K的最小堆,用剩余N-K个输入维护最小堆,若新来元素比堆顶元素大,则弹出,插入新元素。这样这个最小堆存储的就是前K大的数,堆顶就是第K大。

如有不对请指正。
回复 支持 反对

使用道具 举报

 楼主| sam2015 发表于 2016-1-16 02:39:13 | 显示全部楼层
leilater 发表于 2016-1-16 00:04
priority queue默认是最大堆吧?

用最大堆的方法:用priority_queue默认的刚好就是最大堆。建大小为N ...

PriorityQueue默认是最小堆的呀
具体分析在这里 https://leetcode.com/discuss/36966/solution-explained
回复 支持 反对

使用道具 举报

sumbo 发表于 2016-1-17 12:59:15 | 显示全部楼层
xi哥吗哈哈哈哈哈哈。肯定过的。。
回复 支持 反对

使用道具 举报

timpark4 发表于 2016-1-18 06:59:37 | 显示全部楼层
LZ 那个 n个元素数组里面所有k个最大的元素  如果用quick select 你算出的run time 是多少? O(kn)?
回复 支持 反对

使用道具 举报

iamwds 发表于 2016-1-19 17:07:33 | 显示全部楼层
lz没说 sort之后,选最大的k个这种方法了吗? 如果这种方法烙印认可的话,岂不是更简单
回复 支持 反对

使用道具 举报

iamwds 发表于 2016-1-19 18:05:15 | 显示全部楼层
楼主能否给个poll()的代码例子,学习一下,谢谢
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 08:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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