Design a weighted random value generator

Weighted random value generator

Design a generic component that stores values with integer weights and can return a random value with probability proportional to its weight.

Requirements

• Support adding a value with a weight:
  • add(value: T, weight: Int)
• Support returning a random value:
  • pick(): T (name can vary)
• If the stored pairs are [(1,1), (2,1), (5,3)] , then probabilities are:
  • 1 : 20%, 2 : 20%, 5 : 60%
• If you then add (3,5) , probabilities become:
  • 1 : 10%, 2 : 10%, 5 : 30%, 3 : 50%

Focus

Prioritize clarity, maintainability, and extensibility over micro-optimizing performance.

Follow-up

Add an API that supports expiration:

• addWithExpiry(value: T, weight: Int, expireAfterMs: Int)
• After the expiration time elapses, that added weight contribution should no longer affect pick() .

Clarifications to address (state assumptions)

• Whether weight is always positive.
• Whether adding an existing value merges weight or stores multiple entries.
• Expected behavior when there are no active (non-expired) entries.