Random Pick with Weight
Raffle draw. Person i holds weights[i] consecutive tickets. The tickets are numbered from 1 in the order of the people: person 0 holds tickets 1 to weights[0], person 1 holds the next weights[1] tickets, and so on. Each roll is a ticket number. Return, for each roll in order, the index of the person who holds that ticket. (In the real problem the roll comes from a random number generator. Here the rolls are handed in so your answer can be checked.) Limits: 1 <= weights.length <= 100000, 1 <= weights[i] <= 10000, the weights add up to at most 1000000000, 0 <= rolls.length <= 100000, and every roll is a ticket that exists (1 <= rolls[i] <= the total). Think about: if you knew the last ticket each person holds, how many of those would one roll need to look at? Examples: weights = [1,3], rolls = [1,2,3,4] => [0,1,1,1] person 0 holds ticket 1; person 1 holds tickets 2, 3 and 4 weights = [2,5,3], rolls = [10,2,3,8,1] => [2,0,1,2,0] tickets 1-2 are person 0, 3-7 are person 1, 8-10 are person 2
You're running a raffle where each person holds a block of consecutive tickets, and for every number rolled you say whose ticket it is. Interviewers like it because a story about winners hides a running total and a binary search, and the answer only comes fast once you see the blocks as a sorted list of last tickets. The classic trap is an off-by-one at the edge of a block: the ticket that equals a running total belongs to the person whose block ends there. In the original problem the roll comes from a random number generator inside a class; here the rolls are handed in so the answer can be checked. Expect up to 100,000 people with 1 to 10,000 tickets each, at most 1,000,000,000 tickets in all, and up to 100,000 rolls.
Examples
You write
pick_indexes(weights: List[int], rolls: List[int])
Example 1
- Input
- weights = [1,3], rolls = [1,2,3,4]
- returns
- [0,1,1,1]
Example 2
- Input
- weights = [2,5,3], rolls = [10,2,3,8,1]
- returns
- [2,0,1,2,0]
Save this for your laptop
The editor and Run need a bigger screen. The link opens Random Pick with Weight ready to code. It is free, and the editor needs no account.
The pattern behind it
Arrays & Hashing
I reach for it when
- You catch yourself scanning the array again for every element.
- The problem asks about duplicates, pairs, counts or groups.
Say this before you type. Say what the key is and what the value remembers, before you write the loop.
All 128 Arrays & Hashing problemsBinary Search
I reach for it when
- The input is sorted, or sorted and then rotated.
- You want a boundary: the first or last place something is true.
Say this before you type. Say the yes-or-no question, and which side each answer throws away.
All 19 Binary Search problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.