Implement fast sampling for weighted k-sided die

Q: Implement fast sampling for weighted k-sided die

This question evaluates understanding of probabilistic algorithm design, numerical stability, and efficient data-structure implementation for constant-time sampling from categorical distributions.

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

Overview

Comments (0)