Weighted Probability Sampling (Softmax Dice Sampler)

Weighted Probability Sampling (Softmax Dice Sampler) You are given an unfair N-sided die. The probability of each side is derived by applying softmax to a list of scores (logits): [ p_i = \frac{e^{s_i}}{\sum_{j=0}^{N-1} e^{s_j}} ] Implement a sampler that returns an index according to this distribution. What to implement Input: an array scores of length N (ints or floats). Preprocessing: compute softmax probabilities and build a data structure for sampling. Sampling: each call to sample() returns an index i (0 <= i < N) with probability p_i. Constraints / Requirements 1 <= N <= 200000 The sampler should support many calls to sample(), so do preprocessing. Each sample() should run in O(log N) time (hint: prefix CDF + binary search). Handle numerical stability (scores may be very large/small). Example tests (guidance) Note: outputs are random, so validate by sampling many times and comparing empirical frequencies. Case 1: scores = [0, 0] -> ~50% / 50% Case 2: scores = [0, 1] -> index 1 should appear much more often Case 3: scores = [1000, 0, -1000] -> index 0 should appear almost always Example Input 2 0 0 Output (random) 10 indices in [0,1], empirical frequency ~50/50 if sampled many times