10k

346. Moving Average from Data Stream

Published on

Problem

The problem is to design something that can find the moving average of an integer column, the moving window will be set by initializing the constructor, and then if you want to get the moving average, a next function will be called, and this function will pass a new number in. next returns the current moving average after this number is put in.

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

Explanation
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3

This design problem is just like writing code everyday doing requirements more closely. We need to have a use case, like the Example above, and it will be immediately clear what functionality we need to achieve.

Parse

The moving window needs a size to record how long it needs to be, and a data structure to record the maximum first size for calculation purposes. The reason why it is called the most is that the number of numbers in the container may not be enough for size at the beginning, so we can calculate the average of these numbers according to the question.

When the number reaches size, every time a new value is entered, an old value is discarded. Can we think of FIFO in this place? and queue? At first I thought of using a list and removeFirst function. But I didn't think of a queue.

Another small point is that the sum value can actually be updated as an auxiliary variable when the data is added or removed, so it's simpler than writing a separate sum function to iterate through the values of the summation containers.

For design topics, the idea is generally

  • abstracting the problem and decomposing it into smaller problems, categorized and discussed (the framework of the code is there).
  • consider multiple perspectives, you can use reverse thinking, yes, no.
  • picking the right data structure (10 common)
    • BitSet - generally occurs in space optimization
    • HashSet (with or without problems) & HashMap (correspondence)
    • ArrayList (add, get O(1) time complexity) & LinkedList (addFirst O(1) time complexity)
    • Stack (LIFO) & Queue (FIFO) & Deque (combination of heap and queue)
    • TreeSet (ordered HashSet) & PriorityQueue (sorted) & TreeMap (ordered hashmap)
    • If an object has more than one property, you may even want to consider a new class
  • Constructed code

Code

class MovingAverage {
    
    private int size;
    private List<Integer> nums;

    public MovingAverage(int size) {
        this.size = size;
        this.nums = new ArrayList<>();
    }
    
    public double next(int val) {
        nums.add(val);
        int numCount = nums.size();
        if (numCount <= this.size) {
            return (double) sum(nums) / numCount;
        } else {
            nums.remove(0);
            return (double) sum(nums) / size;
        }
    }
    
    private int sum(List<Integer> nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum;
    }
}

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */

class MovingAverage {
    
    private int size;
    private Queue<Integer> queue;
    double sum;

    public MovingAverage(int size) {
        this.size = size;
        this.queue = new LinkedList<>();
        this.sum = 0;
    }
    
    public double next(int val) {
        if (queue.size() == size) {
            int ele = queue.poll();
            sum -= ele;
        }
        
        queue.offer(val);
        sum += val;
        return sum / queue.size();
    }
}

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */

问题

这个问题就是说，设计一个东西可以求一个整数列的移动平均值，移动窗口会通过初始化构造函数来设定，然后如果想要取到移动平均值，会调用一个next函数，这个函数同时会传一个新的数字进去。next返回的就是这个数字放进去之后的当前的移动平均值。

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

Explanation
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3

这种设计题就像日常写代码做需求更贴近一样。我们需要有一个use case，如上文的Example，就会马上清晰的知道我们需要实现的功能是什么。

解析

移动窗口需要一个size来记录到底需要多长的移动窗口；需要一个数据结构来记录最多前size个数字以便计算。为什么叫最多，因为可能在最开始的时候这个容器中数字的数量还不够size个，根据题意我们就计算这些数字的平均值即可。

当数量达到size之后，每进一个新的数值，就会丢弃一个老的数值。这个地方是否能想到FIFO？以及queue？我最开始的时候想到了使用一个list和removeFirst函数。但是并没有想到queue。

另外一个小点就是说，其实sum值可以作为辅助的变量在数据加入或者删除的时候一并更新，这样比我单独再写一个sum函数遍历求和容器的值要看着简洁一些。

对于设计题目来说，思路一般是

  • 抽象问题，并且化解成小问题，分类讨论（代码的框架就有了）；
  • 多角度考虑，可以使用逆向思维，是、否；
  • 选取合适的数据结构（10种常见）
    • BitSet - 一般出现在空间优化
    • HashSet（有或无问题） & HashMap（对应关系）
    • ArrayList（add、get O(1)时间复杂度） & LinkedList（addFirst O(1)时间复杂度）
    • Stack（LIFO） & Queue（FIFO） & Deque（堆和队列结合）
    • TreeSet（有序的HashSet） & PriorityQueue（排序） & TreeMap（有序的hashmap）
    • 如果一个object有多个属性，甚至可能要考虑一个新class
  • 构造代码

代码

class MovingAverage {
    
    private int size;
    private List<Integer> nums;

    public MovingAverage(int size) {
        this.size = size;
        this.nums = new ArrayList<>();
    }
    
    public double next(int val) {
        nums.add(val);
        int numCount = nums.size();
        if (numCount <= this.size) {
            return (double) sum(nums) / numCount;
        } else {
            nums.remove(0);
            return (double) sum(nums) / size;
        }
    }
    
    private int sum(List<Integer> nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum;
    }
}

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */

class MovingAverage {
    
    private int size;
    private Queue<Integer> queue;
    double sum;

    public MovingAverage(int size) {
        this.size = size;
        this.queue = new LinkedList<>();
        this.sum = 0;
    }
    
    public double next(int val) {
        if (queue.size() == size) {
            int ele = queue.poll();
            sum -= ele;
        }
        
        queue.offer(val);
        sum += val;
        return sum / queue.size();
    }
}

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */
Thoughts? Leave a comment