Implement weighted random sampling with preprocessing
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Weighted Random Sampling (with performance follow-up)
You are given an array of **positive** weights `w[0..n-1]`. Implement a data structure that supports:
- `init(w)`: preprocess the weights.
- `pick() -> int`: return an index `i` such that `P(pick() = i) = w[i] / sum(w)`.
### Requirements
1. Provide an approach where `pick()` runs in **O(log n)** time after preprocessing.
2. **Follow-up:** If `pick()` will be called **millions of times**, how would you redesign/precompute so that each `pick()` call is **O(1) expected time** (while keeping preprocessing reasonable)?
### Notes
- Assume weights fit in 64-bit integer / double precision.
- Clarify how you handle very large `sum(w)` and floating-point pitfalls if using doubles.
Quick Answer: This question evaluates algorithm design and probabilistic reasoning for weighted random sampling, including data-structure preprocessing, time-space trade-offs, expected versus worst-case performance, and attention to numerical precision.
Preprocess positive weights with prefix sums. For each supplied draw value in [0,total), return the index selected by weighted sampling. This deterministic form makes the random picker exact-match testable.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([1,3,2], [0,1,3,4,5])
Expected Output: [0, 1, 1, 2, 2]
Explanation: Draws map into prefix ranges.
Input: ([5], [0,4])
Expected Output: [0, 0]
Explanation: Single bucket.
Input: ([2,2,2], [0,2,4])
Expected Output: [0, 1, 2]
Explanation: Equal weights.
Hints
- Pick a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.