Author |
Topic: Yahoo Questions (Read 4907 times) |
|
arunrambo2000
Newbie
Posts: 21
|
 |
Yahoo Questions
« on: Jun 3rd, 2007, 1:33pm » |
 Quote  Modify
|
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)
|
| « Last Edit: Jun 3rd, 2007, 1:34pm by arunrambo2000 » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Yahoo Questions
« Reply #1 on: Jun 3rd, 2007, 2:09pm » |
Quote Modify
|
1) 50-50, if the natural ratio is 50-50
2) xor them all
3) probably something with binary encoding (it was asked before for 1 poisoned bottle; havign 10 changes things a little)
4) 6/(1-3/4)
5) DS??
6) ??
7) Single coin bags would work. You could use binary up to a point to make it more efficient.
8) sounds like a dynamic programming problem
9) 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.
|
| « Last Edit: Jun 3rd, 2007, 2:11pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
A
Full Member
Perder todas as esperanças é liberdade!
Gender:
Posts: 236
|
|
Re: Yahoo Questions
« Reply #2 on: Jun 3rd, 2007, 10:45pm » |
Quote Modify
|
on Jun 3rd, 2007, 2:09pm, towr wrote:
DS -> Data Structure
on Jun 3rd, 2007, 2:09pm, towr wrote:
7) Single coin bags would work. You could use binary up to a point to make it more efficient.
|
|
I guess the question is to do it with minimum number of Bags
|
|
IP Logged |
What Doesn't Kill Me Will Only Make Me Stronger
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Yahoo Questions
« Reply #3 on: Jun 4th, 2007, 12:01am » |
Quote Modify
|
on Jun 3rd, 2007, 10:45pm, R0B1N wrote:Ah, thanks.
So for 5 a tree
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 minimax with heuristics thrown in for pruning. Hashtables may come in handy though.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Yahoo Questions
« Reply #4 on: Jun 4th, 2007, 2:31am » |
Quote Modify
|
For #3, 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.
|
|
IP Logged |
|
|
|
arunrambo2000
Newbie
Posts: 21
|
|
Re: Yahoo Questions
« Reply #5 on: Jun 4th, 2007, 11:34am » |
Quote Modify
|
| hidden: | 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) |
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Yahoo Questions
« Reply #6 on: Jun 4th, 2007, 12:01pm » |
Quote Modify
|
on Jun 4th, 2007, 11:34am, arunrambo2000 wrote: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 |
|
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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Yahoo Questions
« Reply #7 on: Jun 4th, 2007, 12:18pm » |
Quote Modify
|
on Jun 4th, 2007, 11:34am, arunrambo2000 wrote:| 1. I think 50 -50 wont come... |
|
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.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
kapiwu
Newbie
Gender:
Posts: 14
|
|
Re: Yahoo Questions
« Reply #8 on: Jun 5th, 2007, 12:40am » |
Quote Modify
|
Hi Towr,
Could u explain me the solution of 9th problem.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Yahoo Questions
« Reply #9 on: Jun 5th, 2007, 1:23am » |
Quote Modify
|
on Jun 5th, 2007, 12:40am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Yahoo Questions
« Reply #10 on: Jun 5th, 2007, 3:35am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Bishamon
Newbie
Gender:
Posts: 8
|
|
Re: Yahoo Questions
« Reply #11 on: Jun 19th, 2007, 2:03pm » |
Quote Modify
|
7). | hidden: | The number of bags is 10. The bags should contain the following denominations. $1, $2, $4, $8, ...
|
Please correct me if I am wrong.
|
|
IP Logged |
|
|
|
KC
Newbie
\m/ what's a metalhead doing solving puzzles?! \m/
Gender:
Posts: 3
|
|
Re: Yahoo Questions
« Reply #12 on: Jun 20th, 2007, 1:02am » |
Quote Modify
|
on Jun 19th, 2007, 2:03pm, Bishamon wrote:7). | hidden: | The number of bags is 10. The bags should contain the following denominations. $1, $2, $4, $8, ...
|
Please correct me if I am wrong. |
|
Those sum up only to 1023. What happens if we need coins between 1023 and 1070.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Yahoo Questions
« Reply #13 on: Jun 20th, 2007, 2:14am » |
Quote Modify
|
#6 6/(1-3/4)
|
|
IP Logged |
|
|
|
Bishamon
Newbie
Gender:
Posts: 8
|
|
Re: Yahoo Questions
« Reply #14 on: Jun 20th, 2007, 6:52am » |
Quote Modify
|
7). Modification of above.
the number of bags are 11. I apologise. I was thinking in terms of exponents of 2. 1, 2^1...2^ 10
|
|
IP Logged |
|
|
|
jaini_rohit
Newbie
Posts: 1
|
|
Re: Yahoo Questions
« Reply #15 on: Aug 30th, 2007, 9:30am » |
Quote Modify
|
please show me the answer
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Yahoo Questions
« Reply #16 on: Aug 30th, 2007, 9:59am » |
Quote Modify
|
on Aug 30th, 2007, 9:30am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
sk
Newbie
Posts: 45
|
|
Re: Yahoo Questions
« Reply #17 on: Sep 1st, 2007, 6:46pm » |
Quote Modify
|
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..
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print