Katkat

Generate values by weighted probabilities

GoogleMachine Learning Engineer · Onsite

Last updated

This question evaluates understanding of probabilistic sampling, numerical stability, input validation, and algorithmic trade-offs for streaming weighted random draws, including generator determinism via seeding and methods such as CDF/binary-search versus alias for performance.

Given a list of distinct integers and a matching list of probabilities (weights that sum to 1 within a small tolerance), implement a Python generator that yields values according to the specified probability distribution. The generator should support streaming (potentially infinite) draws, validate inputs (length match, nonnegative weights, handling of zeros), and address floating‑point rounding. Implement an efficient sampling method (e.g., prefix sums with binary search or the alias method) and explain the time/space trade‑offs. Provide unit tests that include deterministic checks via random seeding and statistical verification of the output distribution over many samples.