Katkat
Back

Implement weighted random index picker

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Implement weighted random index picker evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Design a class WeightedPicker that is initialized with an array of positive integer weights w and supports pick() that returns an index i with probability proportional to w[i]. Optimize for up to 10^7 picks after preprocessing 10^5 weights. Discuss preprocessing choices (prefix sums vs. alias method), random number generation, numerical stability, and time/space complexity. Extension: support addWeight(i, delta) and pick() with sublinear-time updates and queries.