Weighted Random Letter Generator With Add, Remove and Generate

Write a class that generates random letters according to weights. The class was described as having four methods, of which three were reported: - `add(letter, weight)`: add a letter with a weight. - `generate()`: return a random letter, where each letter's probability is its weight divided by the total weight of all letters currently held. - `remove(...)`: remove a weight. This is a dynamic version of the classic task of picking an index at random with probability proportional to its weight: weights can now be added and removed between draws. ```hint Count the calls Ask how often each method is called relative to the others, then pick a structure whose costs match that mix: a simple layout can make one method cheap and another linear. ``` ```hint Weights on a line Picture the weights laid end to end on a line whose length is the total weight; a uniformly random point on the line lands inside one letter's segment. Think about what has to change on that line when a weight is added or removed. ``` ### Clarifying Questions - The class has four methods, but only three were reported. Is the fourth a constructor taking initial weights, an update to an existing letter's weight, or something else? - Does `remove` take a letter and delete it entirely, or a letter and an amount to subtract? - When `add` is called for a letter that already exists, is its weight increased or replaced? - Are letters limited to `a` through `z`, or can there be any number of distinct labels? - Are weights positive integers, or can they be fractional? - What should `generate` do when no weight is held? - Which method is called most often? ### What a Strong Answer Covers - Settles the meaning of each method, including repeated adds, removals and an empty generator - A correct sampling procedure in which each letter's probability equals its share of the total weight - A data structure whose costs fit the expected mix of calls, with the complexity of every method - A comparison with simpler or faster-to-sample alternatives, and when each one wins - Testability: an injectable random source, boundary tests and a statistical check of the distribution ### Follow-up Questions - `generate` is called a million times between updates. What would you change? - Weights can be fractional. What goes wrong with floating-point running sums, and how do you avoid it? - How would you test that `generate` follows the weights without making the test flaky? - Several threads call these methods at once. How do you make the class safe?