load_balancer.rb

# Insertions, Removals and Random Access in O(1),
# assuming the complexity of growing an array is negligible.
# Otherwise a constant size array with a max-size could be used.
class LoadBalancer
  def initialize
    @map, @vector = {}, []
  end

  def insert(val)
    @map[val] = @vector.length
    @vector << val
  end

  def remove(val)
    # remove the value and the last element from the vector
    index, last, @map[val] = @map[val], @vector.pop, nil

    # re-insert the last element and update the map, only if it is not the one we are removing.
    @vector[index], @map[last] = last, index if last != val
  end

  def getRand
    @vector[rand @vector.length]
  end
end

l = LoadBalancer.new
l.insert :a
l.insert :b
l.insert :c

puts '---'
puts l.getRand
puts l.getRand
puts l.getRand
puts l.getRand
puts l.getRand
puts l.getRand

l.remove :b
puts '---'
puts l.getRand
puts l.getRand
puts l.getRand
puts l.getRand
puts l.getRand
puts l.getRand

l.remove :a
puts '---'
puts l.getRand
puts l.getRand
puts l.getRand
puts l.getRand
puts l.getRand
puts l.getRand

l.remove :c
puts '---'
puts l.getRand
puts l.getRand
puts l.getRand
puts l.getRand
puts l.getRand
puts l.getRand