Implement fast sampling for weighted k-sided die
Company: LinkedIn
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
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.
Quick Answer: This question evaluates understanding of probabilistic algorithm design, numerical stability, and efficient data-structure implementation for constant-time sampling from categorical distributions.
Build a Vose alias table and sample using explicit (column,coin) tickets for deterministic grading.
Constraints
- probabilities are non-negative and normalized internally.
- tickets contain floats in [0,1).
Examples
Input: ([0.2,0.3,0.5], [(0.0,0.1),(0.4,0.9),(0.8,0.2)])
Expected Output: [0, 2, 2]
Explanation: Alias-table sampling with explicit random tickets.
Input: ([1,0,0], [(0.7,0.5)])
Expected Output: [0]
Explanation: Degenerate distribution always returns index 0.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.