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?
java algorithm data-structures
asked Nov 20 at 7:26
john
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.
add a comment |
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?
java algorithm data-structures
asked Nov 20 at 7:26
john
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.
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
add a comment |
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?
java algorithm data-structures
asked Nov 20 at 7:26
john
1,8001667148
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
java algorithm data-structures
asked Nov 20 at 7:26
john
1,8001667148
asked Nov 20 at 7:26
john
1,8001667148
asked Nov 20 at 7:26
john
1,8001667148
asked Nov 20 at 7:26
john
1,8001667148
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
add a comment |
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
add a comment |
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();
answered Nov 20 at 8:16
RoberMP
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
add a comment |
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();
answered Nov 20 at 8:16
RoberMP
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
add a comment |
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();
answered Nov 20 at 8:16
RoberMP
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
add a comment |
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();
answered Nov 20 at 8:16
RoberMP
701615
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();
answered Nov 20 at 8:16
RoberMP
701615
edited Nov 20 at 8:23
answered Nov 20 at 8:16
RoberMP
701615
answered Nov 20 at 8:16
RoberMP
701615
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
add a comment |
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
add a comment |
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