Choose a color with probability proportionate to its weight in a group of colors Input: An array of colors with weights. e.g [['red', 10], ['blue', 20], ['green', 30]]

Output: A random color from the array, based on it's proportion to the other colors. So for the example above, red should show up 1/6 of the time, blue 2/6, green 3/6.

I was asked this during an interview. After talking to that interviewer I went from an O(n2) solution to this, which runs in O(n). I feel like there should be a better way?

def random_color(colors_with_weights)
  probabilities = {}
  count = 0
  colors_with_weights.each do |color_weight|
    probabilities[count..count+color_weight[1]] = color_weight[0]
    count = count + color_weight[1]
  end
  random_number = rand(count)
  random_range = probabilities.keys.find { |k| k.include?(random_number) }
  probabilities[random_range]
end

colors_with_weights = [['red', 10], ['blue', 20], ['green', 30]]
puts random_color(colors_with_weights)
I can't think of a better algorithm.  There is a minor bug, though: you are using inclusive-inclusive ranges, when they should be inclusive-exclusive ranges.  That means that you've overweighted red by \$\frac{1}{60}\$ and underweighted green by \$\frac{1}{60}\$.

The way it the algorithm is expressed could be tweaked a bit.


The count isn't counting elements; it's more of a sum.
The block could accept two parameters |color, weight| to automatically destructure |color_weight|.
The hash isn't really being used for a lookup, so I would just keep it as an array.




def random_color(colors_with_weights)
  sum = 0
  colors_with_cumul_weights = colors_with_weights.collect do |color, weight|
    [color, sum ... (sum += weight)]
  end
  rand_num = rand(sum)
  colors_with_cumul_weights.find { |color, range| range === rand_num }.first
end


In an interview situation, I'd just accept your code as a fine answer.