Negative Sampling

Task

Implement negative_sampling(candidate_ids: list[int], sampling_weights: list[float], random_values: list[float]) -> list[int]. Sample negative candidate IDs with replacement from non-negative weights, using caller-provided uniform random values so the result is deterministic.

Requirements

• candidate_ids and sampling_weights have the same non-zero length.
• Sampling weights are non-negative and have a strictly positive total.
• Each random value is in [0, 1), and produces one sampled candidate.
• For each random value u, find the first cumulative weight strictly greater than u times the total weight.
• Sampling is with replacement, so an ID may appear more than once.
• Zero-weight candidates are never selected, including when u is exactly zero.
• Return an empty result for empty random_values and do not mutate any input.

Example

negative_sampling(
    [10, 20, 30],
    [1.0, 2.0, 1.0],
    [0.0, 0.25, 0.74, 0.75],
)
# [10, 20, 20, 30]