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 ...
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) ?