Katkat
Back

Generate Weighted Random Keys With Add And Remove

NuroSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to efficiently manage a collection of weighted items and perform random sampling based on those weights, requiring O(log N) updates and lookups.

Weighted Random Sampler

Design a data structure that supports the following operations for a set of keys, where each key has an associated positive weight:

  1. add(key, weight): Adds a key with the given weight. If the key already exists, update its weight.
  2. remove(key): Removes the key from the data structure.
  3. pick(): Returns one of the existing keys randomly, where the probability of picking a key is proportional to its weight (weight / total_weight).

Constraints

  • The number of keys N can be up to 10^5.
  • add and remove operations should ideally be O(log N).
  • pick should ideally be O(log N).

Examples

# Initialize with empty structure
sampler = WeightedSampler()
sampler.add("A", 10)
sampler.add("B", 20)

# pick() returns "A" or "B". The probability of "B" is 2/3.
sampler.remove("A")
# pick() will now always return "B".

Edge Cases

  • What happens when pick() is called and the structure is empty?
  • Handling floating-point weights vs. integer weights.
  • The behavior when remove() is called on a non-existent key.

Hints

Hint 1

Consider maintaining the weights in a list and calculating their prefix sums to allow for range-based sampling.

Hint 2

Since prefix sums need to be updated when a weight changes, a Fenwick Tree (Binary Indexed Tree) or a Segment Tree can handle both updates and prefix sum queries in logarithmic time.

Hint 3

To map a random value (0 to total_weight) to a key, use binary search over the prefix sums.

Follow-up questions

  • How would you modify the data structure if weights can be zero or negative?
  • If 'pick' is called significantly more often than 'add' or 'remove', can you optimize the lookup time to O(1) at the cost of slower updates?
  • How would you handle the case where the total weight exceeds the maximum capacity of a 64-bit integer?