Advertisement
Home Data Structure Arrays Random Pick with Weights

Random Pick with Weights

1
Advertisement

Title: Random Pick with Weights

In this guide, you’ll learn how to solve the Random Pick with Weights problem in Java, a classic array and probability interview question. Given an array of positive integer weights, the goal is to design a class that picks a random index, where the probability of picking a given index is proportional to its weight.

This problem shows up often in interviews because it combines prefix sums, binary search, and a careful understanding of how random number generation maps to probability. Let’s explore how to build a pickIndex() method that runs in O(log n) time after a one-time O(n) setup.

Understanding the Problem

You are given an integer array weights where weights[i] describes the weight of index i. You must implement a class with a method pickIndex() that randomly picks an index in the range [0, weights.length - 1], such that the probability of picking index i equals weights[i] / sum(weights).

For example, if weights = [1, 3], index 0 should be picked with probability 1/4 and index 1 should be picked with probability 3/4. Constructing the object may do preprocessing work, but each call to pickIndex() should be fast, ideally faster than scanning the whole array.

The key insight is that weights can be converted into contiguous, non-overlapping ranges whose lengths are proportional to the weights themselves. Picking a random index then becomes equivalent to picking a random point along the total length and finding which range it falls into.

Approach: Prefix Sums with Binary Search

The approach splits into two phases, a one-time setup that builds a prefix sum array, and a fast lookup that uses binary search to map a random draw to an index.

  1. Build a prefixSums array where prefixSums[i] stores the cumulative sum of weights[0..i].
  2. Store the last value of prefixSums as totalSum, the sum of every weight.
  3. In pickIndex(), draw a random integer target in the range 1 to totalSum inclusive.
  4. Binary search prefixSums for the smallest index i such that prefixSums[i] >= target.
  5. Return that index i as the picked index.
  6. Repeat steps 3 to 5 on every call to pickIndex(), since the constructor’s work only happens once.

Java Program

Here is a complete, compilable implementation of RandomPickWithWeights in Java:

Java
import java.util.Random;

public class RandomPickWithWeights {
    private int[] prefixSums;
    private int totalSum;
    private Random random;

    public RandomPickWithWeights(int[] weights) {
        this.prefixSums = new int[weights.length];
        this.random = new Random();

        int sum = 0;
        for (int i = 0; i < weights.length; i++) {
            sum += weights[i];
            prefixSums[i] = sum;
        }
        this.totalSum = sum;
    }

    public int pickIndex() {
        int target = random.nextInt(totalSum) + 1;
        int low = 0;
        int high = prefixSums.length - 1;

        while (low < high) {
            int mid = low + (high - low) / 2;
            if (prefixSums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        int[] weights = {1, 3, 2, 4};
        RandomPickWithWeights picker = new RandomPickWithWeights(weights);

        int[] counts = new int[weights.length];
        int trials = 100000;

        for (int i = 0; i < trials; i++) {
            int index = picker.pickIndex();
            counts[index]++;
        }

        for (int i = 0; i < counts.length; i++) {
            double percentage = (counts[i] * 100.0) / trials;
            System.out.println("Index " + i + " picked " + counts[i] + " times (" + percentage + "%)");
        }
    }
}

Explanation of the Program

  • prefixSums is built once inside the constructor by running a cumulative sum over weights, so prefixSums[i] holds the sum of every weight up to and including index i.
  • totalSum stores the final cumulative value, the sum of every weight, and it defines the upper bound for the random target.
  • pickIndex() draws target from 1 to totalSum using random.nextInt(totalSum) + 1, since nextInt(bound) alone returns a value in [0, bound).
  • The binary search narrows low and high until it finds the smallest index whose prefixSums value is greater than or equal to target, which is exactly the interval containing target.
  • Because the constructor does all the O(n) work once, every call to pickIndex() only pays for an O(log n) binary search.

Step-by-Step Trace

Consider weights = {2, 5, 1}, which gives prefixSums = {2, 7, 8} and totalSum = 8. Suppose the random draw produces target = 6. Since 6 falls inside the interval (3, 7] owned by weights[1] = 5, the expected result of pickIndex() is index 1.

IterationlowhighmidprefixSums[mid]Action
102177 >= 6, so high = mid = 1
201022 < 6, so low = mid + 1 = 1
311––low == high, loop ends, return 1

At the end of each iteration, the search range [low, high] still contains the smallest index whose prefixSums value is greater than or equal to target, so the loop never discards the correct answer.

Examples

Example 1: Equal Weights (Uniform Distribution)

When every weight is equal, every index should be picked with roughly the same frequency.

Java
int[] weights = {1, 1, 1, 1};
RandomPickWithWeights picker = new RandomPickWithWeights(weights);
// prefixSums = {1, 2, 3, 4}, totalSum = 4
// Over many calls, pickIndex() returns 0, 1, 2, and 3 with roughly equal frequency (about 25% each)

Example 2: Skewed Weights

When one weight dominates the others, it should be picked far more often.

Java
int[] weights = {1, 9};
RandomPickWithWeights picker = new RandomPickWithWeights(weights);
// prefixSums = {1, 10}, totalSum = 10
// Index 1 is picked roughly 90% of the time and index 0 roughly 10% of the time,
// because 9 of the 10 possible target values (2 through 10) fall inside index 1's interval

Example 3: Single-Element Weights

With only one weight in the array, every call must return the same index.

Java
int[] weights = {5};
RandomPickWithWeights picker = new RandomPickWithWeights(weights);
int index = picker.pickIndex();
// prefixSums = {5}, totalSum = 5
// index is always 0, since there is only one interval and every possible target falls inside it

Common Mistakes to Avoid

These are the mistakes candidates actually make when implementing weighted random picking, not generic programming advice.

  • Drawing target from 0 instead of 1 – calling random.nextInt(totalSum) without the + 1 lets target equal 0, which falls outside every interval and silently skews the distribution. Always draw target in the range 1 to totalSum inclusive.
  • Replacing binary search with a linear scan – looping through prefixSums from the start still finds the correct index, but it costs O(n) per call and defeats the purpose of precomputing prefix sums. Use binary search so pickIndex() runs in O(log n).
  • Flipping the binary search comparison – writing prefixSums[mid] <= target instead of prefixSums[mid] < target moves high too aggressively and can return an index one position too low near interval boundaries. Keep the comparison as prefixSums[mid] < target when deciding to move low up.
  • Rebuilding prefixSums inside pickIndex() - recomputing the cumulative sums on every call wastes the O(n) work the constructor already finished once. Build prefixSums only inside the constructor and reuse it for every pick.

Edge Cases to Test

Walking through these boundary inputs unprompted is exactly the kind of habit interviewers look for.

  • Single-element weights array
  • All weights equal
  • Highly skewed weights (one very large weight, others very small)
  • Zero weight at some index
  • Sum of weights overflowing int range
  • Negative or zero total weight (invalid input)
  • Large number of repeated pickIndex() calls
  • Large weights array (binary search performance under heavy use)

Additional Considerations

The constructor runs in O(n) time and O(n) space, since it builds one prefix sum array the same length as weights. This cost is paid only once, no matter how many times pickIndex() is called afterward.

Each call to pickIndex() runs in O(log n) time with O(1) extra space, thanks to binary search. This is a significant improvement over a naive linear scan, which would cost O(n) per call.

If the sum of weights can exceed Integer.MAX_VALUE, switch prefixSums and totalSum to long, and replace random.nextInt(totalSum) with ThreadLocalRandom.current().nextLong(totalSum) to avoid overflow.

An alternative is the alias method, which achieves O(1) time per pick after an O(n) setup. It is faster per call but considerably more complex to implement correctly, so the prefix sum and binary search approach remains the standard interview-friendly solution.

Interview Follow-up Questions

A base solution is only the first ten minutes of the interview. Here are the follow-up questions that probe deeper.

  • What if weights can change after the object is constructed? - maintain the weights in a Fenwick tree (binary indexed tree) so both updating a weight and querying a prefix sum run in O(log n), instead of rebuilding the whole prefixSums array.
  • What if an index must never be picked twice? - after picking index i, zero out weights[i] and subtract it from totalSum, updating the Fenwick tree so pickIndex() never lands on that interval again.
  • What if the weights arrive as an unbounded stream? - use weighted reservoir sampling (the A-Res algorithm), assigning each incoming item a key based on a random draw and its weight, and keeping only the item with the largest key seen so far.
  • What if totalSum can exceed Integer.MAX_VALUE? - store prefixSums and totalSum as long, and use ThreadLocalRandom.current().nextLong(totalSum) instead of Random.nextInt(totalSum) to avoid overflow and stay safe under concurrent calls.

Conclusion

The Random Pick with Weights problem is a great example of turning a probability requirement into a search problem. By converting weights into cumulative ranges and using binary search to map a random draw onto those ranges, pickIndex() stays fast even as the number of picks grows.

Try adapting this same prefix sum and binary search pattern to other weighted selection problems, such as weighted sampling from a stream or picking a random node in a tree. You can learn more about array-based interview problems like this one on our Arrays category page.