Practice/Meta/Create a Lottery System Based on Weighted Probability

Create a Lottery System Based on Weighted Probability

CodingMust

Problem

You need to build a lottery system where each participant has a different chance of winning based on an assigned weight value. The higher the weight, the more likely that participant is to win.

For example, if participant A has a weight of 1 and participant B has a weight of 3, then B should be three times more likely to win than A.

Your system should:

• Initialize with a list of participants and their corresponding weights
• Provide a method to randomly select a winner where the probability of selection is proportional to each participant's weight
• Ensure fair probability distribution according to the weights

Requirements

1. Implement a WeightedLottery class that accepts participants and their weights during initialization
2. The draw_winner() method should return one participant selected randomly based on weighted probabilities
3. All weights are positive integers
4. The participants list and weights list have the same length and are non-empty
5. Each call to draw_winner() should be an independent random selection

Constraints

• 1 ≤ number of participants ≤ 10,000
• 1 ≤ weight value ≤ 1,000,000
• The solution should handle repeated calls to draw_winner() efficiently
• Time complexity for initialization: O(n) where n is the number of participants
• Time complexity for each draw: O(log n) or better

Examples

Example 1:

` Input: participants = ["Alice", "Bob", "Charlie"] weights = [1, 2, 3]

Probability Distribution: Alice: 1/6 ≈ 16.67% Bob: 2/6 ≈ 33.33% Charlie: 3/6 = 50%

Output: One of the participants (e.g., "Charlie") Explanation: Charlie has the highest weight and should win approximately 50% of the time across many draws `

Example 2:

` Input: participants = ["Winner"] weights = [100]

Output: "Winner" Explanation: With only one participant, they always win regardless of their weight value `

Example 3:

` Input: participants = ["X", "Y", "Z"] weights = [10, 10, 10]

Probability Distribution: X: 33.33% Y: 33.33% Z: 33.33%

Output: One of "X", "Y", or "Z" Explanation: Equal weights mean equal probability for each participant `