Implement weighted random sampling with preprocessing

Q: Implement weighted random sampling with preprocessing

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

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

Provide an approach where pick() runs in O(log n) time after preprocessing.
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.

Implement weighted random sampling with preprocessing

Quick Overview

Weighted Random Sampling (with performance follow-up)

Requirements

Notes

Comments (0)