Amazon SDE Intern 热腾腾面经（估计跪了）

倒序浏览 · 2019-10-29 07:16:17

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

Amazon SDE intern 阿三给了道题求问正确解。网上都搜不到的题

given streaming

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

> 3

一开始想用两个heap做，但是发现删除的时候会有问题

yu1024000 · 2019-10-29 11:02:51

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

crypnym · 2019-10-29 14:13:36

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

BorrisPoe · 2019-10-29 10:32:18

这题是利口二九五

yqsl888 · 2019-10-29 09:31:56

为什么不能用heap呢？

jessyyilin · 2019-10-29 09:38:14

yqsl888 发表于 2019-10-29 09:31
为什么不能用heap呢？

同问，不能直接用heap吗？

floraazhang · 2019-10-29 09:48:22

yqsl888 发表于 2019-10-29 09:31
为什么不能用heap呢？

比如stream是[1,2,4,3,5]
正常情况下是两个heap 一个min 一个max
那当走完四个之后是
max: [1,2] min: [3,4]
然后走到5
发现怎么着也没办法把1去掉无论5加到那边

ljhgod · 2019-10-29 09:52:11

可以用heap啊
不过还是很刁钻啊，数据的小于k的时候和大于k的时候要分开考虑，还一会儿奇数一会儿偶数。。。
祝顺利

floraazhang · 2019-10-29 10:02:33

ljhgod 发表于 2019-10-29 09:52
可以用heap啊
不过还是很刁钻啊，数据的小于k的时候和大于k的时候要分开考虑，还一会儿奇数一会儿偶数。。 ...

比如stream是[1,2,4,3,5]
如果k是4
那么两边分别是[1,2] [3,4]
那走到5该怎么加

ljhgod · 2019-10-29 10:07:42

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

ljhgod · 2019-10-29 10:16:48

floraazhang 发表于 2019-10-29 10:02
比如stream是[1,2,4,3,5]
如果k是4
那么两边分别是[1,2] [3,4]

5 进min[3,4] , pop 得 3 ，3进max[3,2,1]

floraazhang · 2019-10-29 10:23:23

我看了下其实是可以用heap的，是我当时不自信，我问他两个heap行不行他说不行，我应该证明给他而不是去想别的办法。

ljhgod · 2019-10-29 10:28:36

floraazhang 发表于 2019-10-29 10:23
我看了下其实是可以用heap的，是我当时不自信，我问他两个heap行不行他说不行，我应该证明给他而不是去想别 ...

居然说不行？？？这不是故意坑你么！！即便和面试官争论一般不会也有好事吧.