Katkat
Back

Design a weighted random value generator

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to implement efficient weighted random selection using prefix sums and binary search, and handling state updates.

Problem Statement

Design a class WeightedSelector that provides a method to select an item based on its associated weight. The probability of choosing an item should be directly proportional to its weight relative to the sum of all weights.

Implement the following methods:

  1. add_item(item: str, weight: int): Adds an item with a given weight. If the item already exists, its weight is updated.
  2. pick_item() -> str: Randomly returns an item based on its weight probability.

Constraints

  • weight is a positive integer.
  • pick_item() should be efficient, preferably O(log N) where N is the number of items.
  • Minimize memory usage for large numbers of items.

Examples

# Setup
selector = WeightedSelector()
selector.add_item("A", 1)
selector.add_item("B", 3)

# pick_item() distribution:
# "A" has 25% chance (1 / (1+3))
# "B" has 75% chance (3 / (1+3))

Edge Cases

  • What happens if pick_item() is called when no items have been added?
  • How does the implementation handle a large number of add_item calls versus pick_item calls?
  • Consider the behavior when weights are updated to zero or negative values.

Hints

Hint 1

Consider storing a list of prefix sums where each element is the sum of weights up to that index.

Hint 2

Once you have a prefix sum array, you can generate a random number between 0 and the total weight and use binary search to find the corresponding item range.

Hint 3

Since items can be updated, consider using a Hash Map to store the mapping between items and their current index in the prefix sum array.

Follow-up questions

  • How would you optimize the solution if `pick_item` is called significantly more often than `add_item`?
  • If the weights change frequently, how would you maintain the prefix sum array without rebuilding it from scratch every time?
  • How would you modify your design if you needed to support an item's weight decaying over time?