Katkat
Back

Implement np.random.choice

PinterestData Scientist · Technical Screen
EasyData ScientistTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to implement weighted random sampling from an array, focusing on probability distribution handling and efficient selection algorithms.

Problem Statement

Implement a function weighted_sample(items, weights) that returns a single item from the items list based on the probabilities provided in the weights list.

Function Signature

def weighted_sample(items, weights):
    # returns a single element from items
    pass

Requirements

  • items: A list of any hashable objects.
  • weights: A list of non-negative numbers representing the relative probability of each item. If weights are not provided, assume a uniform distribution.
  • The sum of weights does not necessarily have to be 1.0 (you must normalize them internally or account for the total sum).
  • If all weights are 0, or if inputs are mismatched in length, raise a ValueError.

Examples

# Example 1
items = ['A', 'B', 'C']
weights = [1, 4, 5]
# 'C' should be picked 50% of the time, 'B' 40%, 'A' 10%.

# Example 2
items = ['Red', 'Blue']
weights = [0.5, 0.5]
# Each should be picked 50% of the time.

Constraints

  • len(items) will be between 1 and 10^5.
  • weights elements will be non-negative.
  • You should use random.random() for generating values between [0.0, 1.0).

Hints

Hint 1

Calculate the cumulative sum (prefix sum) of the weights to represent the range [0, total_sum].

Hint 2

Generate a random floating-point number between 0 and the total sum of weights.

Hint 3

Use binary search (like `bisect_right`) on the cumulative sum array to find which interval the random number falls into.

Follow-up questions

  • How would you optimize this implementation if you needed to sample thousands of items from the same distribution repeatedly?
  • How does your implementation handle cases where the sum of weights is zero or negative?
  • What is the time complexity of your solution for a single sample versus the setup cost?