Raffle Winners - Select K Unique Winners from Weighted Ticket Entries

Question

## Problem

A raffle assigns each participant multiple tickets. Given a list `[(participant_id, ticket_count)]` and a random seed, select `k` unique winners. Each ticket has an equal probability of being drawn; once a participant wins, all their remaining tickets are removed.

Return the list of `k` winner IDs in draw order.

```python
def draw_winners(
    entries: list[tuple[str, int]],
    k: int,
    seed: int
) -> list[str]:
```

## Example

```
entries = [("alice",3),("bob",1),("carol",6)]
# total 10 tickets; alice has 30% chance, bob 10%, carol 60%
# with seed=42, suppose first draw hits ticket #7 -> carol wins
# carol's 6 tickets removed; redraw from remaining 4
```

## Follow-ups

1. How do you efficiently pick a weighted random element from a list without materializing all tickets?
2. What is the time complexity of drawing `k` winners using a binary search on prefix sums?
3. How do you ensure reproducibility across different Python versions given the same seed?
4. Extend to support "households": if any member of a household wins, all household members are ineligible.

Raffle Winners - Select K Unique Winners from Weighted Ticket Entries

Question Details

Full Details

Topics

More from Amazon