Weighted Random Sampler · Approach

01 · Develop the design

Plan the design

Snapshot validated items and checked integer prefix sums once. Each sample obtains a uniform integer below total weight and binary-searches the first prefix strictly greater than that draw.

Stage 1

Partition integer positions

Weights [2, 0, 3] own positions [0, 2), [2, 2) and [2, 5). Enumerate every draw for a tiny example.

Stage 2

Use exact bounded integers

Keep total weight within a checked safe-integer bound and require nextInt(total) to return an integer uniformly from zero through total-1.

Stage 3

Test boundaries before frequencies

A scripted generator can exhaust every draw position and prove interval assignment without a flaky probability assertion.

02 · Work through the method

Step-by-step approach

Validate unique item IDs and nonnegative safe-integer weights. Accumulate with checked addition and reject an empty or zero-total distribution.
Store immutable item and cumulative-weight arrays. Zero-weight entries retain repeated prefixes and therefore empty draw intervals.
Call the injected bounded generator with total weight and validate its returned integer range. Use upper-bound search to find the selected index in logarithmic time.
Document O(n) construction and O(log n) sampling with O(n) storage. Updating weights creates a new sampler; security-sensitive randomness and mutable weighted trees are outside this exercise.

03 · Justify the choices

Why this approach works

For a draw r in [0, total), which prefix is selected?

The first prefix strictly greater than r

Strict upper-bound search gives each item exactly its weight in integer draw positions.

How should zero-weight entries behave?

Receive no draw positions even if prefix sums repeat

Repeated prefix sums represent empty intervals and must not be selected.

Can modulo reduction always create a uniform bounded draw?

No; rejection sampling or a supplied unbiased bounded generator is needed

Modulo is biased when the source range is not an exact multiple of the requested bound.

04 · Plan the evidence

Validation strategy

Enumerate every draw for [2, 0, 3] and observe exact counts [2, 0, 3].
Boundary draws zero and total-1 select the correct items.
Reject duplicate IDs, negative weights, unsafe totals and all-zero inputs.
A scripted out-of-range random result fails rather than indexing arbitrary storage.

Trade-offs to explain

Prefix sums favor immutable distributions and make updates linear.
A uniform bounded-integer source is an explicit dependency, not guaranteed by validation alone.
Exact boundary tests are deterministic; empirical distribution checks can supplement but not replace them.