Implement fast sampling for weighted k-sided die

Q: Implement fast sampling for weighted k-sided die

This is a Coding & Algorithms interview question from LinkedIn for Data Scientist roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You must sample from a categorical distribution over k outcomes with probabilities p1..pk (sum to 1) without using built-in categorical samplers. You have access only to a Uniform(0,1) RNG (or equivalently fair random bits). Design an algorithm with O(k) preprocessing time and O(1) sampling time per draw (e.g., Vose’s alias method). Provide: (a) clear build and sample pseudocode; (b) time and space complexity; (c) how you would handle extremely small probabilities and floating-point rounding so the resulting distribution is exactly normalized; (d) how to support incremental probability updates efficiently; (e) a statistical test plan (e.g., chi-square or KS on grouped bins) to validate the sampler’s correctness.

Implement fast sampling for weighted k-sided die

Comments (0)