Housie Magic -
This one arose from a party in my company, where we played Housie. The game goes like this - Every participant is distributed Housie tickets, each of which has 15 random numbers (distinct on a given ticket) printed on them. Numbers are between 1 to 100. Next, random numbers in the same range are selected and the numbers are called out. All participants who have the number on their ticket cross them. The first participant who gets all numbers crossed on their own ticket wins, and gets the prize.
Certainly, all numbers on the ticket are random and those called are random too. So everyone has an equal chance of winning. But there is a twist .....
What if you are allowed to take up more than one ticket ? You then get a bigger range of numbers to cross. Does that increase your chances of winning the prize ? Remember that to win, you need to have all numbers on any single ticket crossed.
Comments welcome ...
Sorting -
I ask this one for interviews and get varying answers... Given an array of integers (of size N), what is the most efficient algorithm to find out the 'K' largest numbers ? Note that K <= N, K > 0.
We don't want the largest K numbers to be sorted by themselves, just find the largest set. Is there a way to find the K numbers in less than O(N*K) ?
3 comments:
Housie Magic - The winning probability will increase with the more no. of tickets. Say among 10 people if i have one ticket then my probability is 1/10, but if i have 2 tickets it get increased to 2/10. With 10 tickts my probability will be 1.
I have a different take on this. Take into account that to win, one has to get ALL numbers crossed on any one ticket. I say that the probability of winning does not increase even if one participant has more housie tickets.
Thinking of an analogous situation will help. Consider that it rains continuously on a given day. There are ten buckets in which to gather the rain water, falling randomly in the buckets. One fellow takes hold of nine buckets and the other fellow takes up the remaining one bucket. The fellow who gets any one bucket full wins. Who has the winning chance ?
My bet is that both have equal chance. Sure, the fellow with nine buckets will accumulate a lot more water, but all water is getting distributed among the nine buckets (randomly). Similarly, the participant with nine housie tickets out of ten will have a lot of numbers to cross, but the chances of any one of his housie tickets being full is equal to that of one ticket with the other participant ...
What say ?
Hi Hrishi,
u have given a good example of buckets getting filled with rain water. as u've mentioned each bucket has the equal chance of getting full before others.
But consider it in this fasion:
there is only 1 bucket that will be full before other buckets. So, its like selecting a random bucket from the 10. If you have 9 buckets and I have only 1, then the probability of ur bucket being selected will be much more than that of mine. Isn't it??
So, same thing applies to housie tickets. If a person has more tickets, he has more chances of winning.
lets take another example. in our childhood there used to be different offers on chewinggums. if u collect 5 different stickers u will get a prize, or something similar. Now, if u buy only 5 chewinggums the chances are that you won't get 5 different stickers. Instead, the more chewinggums u buy, more likely u'll get different stickers. (I know some ppl who used to buy the whole bag of 100 chewinggums to get more "lucky")
so, as u see, the quantity does matter.
(disclaimer: i'm not good in probability :D)
regarding Sorting:
if we don't want to sort the array in place, then the complexity (in terms of memory usage) will be more, i think. because we'll need to store the sorted elements: to know 3rd largest number we need to know first 2 largest numbers. in general, to know K'th largest number we need to know first (K-1) largest numbers. so i think, sorting the array itself will be better performancewise.
well, i was going to explain different sorting algos here, but then there is a good comparison already available on wikipedia (http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms) so i'll leave it for u / readers to know the answer :D ... anyway i was never good in algos and frankly speaking i didn't understand much in the complexities of different algos given on that link :(
May b u can explain it to me some day... when we are going to meet we'll surely discuss abt this ;)
Post a Comment