Weighted Cities Problem

Here's an interesting challenge problem:

A given list of city names and their corresponding populations is provided. Write a method in Java that will return a random city from a list of cities. Ensure that for each call to this method, a city name is returned with probability proportional to its population over total population of all cities. Your final solution should be working code that runs in O(log N) time.

Example:

City Name Population

San Francisco = 20,000
New York = 50,000
Boston = 20,000
Toronto = 7,500
Cambridge = 2,500

------------------------

run (10,000 iterations)

San Francisco: 1898
New York: 4943
Boston: 2140
Toronto: 768
Cambridge: 251

I'll publish a solution to this in a few days.