Sample from a large weighted distribution in O(1) per draw (the alias method). Where do you need it?

Negative sampling in word2vec and recommendation draws millions of weighted samples; doing each in O(log n) is a bottleneck. The alias method makes each draw O(1) after an O(n) setup. Here it is.

Updated Aug 2026 · Grounded in real Applied AI Engineer interview loops and written to a senior-engineer editorial bar.