Write two functions that pick from a fixed set of weights in O(1) per pick.
buildAlias(weights) takes positive numbers and returns { accept, alias }, two arrays of length n. Picture n columns of equal height; column c is filled by outcome c up to the fraction accept[c] (between 0 and 1) and by outcome alias[c] for the restpickAlias({ accept, alias }, rng) draws a column c = Math.floor(rng() * n), then draws again and returns c if rng() < accept[c] and alias[c] otherwise. That is exactly two draws per pick- The build must make outcome
i come out with probability weights[i] / sum(weights). Many different tables are valid; the tests check the probabilities they imply - Build in O(n)