## Google Interview Question for Jr. Software Engineers

Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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``````

Comment hidden because of low score. Click to expand.
0

where do you keep / update your First? :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/**
* 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);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

{
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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Is there an algorithm with O(1) complexity?

Comment hidden because of low score. Click to expand.
0

how could it be O(1), while we have deal with at least N elements ?
O(1) is when we read 1 element by index from an array, or get 1 element by key from hash-table.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 .

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

{
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++;
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0

The idea is to use a round list so we keek track of the last K numbers, we have a variable with the sum of the last K numbers the last number is subtracted and the new number is added. a locks where added to critical regions. the stream is simulated with an array of floats.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

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

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.