Google onsite难题求解，回答就加米~~

最近在地里看到一道狗家onsite题目（链接在此：），苦思冥想了好久都没有头绪，希望大家能够集思广益，appreciate any ideas!

题目是这样的：
给定一个数字input流，要求最后last k value的平均值，并且在计算时要求除去在这k个数字中的t

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

Val找到并且删掉，然后再max-heapify，然而这样就是O（n）了呀，完全失去了用heap的意义啊。。。

希望大佬们能提供一下思路，承诺回答就加米！！

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

joezie 发表于 2019/10/24 04:32:03
可是面试的时候真的有时间写红黑树么…

你猜猜TreeMap是怎么实现的，就是要处理重复，但是不是太难

我用的c艹，这个有multimap，解这个问题更加方便，

比较好想的是红黑树，维护和取都可以O(logn)。
楼上说的线段树也可以，不过如果我没理解错的话这个可能要要求值的取值范围比较小, O(logn)。
然后就是lazy delete的heap, 也是O(logn)。

我觉得工程上的话可能红黑树比较好，支持的操作比较多。

建两个权值线段树，每个节点维护线段和，剔除old value的时候直接log n更新。
或者每个heap配个map,删除old value的时候不真的从heap里面删掉，只是去map里面mark一下这个数已经过期了。

能不能把maxHeap和minHeap的大小定义成k+5%

平衡二叉树（bbst）也可以搞。一个bbst用来维护sliding window中的数，query一下max 5%和min 5%，相当于bbst找k大和k小 logn搞定，old value删除log n，插入新值，update一下max和min 5%的和就可以了。每个节点除了键值，再维护一下子树size，方便k大查询

如果用minHeap和maxHeap来做那这两个heap的size是多少？是 k * 5% 吗？

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

xiaoming2019 发表于 2019-10-23 04:26
平衡二叉树（bbst）也可以搞。一个bbst用来维护sliding window中的数，query一下max 5%和min 5%，相当于bbs ...

哇好厉害的方法啊

novnocturne90 发表于 2019-10-23 04:47
如果用minHeap和maxHeap来做那这两个heap的size是多少？是 k * 5% 吗？

恩恩理想情况下是k*5%，不过如果我们用lazy delete的话，heap大小就可能会超过（因为heap里面还包括了“已过期”的node）

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies