Map Weighted Random Draws to Indices
Company: Nuro
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Map Weighted Random Draws to Indices
Implement `weighted_indices(weights, draws)`.
`weights[i]` is the positive integer weight of index `i`. Let `total = sum(weights)`. A draw is an integer from `1` through `total`, inclusive. Map each supplied draw to the smallest index whose cumulative weight is at least that draw, and return the mapped indices in draw order.
The supplied `draws` make this function deterministic for testing. A real weighted picker would independently sample an integer uniformly from `1..total` and apply the same mapping, making index `i` appear with probability `weights[i] / total`.
## Function Contract
```python
def weighted_indices(weights: list[int], draws: list[int]) -> list[int]:
...
```
## Example
```text
weights = [1, 3, 2]
draws = [1, 2, 4, 5, 6]
result = [0, 1, 1, 2, 2]
```
The cumulative ranges are `1..1` for index `0`, `2..4` for index `1`, and `5..6` for index `2`.
## Constraints
- `1 <= len(weights) <= 100_000`
- `1 <= weights[i] <= 10**9`
- `0 <= len(draws) <= 100_000`
- Every draw satisfies `1 <= draw <= sum(weights)`.
Quick Answer: Map deterministic draws to weighted indices using cumulative ranges. Support large weights and many queries while preserving draw order and respecting inclusive one-based draw boundaries.
Implement weighted_indices(weights, draws). weights[i] is a positive integer weight. For each deterministic draw in the inclusive range 1..sum(weights), return the smallest index whose cumulative weight is at least the draw. Preserve draw order. The supplied draws expose the mapping step of weighted random selection without using randomness during grading.
Constraints
- 1 <= len(weights) <= 100,000
- 1 <= weights[i] <= 1,000,000,000
- 0 <= len(draws) <= 100,000
- 1 <= draw <= sum(weights)
Examples
Input: ([1], [])
Expected Output: []
Explanation: No supplied draws produce no indices.
Input: ([1], [1])
Expected Output: [0]
Explanation: A one-index distribution always maps to zero.
Hints
- Build cumulative weights once.
- Use lower-bound binary search for each draw.