Solution to the Weighted Cities Problem

As promised, here's the code for the Weighted Cities Problem.

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

import java.util.*;

public class City {

String CityName;
int Population; //cumulative population

City (String S, int pop){

CityName = S;
Population = pop;
}
}

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

import java.util.*;

class CityGenerator {

List Cities;
List CumulativePops; //cumulative population
Random rGen;
int CurrentTotalPopulation;
int FinalTotalPopulation;

public CityGenerator(List Cities_List) {
Cities = Cities_List;
City CurrentCity;
rGen = new Random();
CumulativePops = new ArrayList();
CurrentTotalPopulation = 0;

//Calculate the cumulative totals
for (City c : Cities){
CurrentCity = c;
CurrentTotalPopulation += CurrentCity.Population;
CumulativePops.add(CurrentTotalPopulation);
}
FinalTotalPopulation = CurrentTotalPopulation;
}

public City getCity()
{
//runs in log(n) time as it uses a binary search
int randCumulativePop = rGen.nextInt(FinalTotalPopulation);
int cityIndex = Collections.binarySearch(CumulativePops,randCumulativePop);
//binarySearch returns minus one unless its an exact match
if(cityIndex < 0) {
cityIndex *= -1;
cityIndex -= 1;
}
City city = Cities.get(cityIndex);
return (city);
}


public String verifySample(int sampleSize)
{
int citycount = Cities.size();
int[] IncrementTotals = new int[citycount];
int CityIndex;
Integer count;
City C1, C2;
HashMap hm = new HashMap();

for(int i=0;i C1 = getCity();
count = (Integer)(hm.get(C1));
if (count == null) {hm.put(C1, 1);}
else {hm.put(C1,new Integer(count.intValue()+1)); }
}

String output = new String();
for(int j=0;j C2 = Cities.get(j);
output += C2.CityName + ": " + hm.get(C2) + "\n";
}
return output;
}

public static void CreateData (List Cities) {

Cities.add(new City("San Francisco", 20000));
Cities.add(new City("New York", 50000));
Cities.add(new City("Boston", 20000));
Cities.add(new City("Toronto", 7500));
Cities.add(new City("Cambridge", 2500));
}

public static void main(String[] args) {

List Cities = new ArrayList();
CreateData(Cities); //Add sample data
CityGenerator cGen = new CityGenerator(Cities);
System.out.println(cGen.verifySample(100000)); //Verify with large test run
}
}


Here's a brief summary of what's happening. Define a class City that associates each cities name with its population, and create a List of all the cities in your sample data. Pass this to the constructor of CityGenerator, and use it to build a second list of cumulative totals. From here, all the action happens in the getCity() method. In this method, we generate a random number between 1 and the final total population, then we do a binary search on our list of cumulative totals to pull out a random city name. This approach gives us each city name with a proability that is proportional to its population over total population of all the cities, which was the requirement. The method verifySample() simply runs a high volume of tests, and stores all the results in a frequency table, implemented via a HashMap.