Yahoo Interview Question
Web:
www.yahoo.com
|
HQ:
Sunnyvale, CA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
211 Interview Reviews |
Back to all Yahoo Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Software Engineer at Yahoo:
Oct 18, 2011
There are 49 horses of which you need to find the 25th fastest horse.At a time you can race 7 horses.How many number of races are required to find the 25th fastest horse? After each race,we know which is first and which is second but dont know the speed.That makes more sense) Hint - Consider the significance of 25 (24 horses r faster than this horse and 24 are slower)
Add Tags
[?]
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (3)
Nov 22, 2011
The logic is wrong. the third could be 3 - 15; the fourth could be 4 - 22, and so on
Helpful Answer?
Yes |
No
Inappropriate?
Jan 16, 2012
The answer to this question is run the quick sort kind of algorithm. Take some random horse. divide the 49 horses in two stacks. One which runs faster and other which runs slower. how to do this ? since we cannot run all of 1/2*49 together so run 7 at a time and put the faster on end and slower at the start of list. keep doing this until start < end. Now this divides the set into S, B. There are two cases S > 25 then run the same logic over S, else run the logic over B to find 25 - |S| fastest horse. If the horse picked at random is at either 25th position in first case, that horse is 25th faster. In second case if the random horse picked is at 25 - |S| position, the horse is the answer.
Helpful Answer?
Yes |
No
Inappropriate?
To comment on this
question,
Sign In with Facebook or
Sign Up
You might also be interested in: Interview Questions, Software Engineer Interview Questions, Yahoo Interview
0 of 2 people found this helpful
by Jatin Kapoor:
Race them in 7 groups. (7)
Race the first place of each group. (1) Let the group the winner originally came from group 1, and runner up's group 2 and so on.
The winner of the second race is the overall winner.
The second place has to be faster than all the horses in his own group (group 2) and all the horses in group 3 to 7
, since its faster than the fastest horses in those groups.
But group 1 horses (other than overall winner) can either be faster or slower than the second place horse in second race,
so the horse which got second place in second race (it rhymes!) can be ranked from 2 to 8 overall.
Using this logic, the the 5th place in the second race can be ranked from 23 to 29 overall.
Group 5 second place can be 24 to 30, third 25 to 31, so these are all possible 25th places overall.
In group 4, applying the same logic, the last 4 horses are all possible 25th place overalls also.
So there are total of 7 possible 25th rankers, race them again (1).
Total is 9.