谷歌onsite的一道题

闲来无事，想起一道当年面谷歌的题目。是第二轮，先是问了常见排序算法的复杂度。然后正题是给一个stream of int, 求sum, average, median.
话说sum 和 average是很trival的，记录sum和stream int 的count 即可。这个m

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

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

. 是stream of stock value, 有时间戳的。这样就可以比较容易的修改了。应该还是要尽量保证顺序存储，这样查找起来应该比较方便。

数据流running median是经典的用到两个heap的题，可不是楼主说的两个queue啊。路过的走马观花的，可不要给误导了。

dayfine 发表于 2020/01/09 15:12:13
stream怎么修改 异想天开吧... 哪个面试官一拍脑门想到的

可能是模拟传输错误 哈哈

wx6807 发表于 2020-1-9 16:52
刚做了这一道，直接有序动态数组，一个个插入，没啥好办法。 每次插入都是 log n。 两个heap反而慢，每次倒 ...

1.     public void addNum(int num) {
   
2.         if (len == 0) arr.add(num);  //avoid null exception
   
3.         int index = add(num, 0, len - 1);
   
4.         arr.add(index, num);          //  <-----------  这一行需要O(n)时间
   
5. 
   
6.         len++;
   
7.     }
   
8. 
   

复制代码

一个array不行吧，array list在中间插入要额外花时间的

stream怎么修改 异想天开吧... 哪个面试官一拍脑门想到的

只改一个的话，median可以看这个数改了前后在哪一堆里，不要找到删除吧

xiaoduoduo 发表于 2020/01/09 15:16:24
只改一个的话，median可以看这个数改了前后在哪一堆里，不要找到删除吧

确实不大行，还要算sum 和 avg  

CalL_Me_Joker 发表于 2020/01/09 15:54:26
确实不大行，还要算sum 和 avg

Sum 跟AVG只要update difference就行了。median按新旧值是不是在同一堆来计算

刚做了这一道，直接有序动态数组，一个个插入，没啥好办法。 每次插入都是 log n。 两个heap反而慢，每次倒腾要额外耗费，2lg（n/2)，感觉有点秀操作的意思

补充内容 (2020-1-9 00:58):
https://leetcode.com/problems/fi...into-a-sorted-array

补充内容 (2020-1-19 15:10):
谢谢楼下的提醒。这个方法复杂度不如双heap，因为arraylist add 复杂度是O（n）。

两个iterator，一个左边，一个右边，都指向最中间的一个/两个数，根据情况更新左边的iterator的位置。这是求median的。
sum的话用Fenwick tree，update() 和query()都是O(logn),专门应付real-time update的。
average的话可能Segment tree更好一点，因为每个Node都有一个range,直接找出相应Node位置求average。