- a list of countries with population data (eg.
Russia:100, US:50, Mexico: 150)
- 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)))]
@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.
@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.
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.