find random country but probability of picking higher population country should be higher [duplicate]











up vote
0
down vote

favorite













This question already has an answer here:




  • Random number with Probabilities

    10 answers




I am working on below interview question:




If you're given a list of countries and its corresponding population,
write a function that will return a random country but the higher the
population of the country, the more likely it is to be picked at
random.




I came up with below logic:




Make two traversal on the list. In the first traversal, sum up all the
population of every location to get the total population TOTAL_POP. In
the second iteration, calculate % of each location's population
against TOTAL_POP. For example, if location A has a popoulation 'a'.
The percentage of population for A is (a/TOTAL_POP)*100.



Let's say, after these steps, we have the following values. Location A
= 35% B = 22% C = 19% D = 20% E = 4%



Note that the percentages should add up to 100.



Now, randomly generate a number 'n' between 1 and 100.



if 1 <= n <=35 OUTPUT A 36 <= n <= 57 OUTPUT B




Is there any better way to solve this problem? Algorithm or code anything is fine. Also if we are gonna implement this in Java then what is the best data structure to use here?










share|improve this question













marked as duplicate by Paul, DaveyDaveDave, EdChum, Jim Mischel algorithm
Users with the  algorithm badge can single-handedly close algorithm questions as duplicates and reopen them as needed.

StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;

$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');

$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Nov 20 at 13:47


This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.















  • This is perfectly fine. It is one of the standard ways to sample a discrete set with specified probabilities. A simple list (sorted by their ranges) is enough (do a binary search to find the country).
    – Nico Schertler
    Nov 20 at 7:29












  • why you should stick to 1 <= n <=35 , this is the not a fair random selection , you could have used "1 <= n <= 90" it is A, so it will have a higher probability to pick A. but it is even unfair random selection. i think what you need is build up a distribution . what you have come with is equivalent to the population distribution among countries.
    – hunter
    Nov 20 at 9:01










  • what about real figures rounding up to the same integer value ? which country are you going to select then ? And what about countries with a population < 1% ?
    – Laurent S.
    Nov 20 at 11:55















up vote
0
down vote

favorite













This question already has an answer here:




  • Random number with Probabilities

    10 answers




I am working on below interview question:




If you're given a list of countries and its corresponding population,
write a function that will return a random country but the higher the
population of the country, the more likely it is to be picked at
random.




I came up with below logic:




Make two traversal on the list. In the first traversal, sum up all the
population of every location to get the total population TOTAL_POP. In
the second iteration, calculate % of each location's population
against TOTAL_POP. For example, if location A has a popoulation 'a'.
The percentage of population for A is (a/TOTAL_POP)*100.



Let's say, after these steps, we have the following values. Location A
= 35% B = 22% C = 19% D = 20% E = 4%



Note that the percentages should add up to 100.



Now, randomly generate a number 'n' between 1 and 100.



if 1 <= n <=35 OUTPUT A 36 <= n <= 57 OUTPUT B




Is there any better way to solve this problem? Algorithm or code anything is fine. Also if we are gonna implement this in Java then what is the best data structure to use here?










share|improve this question













marked as duplicate by Paul, DaveyDaveDave, EdChum, Jim Mischel algorithm
Users with the  algorithm badge can single-handedly close algorithm questions as duplicates and reopen them as needed.

StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;

$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');

$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Nov 20 at 13:47


This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.















  • This is perfectly fine. It is one of the standard ways to sample a discrete set with specified probabilities. A simple list (sorted by their ranges) is enough (do a binary search to find the country).
    – Nico Schertler
    Nov 20 at 7:29












  • why you should stick to 1 <= n <=35 , this is the not a fair random selection , you could have used "1 <= n <= 90" it is A, so it will have a higher probability to pick A. but it is even unfair random selection. i think what you need is build up a distribution . what you have come with is equivalent to the population distribution among countries.
    – hunter
    Nov 20 at 9:01










  • what about real figures rounding up to the same integer value ? which country are you going to select then ? And what about countries with a population < 1% ?
    – Laurent S.
    Nov 20 at 11:55













up vote
0
down vote

favorite









up vote
0
down vote

favorite












This question already has an answer here:




  • Random number with Probabilities

    10 answers




I am working on below interview question:




If you're given a list of countries and its corresponding population,
write a function that will return a random country but the higher the
population of the country, the more likely it is to be picked at
random.




I came up with below logic:




Make two traversal on the list. In the first traversal, sum up all the
population of every location to get the total population TOTAL_POP. In
the second iteration, calculate % of each location's population
against TOTAL_POP. For example, if location A has a popoulation 'a'.
The percentage of population for A is (a/TOTAL_POP)*100.



Let's say, after these steps, we have the following values. Location A
= 35% B = 22% C = 19% D = 20% E = 4%



Note that the percentages should add up to 100.



Now, randomly generate a number 'n' between 1 and 100.



if 1 <= n <=35 OUTPUT A 36 <= n <= 57 OUTPUT B




Is there any better way to solve this problem? Algorithm or code anything is fine. Also if we are gonna implement this in Java then what is the best data structure to use here?










share|improve this question














This question already has an answer here:




  • Random number with Probabilities

    10 answers




I am working on below interview question:




If you're given a list of countries and its corresponding population,
write a function that will return a random country but the higher the
population of the country, the more likely it is to be picked at
random.




I came up with below logic:




Make two traversal on the list. In the first traversal, sum up all the
population of every location to get the total population TOTAL_POP. In
the second iteration, calculate % of each location's population
against TOTAL_POP. For example, if location A has a popoulation 'a'.
The percentage of population for A is (a/TOTAL_POP)*100.



Let's say, after these steps, we have the following values. Location A
= 35% B = 22% C = 19% D = 20% E = 4%



Note that the percentages should add up to 100.



Now, randomly generate a number 'n' between 1 and 100.



if 1 <= n <=35 OUTPUT A 36 <= n <= 57 OUTPUT B




Is there any better way to solve this problem? Algorithm or code anything is fine. Also if we are gonna implement this in Java then what is the best data structure to use here?





This question already has an answer here:




  • Random number with Probabilities

    10 answers








java algorithm data-structures






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked Nov 20 at 7:26









john

1,8001667148




1,8001667148




marked as duplicate by Paul, DaveyDaveDave, EdChum, Jim Mischel algorithm
Users with the  algorithm badge can single-handedly close algorithm questions as duplicates and reopen them as needed.

StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;

$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');

$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Nov 20 at 13:47


This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.






marked as duplicate by Paul, DaveyDaveDave, EdChum, Jim Mischel algorithm
Users with the  algorithm badge can single-handedly close algorithm questions as duplicates and reopen them as needed.

StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;

$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');

$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Nov 20 at 13:47


This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.














  • This is perfectly fine. It is one of the standard ways to sample a discrete set with specified probabilities. A simple list (sorted by their ranges) is enough (do a binary search to find the country).
    – Nico Schertler
    Nov 20 at 7:29












  • why you should stick to 1 <= n <=35 , this is the not a fair random selection , you could have used "1 <= n <= 90" it is A, so it will have a higher probability to pick A. but it is even unfair random selection. i think what you need is build up a distribution . what you have come with is equivalent to the population distribution among countries.
    – hunter
    Nov 20 at 9:01










  • what about real figures rounding up to the same integer value ? which country are you going to select then ? And what about countries with a population < 1% ?
    – Laurent S.
    Nov 20 at 11:55


















  • This is perfectly fine. It is one of the standard ways to sample a discrete set with specified probabilities. A simple list (sorted by their ranges) is enough (do a binary search to find the country).
    – Nico Schertler
    Nov 20 at 7:29












  • why you should stick to 1 <= n <=35 , this is the not a fair random selection , you could have used "1 <= n <= 90" it is A, so it will have a higher probability to pick A. but it is even unfair random selection. i think what you need is build up a distribution . what you have come with is equivalent to the population distribution among countries.
    – hunter
    Nov 20 at 9:01










  • what about real figures rounding up to the same integer value ? which country are you going to select then ? And what about countries with a population < 1% ?
    – Laurent S.
    Nov 20 at 11:55
















This is perfectly fine. It is one of the standard ways to sample a discrete set with specified probabilities. A simple list (sorted by their ranges) is enough (do a binary search to find the country).
– Nico Schertler
Nov 20 at 7:29






This is perfectly fine. It is one of the standard ways to sample a discrete set with specified probabilities. A simple list (sorted by their ranges) is enough (do a binary search to find the country).
– Nico Schertler
Nov 20 at 7:29














why you should stick to 1 <= n <=35 , this is the not a fair random selection , you could have used "1 <= n <= 90" it is A, so it will have a higher probability to pick A. but it is even unfair random selection. i think what you need is build up a distribution . what you have come with is equivalent to the population distribution among countries.
– hunter
Nov 20 at 9:01




why you should stick to 1 <= n <=35 , this is the not a fair random selection , you could have used "1 <= n <= 90" it is A, so it will have a higher probability to pick A. but it is even unfair random selection. i think what you need is build up a distribution . what you have come with is equivalent to the population distribution among countries.
– hunter
Nov 20 at 9:01












what about real figures rounding up to the same integer value ? which country are you going to select then ? And what about countries with a population < 1% ?
– Laurent S.
Nov 20 at 11:55




what about real figures rounding up to the same integer value ? which country are you going to select then ? And what about countries with a population < 1% ?
– Laurent S.
Nov 20 at 11:55












1 Answer
1






active

oldest

votes

















up vote
1
down vote













You can use TreeMap for this, it is O(log n) and has a handy api. Something like:



TreeMap<Integer, Country> map = new TreeMap<>();
map.put(percentCountry1, country1);
map.put(percentCountry1 + percentCountry2, country2);
// ...

int random = (new Random()).nextInt(100);
Country country = map.ceilingEntry(random).getValue();





share|improve this answer



















  • 1




    You don't need to traverse once to find total population, and then compute percentages. This solution works if you replace percentCountry1 etc above with populationCountry1 (etc) and draw a random number between 1 and total world population (using double or 64-bit integer for the population, since 32-bit integer do not suffice).
    – Hans Olsson
    Nov 20 at 9:10


















1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
1
down vote













You can use TreeMap for this, it is O(log n) and has a handy api. Something like:



TreeMap<Integer, Country> map = new TreeMap<>();
map.put(percentCountry1, country1);
map.put(percentCountry1 + percentCountry2, country2);
// ...

int random = (new Random()).nextInt(100);
Country country = map.ceilingEntry(random).getValue();





share|improve this answer



















  • 1




    You don't need to traverse once to find total population, and then compute percentages. This solution works if you replace percentCountry1 etc above with populationCountry1 (etc) and draw a random number between 1 and total world population (using double or 64-bit integer for the population, since 32-bit integer do not suffice).
    – Hans Olsson
    Nov 20 at 9:10















up vote
1
down vote













You can use TreeMap for this, it is O(log n) and has a handy api. Something like:



TreeMap<Integer, Country> map = new TreeMap<>();
map.put(percentCountry1, country1);
map.put(percentCountry1 + percentCountry2, country2);
// ...

int random = (new Random()).nextInt(100);
Country country = map.ceilingEntry(random).getValue();





share|improve this answer



















  • 1




    You don't need to traverse once to find total population, and then compute percentages. This solution works if you replace percentCountry1 etc above with populationCountry1 (etc) and draw a random number between 1 and total world population (using double or 64-bit integer for the population, since 32-bit integer do not suffice).
    – Hans Olsson
    Nov 20 at 9:10













up vote
1
down vote










up vote
1
down vote









You can use TreeMap for this, it is O(log n) and has a handy api. Something like:



TreeMap<Integer, Country> map = new TreeMap<>();
map.put(percentCountry1, country1);
map.put(percentCountry1 + percentCountry2, country2);
// ...

int random = (new Random()).nextInt(100);
Country country = map.ceilingEntry(random).getValue();





share|improve this answer














You can use TreeMap for this, it is O(log n) and has a handy api. Something like:



TreeMap<Integer, Country> map = new TreeMap<>();
map.put(percentCountry1, country1);
map.put(percentCountry1 + percentCountry2, country2);
// ...

int random = (new Random()).nextInt(100);
Country country = map.ceilingEntry(random).getValue();






share|improve this answer














share|improve this answer



share|improve this answer








edited Nov 20 at 8:23

























answered Nov 20 at 8:16









RoberMP

701615




701615








  • 1




    You don't need to traverse once to find total population, and then compute percentages. This solution works if you replace percentCountry1 etc above with populationCountry1 (etc) and draw a random number between 1 and total world population (using double or 64-bit integer for the population, since 32-bit integer do not suffice).
    – Hans Olsson
    Nov 20 at 9:10














  • 1




    You don't need to traverse once to find total population, and then compute percentages. This solution works if you replace percentCountry1 etc above with populationCountry1 (etc) and draw a random number between 1 and total world population (using double or 64-bit integer for the population, since 32-bit integer do not suffice).
    – Hans Olsson
    Nov 20 at 9:10








1




1




You don't need to traverse once to find total population, and then compute percentages. This solution works if you replace percentCountry1 etc above with populationCountry1 (etc) and draw a random number between 1 and total world population (using double or 64-bit integer for the population, since 32-bit integer do not suffice).
– Hans Olsson
Nov 20 at 9:10




You don't need to traverse once to find total population, and then compute percentages. This solution works if you replace percentCountry1 etc above with populationCountry1 (etc) and draw a random number between 1 and total world population (using double or 64-bit integer for the population, since 32-bit integer do not suffice).
– Hans Olsson
Nov 20 at 9:10



Popular posts from this blog

404 Error Contact Form 7 ajax form submitting

How to know if a Active Directory user can login interactively

TypeError: fit_transform() missing 1 required positional argument: 'X'