Google phone interview 面经

上周一（2/29/2016）的google电面，今天刚刚收到通过的通知电面通过，赶快过来发面经。

面我的是个白人小哥，人非常nice，只问了一个问题：moving window aver

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

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

到通知之间用了一个星期，不知道是不是答得一般，committee意见有分歧。onsite求bless！

jemi 发表于 2016-3-9 12:32
楼主你这两个follow up 是怎么答的啊

这两个follow up是根据我的回答问的。
1） 我用了一个sum 来记录window值的总和， window 里每次加入／剔除一个树时就update一下sum，这样求average是O（1）的时间。但是如果data stream太大，每次求sum的error会累积，最后就不准确了。
我当时回答如果data stream太大就不用sum记录了，但是这样求average 就是O（k）。

现在想，其实可以每一定量数（e.g 1000）后refresh一下sum，这样还是可以keep O（1）in time。

2） 这个面试小哥是想说每次create list node 和delete list node不太好，可以保持list node 不变，每次改node value 就可以了。

tianlu1 发表于 2016-3-9 12:28
不好意思，这个题没有说明白。
题目是有一个data stream， find the average of latest k numbers。 data  ...

这个问题听着像是simple moving average
https://rosettacode.org/wiki/Averages/Simple_moving_average#Java

请问follow up第一问到底什么意思，为什么会有error呢？

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

lz 能稍微详细说下题目嘛，有点没看明白

同没明白，能稍微解释一下这几个词组成的意思么？

麻烦楼主解释一下题目吧，谢谢！

不好意思，这个题没有说明白。
题目是有一个data stream， find the average of latest k numbers。 data 是 double parameter。这就类似于array 的moving window average

楼主你这两个follow up 是怎么答的啊

用array应该更好吧

想问楼主是用什么语言刷题的呀？