Google Interview Question
Jr. Software EngineersInterview Type: Phone Interview
I am certain that I am missing something as it cannot be trivial.
Assuming we know k before hand
// Program to find k-average where the number is extracted from a stream one by one.
// if n<k , Compute n-average where n is the numbers extracted so far.
// Given a provider with GetNextNumber , IsEmpty signatures
// Average = (a1+ a2 + a3 + a4 +.....am)/m , m= Min(m,k)
// Average = Sum/Count
// SumSofar , First , Next , Count {increment only if count < k }
public class MovingAverage
{
float SumSoFar {get;set;}
float First {get;set;}
int Count {get;set;}
const int AverageLimit = 10 ;// k
void Insert(float next){
if(Count < AverageLimit) Count++;
else SumSoFar -= First;
SumSoFar += next;
}
public void Process(){
while(!provider.IsEmpty())
Insert(provider.GetNextNumber());
}
public void Average(){
return SumSoFar/Count;
}
}
// if we do not know k before hand , then we need to store whole stream and manipulate average based on k
O(1) runtime, O(K) space
from collections import deque
class MovingAverage(object):
def __init__(self, k):
self._moving_avg = 0
self._last_k_numbers = deque(maxlen=k)
self._num_floats = 0
self._k = k
def moving_avg(self, val):
if self._num_floats == 0:
self._moving_avg = float(val)
elif self._num_floats < self._k:
self._moving_avg = ((self._moving_avg * self._num_floats) + val) / (self._num_floats + 1)
else:
self._moving_avg = ((self._moving_avg * self._k) -
self._last_k_numbers[0] + val) / self._k
self._last_k_numbers.append(val)
self._num_floats += 1
return self._moving_avg
O(1) runtime, O(K) space
from collections import deque
class MovingAverage(object):
def __init__(self, k):
self._moving_avg = 0
self._last_k_numbers = deque(maxlen=k)
self._num_floats = 0
self._k = k
def moving_avg(self, val):
if self._num_floats == 0:
self._moving_avg = float(val)
elif self._num_floats < self._k:
self._moving_avg = ((self._moving_avg * self._num_floats) + val) / (self._num_floats + 1)
else:
self._moving_avg = ((self._moving_avg * self._k) -
self._last_k_numbers[0] + val) / self._k
self._last_k_numbers.append(val)
self._num_floats += 1
return self._moving_avg
/**
* Consider a stream of doubles. At any moment find the moving average of the
* last k numbers. If received less than k numbers than return average of only
* those numbers.
*
* @author shivam.maharshi
*/
public class StreamAverage {
public static void runningAverage(double[] stream, int k) {
double avg = 0F;
double[] store = new double[k];
int i = 0, sl = stream.length;
boolean touchedK = false;
for (int j = 0; j < sl; j++) {
if (j == k) {
touchedK = true;
}
if (i == k) {
i = 0;
}
if (touchedK) {
avg = (avg * k - store[i] + stream[j]) / k;
} else {
avg = (avg * (j) + stream[j]) / ( j + 1);
}
System.out.println(avg);
store[i] = stream[j];
i++;
}
}
public static void main(String[] args) {
double[] stream = new double[] { 1, 3, 5, 7, 0, 2, 5, 6 };
StreamAverage.runningAverage(stream, 3);
}
}
public class MovingAvgSvc
{
private float[] values
private float avg;
int rplc;
int size;
MovingAvgSvc(int k)
{
values=new float[k];
avg=0.0;
size=0;
rplc=0;
}
public void addValue(float f)
{
float sum=avg * size;
if(size<k)
{
size++;
}else
{
rplc=0;
}
sum-=values[rplc];
values[rplc++]=f;
sum+=f;
avg=sum/size;
}
public float getAvg()
{
return avg;
}
///O(K) Space, O(1) time.
I used following algo.
count= number of inputs
num = actual number that is added in queue
average= moving average
for count <2 , compute average normal way. (ie if( count==1) return num; if(count==2) return (num+avg)/2
for rest ,
average= ((average/(count/(count-1)) + num/count
I wrote following program with input as int but can be easily modified to accommodate float
float moving_avg(int num){
static float avg;
static int count;
float olddata;
count++;
if(count >2){
olddata= avg/(count/(count-1));
avg=olddata+(num/count);
} else if( count ==2 ){
avg=(avg+num)/2;
} else {
avg=num;
//printf("olddata=%.2f count=%d avg=%f\n",olddata,count,avg);
}
return avg;
}
Call above function to calculate the moving average .
c# implementation
public class AverageManager
{
private int k;
private float[] values;
private float total = 0;
private int n = 0;
private int index = 0;
private object obj = new object();
public AverageManager (int k)
{
Debug.Assert(k > 0);
this.k = k;
values = new float[k];
}
public float Average()
{
lock (obj)
{
return total / n;
}
}
public void AddItems(float[] stream)
{
int i=0;
while (i < stream.Length)
{
lock (obj)
{
total += stream[i];
total -= values[index];
values[index] = stream[i];
index++;
if (index >= values.Length)
index = 0;
if (n < k)
n++;
}
}
}
}
Idea is to use the array as queues.
import java.io.InputStream;
import java.util.Scanner;
/**
* Created by Nilesh Agrawal on 5/25/16.
*/
public class MovingAverage {
public void movingAvergage(int K){
double[] a = new double[K];
double sum = 0.0;
Scanner scanner = new Scanner(System.in);
for(int i =1;scanner!=null;i++){
sum -= a[i%K];
a[i%K] = scanner.nextDouble();
sum += a[i%K];
if(i>=K){
System.out.print(sum/K +" ");
}else{
System.out.print(sum/i+" ");
}
}
}
public static void main(String args[]){
MovingAverage movingAverage = new MovingAverage();
movingAverage.movingAvergage(6);
}
}
1. Take another array of length K, 'kLengthArray'
2. Add K elements to this array and sout(sum/k)
3. Now set a pointer at 0 index of this new array
4. If there are more elements coming from the stream, replace the element at pointer index with the new element. Increment the pointer. If pointer == K i.e. the length of the array, set it to 0 again.
public class MovingAverageDemo {
static void movingAverage(float[] dataStream, int K) {
float[] kLengthArray = new float[K];
int i;
for(i = 0; i< dataStream.length && i < K; i++) {
kLengthArray[i] = dataStream[i];
}
System.out.println(sumOfArray(kLengthArray)/ i);
if(dataStream.length > K ) {
int pointer = 0;
for(int z = i ; z < dataStream.length; z++) {
kLengthArray[pointer] = dataStream[z];
pointer++;
if(pointer == K) {
pointer = 0;
}
System.out.println(sumOfArray(kLengthArray)/K);
}
}
}
static float sumOfArray(float[] data) {
float sum = 0;
for(int i = 0; i< data.length ; i++) {
sum = sum + data[i];
}
return sum;
}
public static void main(String[] args) {
float[] dataStream = {1,2,3,4,5,6,7,8,9,10,11,12};
movingAverage(dataStream, 3);
}
}
Space Complexity = K
Time complexity is K*n.
K is supposed to be a small number. If K is in millions, then the average won't change much anyways by the next number coming.
All suggestions/improvements welcome. Thanks
Hi Vicky,
You algorithm and thinking is perfect. Just one improvement. I see you are calculating sum by repeatedly parsing the array of size k. You don't need to do this. Running average = Previous Running Average + ( Element read from stream - Element eliminated from store this time) / K
c# implementation.
This is the emulation as much as I understand the task.
The emulation is actually in form of adding random float numbers to list in cycle.
Then I take the last K (or less, if total number of elements is less than K) numbers from the list, and calculate their average.
- zr.roman November 15, 2015