“You are given an n-sided die where side i has probability pi of being rolled. What is the most efficient data structure for simulating rolls of the die?”
A very similar question was posted to me recently :
The approaches above are very cool, and illustrate the use of augmented search trees.
However, it seems there is a better method for this problem – and it has been out there for a while now. This was a fascinating read :
Additional pointers for the alias method: