Compute Statistics from a Frequency Array
Company: Citadel
Role: Software Engineer
Category: Statistics & Math
Difficulty: hard
Interview Round: Technical Screen
# 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.
### What a Strong Answer Covers
- Correct formulas and zero-based or one-based median-rank handling.
- A clear empty-input contract and deterministic mode tie-breaking.
- Overflow and floating-point precision considerations.
- `O(256)` time and `O(1)` extra space, generalized to `O(m)` for `m` bins.
- An explanation of why the implicit data set must not be expanded.
### Follow-up Questions
1. How would you merge statistics from frequency arrays computed on separate machines?
2. When can `E[X^2] - E[X]^2` lose numerical precision, and what alternative would you use?
3. How would the algorithm change if values were arbitrary sparse integers rather than `0..255`?
4. How would you compute a requested percentile?
Quick Answer: Compute count, minimum, maximum, mean, median, mode, and population standard deviation directly from a 256-bin frequency array. Use weighted moments and cumulative ranks without expanding samples, define empty-data behavior and ties, and address overflow and numerical precision.