wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Yahoo Questions
        
(Message started by: arunrambo2000 on Jun 3^rd, 2007, 1:33pm)

Title: Yahoo Questions
Post by arunrambo2000 on Jun 3^rd, 2007, 1:33pm

These were the list of questions asked @ Yahoo....
@the initial round

1. In a village in each family they give birth to children till they
get a boy. IF girl child they try again. What is the ratio of boys to
girls.

2. 2n+1 numbers in a list except for 1 num all had duplicates, how to
find out that num in O(n)

3. In 1000 wine bottles stack 10 are poisoned given 10 rats what is
the minimum number of tries to find the poisoned one. Rat dies once it
licks the poisoned wine.

4. Write 1,3,6,4 using +,-,*,/ to get 24 (no repeat of numbers)

5. Which is the DS used in dictionary mode in mobile (t9)

6. Which is DS used for chess program...to predict move each and every
time..

7. There are $1070 dollars how to split them into bags such that asked
for any denomination from $1 to $1070 , u must b able to give without
opening bag...

8. Algorithm to partition set of numbers into two s.t. diff bw their
sum is min and they hav equal num of elements

9. Prog: given Numerator & Denominator.... print 0.3333333333 as .(3)
0.123123 as .(123)

Title: Re: Yahoo Questions
Post by towr on Jun 3^rd, 2007, 2:09pm

1) [hide]50-50, if the natural ratio is 50-50[/hide]
2) [hide]xor them all[/hide]
3) [hide]probably something with binary encoding[/hide] (it was asked before for 1 poisoned bottle; havign 10 changes things a little)
4) [hide]6/(1-3/4)[/hide]
5) DS??
6) ??
7) [hide]Single coin bags would work. You could use binary up to a point to make it more efficient.[/hide]
8) [hide]sounds like a dynamic programming problem[/hide]
9) [hide]to find the period k, I think you can find the least k>0 for which the D/gcd(N,D) divides 10[sub]k[/sup]-1. [/hide]

Title: Re: Yahoo Questions
Post by R0B1N on Jun 3^rd, 2007, 10:45pm

on 06/03/07 at 14:09:18, towr wrote:

5) DS??
6) ??

DS -> Data Structure

on 06/03/07 at 14:09:18, towr wrote:

7) [hide]Single coin bags would work. You could use binary up to a point to make it more efficient.[/hide]

I guess the question is to do it with minimum number of Bags

Title: Re: Yahoo Questions
Post by towr on Jun 4^th, 2007, 12:01am

on 06/03/07 at 22:45:27, R0B1N wrote:

DS -> Data Structure

Ah, thanks.
So for 5 [hide]a tree[/hide]
And for 6, I don't see how the question makes sense. because it doesn't depend on a datastructure. It depends on an algorithm [hide]minimax with heuristics thrown in for pruning[/hide]. Hashtables may come in handy though.

Title: Re: Yahoo Questions
Post by Grimbal on Jun 4^th, 2007, 2:31am

For #3, [hide] I am not sure it is meant like that, but you have as many rats as there are poisoned bottles. You need at least one rat to identify a poisoned bottle. If you ever give a mixture of wines to a rat and it dies, you haven't identified a poisoned bottle and you are short of one rat. So you can test only one wine at a time one each rat. In the worst case, 9 rats identify 9 bottles and the last rat doesn't find the poison before the 999th bottle. So 999 testings can be necessary. And it is enough because if one bottle remains and the rat isn't dead, the last bottle is poisoned.

Depending on what you call the minimum, the minimum number of tests to possibly identify all bottles is 10. The minimum of tests to guarantee to find all bottles is 999.
[/hide]

Title: Re: Yahoo Questions
Post by arunrambo2000 on Jun 4^th, 2007, 11:34am

[hideb]1. I think 50 -50 wont come... considering the probability of a boy child is 0.5 & also that of a gal child is 0.5
but if a gal is born then they try again for a boy.. now also both have equal probability.. So they both wont be equal
I can figure out just this ,, not more than that.. plz help me out

3. I think this is dependent upon the last poisoned bottle say k.. so for this case minimum no of tries is k.. in the worst case it leads to 999 as Grimbal proposed
but if the no of rats is greater than the n of poisoned bottles we can try out in a less no of trails as Grimbal proposed... ( I think this is similar to the egg breaking problem .... )

5. For T9 it can be done using trie data structure (prefix tree)[/hideb]

Title: Re: Yahoo Questions
Post by towr on Jun 4^th, 2007, 12:01pm

on 06/04/07 at 11:34:02, arunrambo2000 wrote:

[hide]1. I think 50 -50 wont come... considering the probability of a boy child is 0.5 & also that of a gal child is 0.5
but if a gal is born then they try again for a boy.. now also both have equal probability.. So they both wont be equal
I can figure out just this ,, not more than that.. plz help me out[/hide]

You can consider it like this. Consider the first-born children, you will find 50-50 boy-girl
For the second-born children, you'll also find 50-50 boy-girl
the third-born children, again, 50-50 boy-girl
etc.
Hence, 50-50.

The proportions of boys and girls remain at their natural levels (they needn't even be 50-50)

Title: Re: Yahoo Questions
Post by SMQ on Jun 4^th, 2007, 12:18pm

on 06/04/07 at 11:34:02, arunrambo2000 wrote:

[hide]1. I think 50 -50 wont come... [/hide]

[hide]Sure it will -- consider the odds for a family:
50% chance 0 girls, 1 boy
25% chance 1 girl, 1 boy
12.5% chance 2 girls, 1 boy
6.25% chance 3 girls, 1 boy
etc.

Expected number of boys: 50% * 1 + 25% * 1 + 12.5% * 1 + 6.25% * 1 + ... = 1
Expected number of girls: 50% * 0 + 25% * 1 + 12.5% * 2 + 6.25% * 3 + ... = 1

So on average each family will have one boy and one girl.[/hide]

--SMQ

Title: Re: Yahoo Questions
Post by kapiwu on Jun 5^th, 2007, 12:40am

Hi Towr,
Could u explain me the solution of 9th problem.

Title: Re: Yahoo Questions
Post by towr on Jun 5^th, 2007, 1:23am

on 06/05/07 at 00:40:20, kapiwu wrote:

Hi Towr,
Could u explain me the solution of 9th problem.

Well, it's only a partial solution. But if you have a repeating part, you can get that by taking it as a number, and dividing it by a string of equally many 9's.
So 0.(1) = 1/9, 0.(12)=12/99=4/33, 0.(436543897)=436543897/999999999
You'd have to be carefull if the repeating part doesn't start immediately after the dot though. But you can shift the dot to the right place first.
0.1(6)= 1/10 1.(6) = 1/10 (1 + 6/9)

For very large repeating parts this may not be the best way, due to limits of integers in the computer. (And even otherwise there may be better ways.) But it should work.

Title: Re: Yahoo Questions
Post by Grimbal on Jun 5^th, 2007, 3:35am

For #5, I think nobody types so fast that performance is an issue. The main criterion would be size. A list of words sorted by length and T9-code would be easy enough to search. Each word must have a score attached to sort them from most used to less used.

Title: Re: Yahoo Questions
Post by Bishamon on Jun 19^th, 2007, 2:03pm

7). [hideb] The number of bags is 10. The bags should contain the following denominations. $1, $2, $4, $8, ...
[/hideb]

Please correct me if I am wrong.

Title: Re: Yahoo Questions
Post by KC on Jun 20^th, 2007, 1:02am

on 06/19/07 at 14:03:09, Bishamon wrote:

7). [hideb] The number of bags is 10. The bags should contain the following denominations. $1, $2, $4, $8, ...
[/hideb]

Please correct me if I am wrong.

Those sum up only to 1023. What happens if we need coins between 1023 and 1070.

Title: Re: Yahoo Questions
Post by Grimbal on Jun 20^th, 2007, 2:14am

#6 [hide] 6/(1-3/4)[/hide]

Title: Re: Yahoo Questions
Post by Bishamon on Jun 20^th, 2007, 6:52am

7). Modification of above.
[hide]the number of bags are 11. I apologise. I was thinking in terms of exponents of 2. 1, 2^1...2^ 10[/hide]

Title: Re: Yahoo Questions
Post by jaini_rohit on Aug 30^th, 2007, 9:30am

please show me the answer

Title: Re: Yahoo Questions
Post by towr on Aug 30^th, 2007, 9:59am

on 08/30/07 at 09:30:24, jaini_rohit wrote:

please show me the answer

If you select the orange fields in the posts above, there's answers there.
Not necessarily all correct, but generally close enough.

Title: Re: Yahoo Questions
Post by sk on Sep 1^st, 2007, 6:46pm

For 8
sort the numbers
calculate the sum
then this problem reduces to finding denominations given a sum. So find the subset which is equal to or closest to (sum/2) and mark them. this is one set, the numbers remaining are in the other set.
this can be called greedy..sort of..

Title: Re: Yahoo Questions
Post by baba on Sep 5^th, 2007, 3:05am

link for prob similar to #9

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1186062393