Compute Statistics from a Frequency Array

You receive an array freq of length 256. freq[v] is the number of times integer value v occurs in an implicit data set. For example, [2, 5, 8] represents two zeroes, five ones, and eight twos.

Without expanding the implicit data set, explain how you would compute its count, minimum, maximum, arithmetic mean, median, mode, and population standard deviation. Give the time and extra-space complexity and define the behavior for an empty data set.

Constraints & Assumptions

• Every frequency is a non-negative integer.
• The total count and weighted sums may require wider numeric types than an individual frequency.
• If multiple values share the largest frequency, report the smallest as the mode.
• For an even count, the median is the average of the two middle observations.
• Return “undefined” for value-based statistics when the total count is zero.

Clarifying Questions to Ask

• Is population or sample standard deviation required?
• How should ties for the mode be resolved?
• What numeric precision and overflow behavior are expected?
• What should the API return for an empty data set?

Solving Hints

• Most statistics are weighted sums or positions in cumulative frequency.
• The two median ranks can be located during a single cumulative scan.
• A variance formula based on two weighted moments avoids materializing samples.