Google phone interview 面经

hkc593 发表于 2016-6-13 11:50
不需要update list的每一个node的 。我想是把head pop出来，update value，然后再append到list的尾部。

啊 这也是个方法 我还是用deque吧…………

https://leetcode.com/problems/moving-average-from-data-stream/

本质就是需要一个 queue 的数据结构来 cache 最后 k 个数据，然后维护一个 sum。避免频繁的 new / delete 的方法就是用数组来模拟 queue。因为 queue 的大小恒定是 k，所以存一个 head 一个 tail，把这个 size = k 的数组循环着用就行了……

环形缓冲区了解一下 (circular queue), 希望有帮助