Find Missing Observations

Find Missing Observations

What is this problem about?

The Find Missing Observations interview question is a probability-themed construction problem. You are given $n$ rolls of a 6-sided die, but you only know the results of $m$ of them. You are also given the average (mean) of all $n+m$ rolls. Your task is to reconstruct the missing $n$ rolls such that each roll is between 1 and 6, and the total average matches the target. If no such combination exists, return an empty array.

Why is this asked in interviews?

Microsoft and Google ask the Find Missing Observations coding problem to evaluate a candidate's ability to handle mathematical constraints and implement Greedy interview patterns. It tests whether you can translate a "mean" requirement into a "sum" requirement and then distribute that sum fairly across a set of containers (the die rolls).

Algorithmic pattern used

This problem follows the Greedy Distribution and Math patterns.

1. Calculate Target Sum: TotalSum = mean * (n + m).
2. Missing Sum: MissingSum = TotalSum - Sum(m_rolls).
3. Feasibility Check: The MissingSum must be between $n imes 1$ and $n imes 6$. If not, return [].
4. Distribution:
   • Give every missing roll a base value: MissingSum / n.
   • Distribute the remainder: MissingSum % n. Add 1 to the first remainder elements.

Example explanation

$m\_rolls = [3, 2, 4, 3], n = 2, mean = 4$

1. Total rolls = 6. Total Sum needed = $4 imes 6 = 24$.
2. Known sum = $3+2+4+3 = 12$.
3. Missing Sum = $24 - 12 = 12$.
4. Check: $2 \leq 12 \leq 12$. OK.
5. Distribution: $12 / 2 = 6$ remainder 0. Result: [6, 6].

Common mistakes candidates make

• Integer Division: Forgetting to handle the remainder properly, leading to a sum that is slightly off from the target.
• Range Validation: Failing to check if the MissingSum is even possible with $n$ dice before attempting to construct the array.
• Randomization: Trying to use random numbers to find a solution instead of a deterministic greedy distribution.

Interview preparation tip

When distributing a value $V$ across $N$ slots, use quotient = V / N and remainder = V % N. Assigning quotient + 1 to the first remainder slots and quotient to the rest is the most uniform way to fill the slots.