Q
Q
qiGuar2018-11-05 00:56:14
Java
qiGuar, 2018-11-05 00:56:14

How to calculate Big O when generating statistics by values?

Faced the following task:
There is a web service with nkolki endpoints.
There is a set of numbers and you need to display statistics on them when requesting one of the endpoints: the maximum number, the minimum, the average value, how many numbers in total.
The difficulty lies in the fact that this request must be processed in constant time and memory (constant time and memory o (1)).
So far, the idea is only to have a job that runs every second and counts statistics on the available numbers, and a request to the endpoint will return the already calculated values.
There is a nuance here: if a new number is added within one second and there is a request for statistics, then the data will be returned incorrect, since the job will not recalculate the value.
Tell me, please, what am I missing and how to approach the solution of the problem so that there is a constant execution time?

Answer the question

In order to leave comments, you need to log in

1 answer(s)
W
Wataru, 2018-11-08
@wataru

It seems to me that statistics should be recalculated in constant time when entering each new number. When prompted, print the latest statistics. If some of the numbers are set initially, then you will have to calculate the statistics for them in O(n), there is no other way - after all, you will have to look at all the numbers at least once.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question