Katkat
Back

Design dynamic weighted random sampling with updates

CitadelSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates a candidate's ability to design and analyze dynamic data structures that support weighted random sampling with inserts and deletes, testing skills in algorithm design, complexity analysis, and randomized sampling under large numeric constraints.

Problem: Support weighted random sampling with insert/delete

Design a data structure that maintains a dynamic set of items, each with a positive integer weight, and supports:

  1. insert(id, weight)
  • Adds a new item id with the given weight.
  • If id already exists, you may either reject or treat it as an update (state your choice).
  1. delete(id)
  • Removes the item if it exists.
  1. sample() -> id
  • Returns an id chosen randomly such that:

[ P(id) = \frac{weight(id)}{\sum_j weight(j)} ]

Requirements

  • Target time complexity: O(log n) per operation.
  • Must handle up to ~10^5 operations.
  • Weights can be large (e.g., up to 10^9); total weight may exceed 32-bit.
  • sample() should be unbiased given an ideal RNG.

Notes

  • You may assume access to a function randInt(1, totalWeight) that returns a uniform integer in that range.
  • Clearly define how you map item IDs to internal indices as the set changes over time.