Red and Blue Marbles

Question: You have 50 red marbles, 50 blue marbles and 2 jars. One of the jars is chosen at random and then one marble will be chosen from that jar at random. How would you maximize the chance of drawing a red marble? What is the probability of doing so? All 100 marbles should be placed in the jars.
Answer: Seems tricky at first right? Given that the number of red and blue marbles are the same, you would tend to think that the odds are 50-50. You would try different combinations, such as 25 of each colored marble in a jar or putting all red marbles in one jar and all the blue in the other. You would still end up with a chance of 50%.
So lets think of a better way to distribute the marbles. What if you put a single red marble in one jar and the rest of the marbles in the other jar? This way, you are guaranteed at least a 50% chance of getting a red marble (since one marble picked at random, doesn’t leave any room for choice).  Now that you have 49 red marbles left in the other jar, you have a nearly even chance of picking a red marble (49 out of 99).
So let’s calculate the total probability.
P( red marble ) = P( Jar 1 ) * P( red marble in Jar 1 ) + P( Jar 2 ) * P( red marble in Jar 2 )
P( red marble ) = 0.5 * 1 + 0.5 * 49/99
P( red marble ) = 0.7474
Thus, we end up with ~75% chance of picking a red marble.

Comments

Post a Comment

Popular posts from this blog

First Non-Repeated Character

Question:  Write an algorithm to find the first non-repeated character in a string. For example, the first non-repeated character in the string ‘abcdab’ is ‘c’. Answer:  Seems trivial enough right? If a character is repeated, we should be able to search the string to determine if that character appears again. So if we go about doing this for every character in the string, our worst case run time would O(n^2). Here is some code to show this logic. char returnFirstNonRepeatedChar( char * str ) { int i, repeated = 0; int len = strlen(str); for( i = 0; i < len; i++ ) { repeated = 0; for( j = 0; j < len; j++ ) { if( i != j && str[i] == str[j] ) { repeated = 1; break; } } if( repeated == 0 ) { // Found the first non-repeated character return str[i]; } } return ''; } This approach seems to work perfectly well. But
Read more

Pick a Random Byte

Question:  You have a stream of bytes from which you can read one byte at a time. You only have enough space to store one byte. After processing those bytes, you have to return a random byte. Note: The probability of picking any one of those bytes should be equal. Answer:  Since we can only store one byte at a time, we have to be able to work with the bytes as they come in. We can’t store everything, count the number of bytes and pick one. That would be too easy wouldn’t it? Let’s think it through. We don’t know how many bytes there are, so at any point in time we should have a random byte picked from all the bytes we have seen so far. We shouldn’t worry about the total number of bytes at any time. When we get the first byte, it is simple. There is only one so we store it. When we get the second one, it has 1/2 probability of being picked and the one we have stored has a 1/2 probability of being picked (we can use any programming language’s built-in random function). After pick
Read more

Search in a sorted rotated array

Question:  Implement a search function for a sorted rotated array. Duplicates are allowed. Returning any one of the duplicates is acceptable. Answer:  We can do a binary search with some modified checks. public int rotatedSearch(int[] values, int start, int end, int x){ if(values[start] == x){ return start; } else if(values[end] == x){ return end; } else if(end - start == 1) { return -1; } int middle = (start + end) / 2; if(values[start] <= values[middle]){ if(x <= values[middle] && x >= values[start]){ return rotatedSearch(values, start, middle, x); } else { return rotatedSearch(values, middle, end, x); } } else if(values[middle] <= values[end]){ if(x >= values[middle] && x <= values[end] ){ return rotatedSearch(values, middle, end, x); } else { return rotatedSearch(values, start,
Read more