Coding questions · LinkedIn

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.

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.

Alias Method Sampling With Tickets

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

Example 1

Input: ([0.2,0.3,0.5], [(0.0,0.1),(0.4,0.9),(0.8,0.2)])
Output: [0, 2, 2]

Explanation: Alias-table sampling with explicit random tickets.

Example 2

Input: ([1,0,0], [(0.7,0.5)])
Output: [0]

Explanation: Degenerate distribution always returns index 0.

Hints

Clarify edge cases before coding.
Keep the return value deterministic.