# Given Country Population Generate Distribution

• Given:

1. a list of countries with population data (eg. `Russia:100, US:50, Mexico: 150`)
2. getRandom API `getRandomNumber(int min, int max)`

Write a function that returns country names, so that the probability of each name's occurrence conforms to the distribution of the given population data (eg. 1/3 of the times returns Russia, 1/6 of the times returns returns US, 1/2 of the times returns returns Mexico).

• @hellowworld is this phone interview or onsite?

• My R code

``````popName=c("Russia","US","Mexico")
pop=c(100,50,150)
popName[which(cumsum(pop) > floor(runif(1,0,1)*sum(pop)))[1]]

``````

• @Chengcheng.Pei It is a phone interview question. I came up with the idea to generate a number from `getRandomNumber(1, sum)` and then check which range does it fall in. But the answer seems odd.

• But the answer seems odd.

thanks. but why `But the answer seems odd.`? what is the odd answer? I have the same idea with you.

• This post is deleted!

• @hellowworld : Yes, that idea is quite correct. My script does the same thing.

• Seems like very similar to a load balancer problem I saw before.

We can use binary search if there are a lot of countries.

• @wish Exactly

We can keep an array A with the running sum of the population like this:
A = [100, 100+50, 100+50+150]

Next, we call `getRandomNumber(0,total)` and find which interval contains the random number. Since A is sorted by definition, you can use a binary search to improve the time complexity.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.