The 60-second answer
Build prefix sums of weights so each index owns an interval proportional to its weight. Draw a uniform sample over the total mass and binary-search the first prefix boundary that contains it.
Build the answer in this order
1
Clarify constraints
Build prefix sums of weights so each index owns an interval proportional to its weight.
2
Choose the approach
Draw a uniform sample over the total mass and binary-search the first prefix boundary that contains it.
3
Prove complexity
Preprocessing is O(n), each draw is O(log n), and storage is O(n).
4
Test edge cases
Test zero weights, integer vs floating-point mass, deterministic seeds, and empirical frequency convergence.
A useful interview mental model
This is the shape of a strong answer—not a script to memorize.
01Clarify
02Approach
03Implement
04Test
05Complexity
Senior-level signal
- For update-heavy workloads, use a Fenwick/segment tree; for huge read volume, consider the alias method.
- Discuss testing randomized code statistically as well as with deterministic structural tests.
What the interviewer is really testing
Problem decomposition, correctness, data-structure choice, complexity reasoning, and clean implementation under pressure.
Likely follow-up questions
Can you improve the time or space complexity?
Which edge case is most likely to break this solution?
How would you test this under interview time pressure?
Common weak-answer patterns
- Starting to code before constraints are clear.
- Giving complexity without explaining why it is correct.
- Skipping adversarial and boundary cases.