Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
You have to be careful with solutions like this. Storing the average in some sort of floating-point value runs the risk of accumulated roundoff error. It would be important to clarify precision requirements first.
This works because by definition
{{
avg = (1/n) * sum(i=0 to n) a[i]
}}
Then
{{
n * avg = sum(i=0 to n) a[i]
}}
Hence
{{
n * avg + a[n + 1] = sum(i=0 to n) a[i] + a[n + 1] = sum(i = 0 to n+1) a[i]
}}
so that
{{
(n * avg + a[n + 1]) / (n + 1) = (1 / (n + 1)) sum(i = 0 to n+1) a[i]
}}
which is the new average. The trick is to not store the sum of the numbers seen so far because it can blow up. However, you pay for that with roundoff errors.
You could store the numbers precisely if you wanted to, and it wouldn't be all so bad. If your incoming numbers are d digits long, you would need d*logN bits for the exact sum, and another logN for the counter, so O(d*logN) total space. Calculation time would be at worst something like the square of that (d^2*(logN)^2), so still very reasonable.
(1) Take three variables avg,count=0;
for first element store it in avg and increment count by 1
for each coming element
avg=(avg*count+ComingElement)/(count+1);
done
print avg
exit
"avg*count" this is an unnecessary overhead. instead u cud just add all and divide by count
store avg. and count of numbers
- Siva June 10, 2012do (avg/(count+1))* count + newelement / (count+1)
to avoid integer overflow