Weighted Die Roller from Per-Face Probabilities, with Corner Cases

Implement rolling a biased die. The die has `k` faces, and you are given the probability of each face as a list `probs`: face `i` should come up with probability `probs[i]`, and the probabilities need not be equal. Write a function or class whose `roll()` returns a face index drawn from that distribution, using a standard uniform random number generator. After the implementation, the interviewer followed up on corner cases. ### Clarifying Questions - Will the same die be rolled once, or many times after it is created? - Must results be reproducible in tests, for example through a seed or an injected random source? - Are faces identified by their index in `probs`, or by separate labels? ### Part 1 — Roll the die Implement `roll()`, and state the setup cost and the cost of each roll. ```hint Start from one uniform draw Ask what a single uniform random number in `[0, 1)` gives you, and how to turn it into an event that happens with probability exactly `probs[i]`. ``` #### What This Part Should Cover - A mapping from uniform draws to faces that gives every face exactly its probability - Setup and per-roll time and memory, and how the face is located - A design that lets tests control the random source ### Part 2 — Corner cases Which inputs and numerical situations can break your implementation, and how should each one be handled? ```hint Look at the boundaries Consider what happens at the edges of each face's share, for faces whose probability is zero, and when the probabilities do not add up to exactly `1` in floating point. ``` #### Clarifying Questions for this Part - Must the probabilities sum to exactly `1`, or should the function accept relative weights and normalize them? - Should invalid input fail when the die is created, or when it is rolled? #### What This Part Should Cover - Validation of empty, negative, non-finite and all-zero inputs, and of sums that are off by rounding versus genuinely wrong - Zero-probability faces, a single face, and a draw that lands at the very end of the range - Testing a randomized function: deterministic tests with chosen draws, plus a statistical check that does not flake ### What a Strong Answer Covers - Correct sampling, with every face receiving exactly its probability - Awareness of setup versus per-roll cost, and a constant-time option when rolls are frequent - An explicit policy for invalid input, agreed before coding - Floating-point care at the boundaries between faces - Tests that pin down boundary behavior and check the distribution without flakiness ### Follow-up Questions - The die is rolled millions of times. How do you make each roll take constant time? - One face's probability changes between rolls. Which structure keeps both updates and rolls fast? - The probabilities arrive as integer counts instead of floats. How does that change your implementation and its exactness? - How would you test that the distribution is correct without writing a test that fails at random?