想讨论一道谷歌高频题

最近看到一道谷歌高频题，一直没有思路想和大家讨论一下.
有一个integer的数据流，其中要去除最大的百分之5和最小的百分之五的数据，然后求剩下数据的平均数！

楼主只想到brute force的方法

感觉这题其实比295，480还要简单一点。

我的想法是维护两个pq，把5%的最小数和最大数放进去。在维护一个TreeSet放中间的数
如果数据量太大，就存Pair<value, count>, 再不行就用分布式分段计算

import java.util.*;

public class Test {
    PriorityQueue<Integer> bottom;
    PriorityQueue<Integer> top;
    TreeSet<Integer> middle;
    int totalSize;
    int percentage;
    int sumOfMiddle;
    /** initialize your data structure here. */
    public Test() {
        bottom = new PriorityQueue<>((a, b)-> b.compareTo(a));
        top = new PriorityQueue<>();
        middle = new TreeSet<>();
        totalSize = 0;
        percentage = 5;
        sumOfMiddle = 0;
    }
   
    public void addNum(int num) {
        middle.add(num);
        totalSize++;
        sumOfMiddle += num;
        rebalanceBottom();
        rebalanceTop();
    }
   
    public double findAverage() {
        return (double)sumOfMiddle / middle.size();
    }

    private void rebalanceBottom() {
        int bottomSize = percentage * totalSize / 100;
        //put one more to bottomHeap
        if (bottomSize > bottom.size()) {
            int num = middle.pollFirst();
            bottom.add(num);
            sumOfMiddle -= num;
        } else {
            //same size:
            int num = middle.pollFirst(); //pull out the smallest number
            bottom.offer(num);
            sumOfMiddle -= num;
            num = bottom.poll(); //pull in the biggest value
            middle.add(num);
            sumOfMiddle += num;
        }
    }

    private void rebalanceTop() {
        int topSize = percentage * totalSize / 100;
        //put one more to topHeap
        if (topSize > top.size()) {
            int num = middle.pollLast();
            top.add(num);
            sumOfMiddle -= num;
        } else {
            //same size:
            int num = middle.pollLast(); //pull out the largest number
            top.offer(num);
            sumOfMiddle -= num;
            num = top.poll(); //pull in the smallest value
            middle.add(num);
            sumOfMiddle += num;
        }
    }

    public static void main(String args[]) {
      Test t = new Test();
      for (int i = 0; i < 200; i++) {
        t.addNum(i);
        System.out.println("i=" +i+ ", avg="+ t.findAverage());
        System.out.print("number removed in top: ");
        for (int j: t.top) {
          System.out.print(j + " ");
        }
        System.out.println();
        
        System.out.print("number removed in bottom: ");
        for (int j: t.bottom) {
          System.out.print(j + " ");
        }
        System.out.println();
      }
      for (int i = 100; i >= 0; i--) {
        t.addNum(i);
        System.out.println("i=" +i+ ", avg="+ t.findAverage());
        System.out.print("number removed in top: ");
        for (int j: t.top) {
          System.out.print(j + " ");
        }
        System.out.println();
        
        System.out.print("number removed in bottom: ");
        for (int j: t.bottom) {
          System.out.print(j + " ");
        }
        System.out.println();
      }
   }
}

O(log(k)) 的解法以及步骤，大家看看哪里不对：

1. 使用最近的 k 个元素建立一个哈希表，其中键为该元素的 index，值为该元素的（值，index）组成的 tuple。
2. 使用最近的 k 个元素的（值，index）组成的 tuple 组成一个二叉平衡树（Treaps，红黑树），其中每个节点都记录左右子树的节点个数以及和。
3. 当有新的元素加入的时候，通过哈希表找到需要删除的旧 index 对应的 tuple，在二叉平衡树找到该 tuple 并删除，更新相应子树的记录。
4. 把新元素插入到哈希表以及二叉平衡树，并更新相应的子树记录。
5. 在二叉平衡树总查找第 5% 大 以及第 95% 大的元素，并用根节点的总和减去它们分别左右子树的值。得到结果

开一个BST，维护一个mean，total number of integers，number of integers in BST
每有一个新integer，进树，更新mean和两个number，然后看要不要从BST里去除最大最小数，如果不用就不管，如果用就去掉，更新树和number

之后可以想下怎么把BST中间的那部分放进disk里

个人觉得，可以用一个最大堆，一个最小堆，然后一个记录所有的小的数，另一个记录所有大的数。另外记录一个size，每次来一个数据，对比一个两个堆，看看是不是需要加入堆。然后再看是不是要平均这个数。

不知道小帅 发表于 2020-1-17 02:15
个人觉得，可以用一个最大堆，一个最小堆，然后一个记录所有的小的数，另一个记录所有大的数。另外记录一个 ...

好奇一下，你的堆要开多大，比如这种情况，流的头部是大于1的值，后面都是1
这种情况你的大数堆要怎么处理？

c393323264 发表于 2020-1-17 05:51
好奇一下，你的堆要开多大，比如这种情况，流的头部是大于1的值，后面都是1
这种情况你的大数堆要怎么处 ...

堆里存储的可以是data structure——比如<value, count>的pair

stcheng 发表于 2020-1-17 06:02
堆里存储的可以是data structure——比如的pair

我的意思是，刚开始的一些数字比如2不在top 5 percent里面，然后如果stream后面都是1，在足够多的1之后，2就会来到top 5 percent里面

楼主是哪里看到高频题的？因为我onsite也遇到了。问题有一点不一样。给一个数据流，求最近的k个元素的去掉top5%和最后5%之后的平均值。O(k)的方法是

1. 队列第一次达到 k 个元素的时候，用额外列表 lst 存储队列前 k 个元素从小到大的排序（init 操作需要 O (k * log(k)))
2. 当增加新元素 i 的时候，先遍历 lst 找到 oldest 元素然后删除( O(k) 时间)，然后使用插入排序，插入 i 到 lst 中（ O(k) 时间）
3. 使用 sum 函数计算中间 90% 的元素和（ O(k) 时间）

你的题目就把k当成现有数据流的长度n就好，除了第一次之外，之后每次O(n)。我听面试官说好像有 log(k) （我的问题）的解法，不过没想出来。

WIwindson 发表于 2020-1-17 13:58
楼主是哪里看到高频题的？因为我onsite也遇到了。问题有一点不一样。给一个数据流，求最近的k个元素的去掉t ...

你这个就简单很多了，因为你的窗大小是固定的，它的那个窗是一直变大的

c393323264 发表于 2020/01/18 03:30:15
你这个就简单很多了，因为你的窗大小是固定的，它的那个窗是一直变大的

我的解法只能每次O(n)，你有想到什么更好的做法吗？

WIwindson 发表于 2020-1-17 13:58
楼主是哪里看到高频题的？因为我onsite也遇到了。问题有一点不一样。给一个数据流，求最近的k个元素的去掉t ...

可以优化到 log(k) 的话

1. init k 不变还是 k * log k
2. 删除 oldest 可以用一个queue 每次pop top 在list里删除
  这样 多一个O（k） space 但是记录 oldest 就是 O（1）
  sorted list 删除 是 O（log k）
  sorted list 增加 是 O（log k）
3. total sum 可以类似 sliding window 记录
  删除时候 sum -= 删除项 O（1）
  增加时候 sum += 增加项 O（1）
  减除 top bottom 5% 估计需要 再加 一个 minheap 一个maxheap
  会在第二步多2个 O（log k）

=。 = 有错误请指正～
top bottm sum哪里 估计还能优化

不知道小帅 发表于 2020/01/17 02:15:58
个人觉得，可以用一个最大堆，一个最小堆，然后一个记录所有的小的数，另一个记录所有大的数。另外记录一个size，每次来一个...

我也是这个想法，如果两个堆超出memory你会怎么处理呢？想讨论一下