CareerCup

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.

using System;
using System.Collections.Generic;
using System.Threading;

namespace MovingAverage {

    static class Program {

        static void Main(string[] args) {

            Console.WriteLine("Input the K value and hit <Enter>");
            foreach ( var item in GetEverage( int.Parse(Console.ReadLine()) ) ) {
                Console.WriteLine(item);
            }
        }

        private static readonly List<float> StreamOfFloats = new List<float>();

        private static IEnumerable<float> GetEverage( int K ) {

            const int limit = 100;
            var rand = new Random();

            while ( true ) {
                Thread.Sleep( 1000 );
                StreamOfFloats.Add( (float)rand.NextDouble() );
                if ( StreamOfFloats.Count > limit ) {
                    StreamOfFloats.RemoveAt( 0 );
                }
                float sum = 0;
                var cnt = StreamOfFloats.Count;
                for ( int i = cnt - 1; ( cnt >= K && i >= cnt - K ) || ( cnt < K && i >= 0 ) ; i-- ) {
                    sum += StreamOfFloats[ i ];
                }
                yield return sum / (StreamOfFloats.Count >= K ? K : StreamOfFloats.Count );
            }
        }
    }
}

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.

hist = []
sum = 0
def movavg(v, k):
  global hist, sum
  hist.append(v)
  if len(hist) > k:
    old = hist.pop(0)
  else:
    old = 0
  sum += v - old
  return sum/len(hist)

Is there an algorithm with O(1) complexity?

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);
    }
}

Not completely what's needed, but the idea behind

def imean(a_stream):
    K = 10
    i = 0
    mean = 0.
    for i, el in enumerate(a_stream):
        if i < K:
            mean += el
            i += 1
        else:
            mean += (el - a_stream[i - K])
    return mean / (min(K, i) if i else 1)

Not completely what's needed, but the general idea

def imean(a_stream):
    K = 10
    i = 0
    mean = 0.
    for i, el in enumerate(a_stream):
        if i < K:
            mean += el
            i += 1
        else:
            mean += (el - a_stream[i - K])
    return mean / (min(K, i) if i else 1)

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