Find Probability


  • 1
    R

    Given a list of countries with their population.
    For example: USA: 3M, Russia: 1.5M, China: 0.75M

    Write a function that calculates probability of population and give that country.
    For example: USA= 2xRussia
    so the times usa should be selected should be 2(Russia) and 4(China)
    Each function call is independent of the previous call.

    You can use getRandomNumber(int min, int max)


  • 0
    N

    The question is ambiguous. Need more info about why we need getRandomNumber method? and what is the expected output and input?

    Assuming the given input is a list of countries and their corresponding population in millions. We could calculate the probability of population relative to a particular country(input).

    def get_proability(country):
        country_population={'usa': 3, 'russia' = 1.5, 'china': 0.75}
        probability_table = {}
        input_country_population = country_population.get(country)
    
        for country, population in country_population:
        	probability_table[country] = input_country_population / population
    
        return probability_table
    

    You can iterate through probaility_table and print times(country)


  • 0

    @nadar It is not exactly the case, reemak discuss. Why do we need getRandomNumber?
    I understand that USA is selected with probability 3/(3+1.5+0.75), Russia 1.5/(3+1.5+0.75) , China with 0.75/(3+1+0.75)
    But this senetense3 is unclear so the times usa should be selected should be 2(Russia) and 4(China) and You can use getRandomNumber(int min, int max)

    @nadar please, give more explantation


  • -1
    R

    @nadar your answer is not accurate.
    how are you going to know which country is called how many times?

    all your are doing is population/total population of all countries and storing it in the array.

    You have to make use of randomNumber function


  • 0
    R

    Solution I can think of is:

    Pass min and max value in a particular way so that it returns a number which is the population of that particular country.
    Main modification is in getRandomNumber function as per me


  • 0

    @reemak can you explain better the random process. What is selected from where, how -with repeatance or not, what distribution and so on. Thanks. you mentioned that somebody select each contry, how does it happen?


  • 0
    N

    @elmirap update my reply. The question is ambiguous. I went with an assumption of given countries and their population and a country against which the probability has to be calculated.


  • 0

    @nadar I agree with you. I am waiting for the author's clarifications.


  • 0
    R

    @elmirap @nadar: this is all the details i have about the question and was asked to solve


  • 1

    @reemak How similar is your problem to this one?

    You're given a list of countries and its  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.
    
    

  • 0
    K

    Ok I have an intuition about the solution, will code up a solution shortly can someone discuss the solution with me.

    How about we sort the population table by population reverse order, then we assign ranges of integers such that every country has a start and end.

    # code block
    Map<String, Integer> country = {A:30, B:20, C:10};
    long sum = 30 + 20 + 10;
    Map<String, Range>  ranges  = {A:[0,29], B:[30, 49], C:[50, 59]}
    Random r = new Random();
    int num = r.nextInt(sum);
    Binary search on the correct interval. O(log N) and return the country associated with the range.
    
    So:
    num = 11 -> A
    num = 12 -> A
    num = 31 -> B
    num = 59 -> C
    

    and so the country with the larger population has a larger chance of being picked up.
    one defect about this approach is the country population is in millions so we may overflow if we are not careful.


  • 0
    K

    @elmirap I tried a solution, if you have a solution please share.
    Thanks


  • 0

    @Karibo I don't have the solution, but I think you are on the right way. You needn't search with binary search because you know the range boundaries in advance
    A - [0..29]
    B-[30..49]
    C-[50...59]


  • 0
    K

    @elmirap

    I ran some tests and in fact the probabilities are quite close run it you will see that as the sample size increase the probabilities are closer to the actual values (Large number theorem)

    Note : I think we will need Binary search as our random number will fall inside a range so to find the valid range we have to BS for it.

    package discussion;
    
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Random;
    
    public class CountryPopulation {
    
    	class Range {
    		String country;
    		int start, end;
    
    		public Range(String country, int start, int end) {
    			this.country = country;
    			this.start = start;
    			this.end = end;
    		}
    	}
    
    	private Map<String, Long> country;
    	private Range[] ranges;
    	private Random r;
    	private int sum, size;
    
    	public CountryPopulation(Map<String, Integer> population) {
    		if (population == null || population.isEmpty())
    			throw new IllegalArgumentException("No null params.");
    		this.size = population.size();
    		this.ranges = new Range[size];
    		this.country = new HashMap<String, Long>();
    		int i = 0;
    		this.sum = 0;
    		for (String key : population.keySet()) {
    			int start = sum;
    			int end = sum + population.get(key) - 1;
    			ranges[i++] = new Range(key, start, end);
    			sum += population.get(key);
    		}
    		this.r = new Random(System.nanoTime());
    	}
    
    	public String nextCountry() {
    		return find(r.nextInt(sum)).country;
    	}
    
    	private Range find(int val) {
    		int l = 0, h = size - 1;
    		while (l <= h) {
    			int m = (l + h) >> 1;
    			if (val > ranges[m].end)
    				l = m + 1;
    			else if (val < ranges[m].start)
    				h = m - 1;
    			else
    				return ranges[m];
    		}
    		return null;
    	}
    
    	public static void main(String[] args) {
    		Map<String, Integer> map = new HashMap<String, Integer>();
    		map.put("A", 300);
    		map.put("B", 20);
    		map.put("C", 10);
    		CountryPopulation cp = new CountryPopulation(map);
    		Map<String, Integer> cnt = new HashMap<String, Integer>();
    		int sum = 0, size = 10000000;
    		for (String key : map.keySet()) {
    			cnt.put(key, 0);
    			sum += map.get(key);
    		}
    		for (int i = 0; i < size; i++) {
    			String key = cp.nextCountry();
    			cnt.put(key, cnt.get(key) + 1);
    		}
    
    		for (String key : cnt.keySet()) {
    			System.out.println(key + " : " + cnt.get(key));
    			System.out.println("Population % : " + 1.0 * map.get(key) / sum);
    			System.out.println("Propaility % : " + 1.0 * cnt.get(key) / size);
    		}
    	}
    }

Log in to reply
 

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