Difficult Puzzle || 25 Horses Race || Asked in Google and Microsoft Interviews
Вставка
- Опубліковано 20 тра 2017
- This is one of the difficult puzzles asked in interviews of companies such as Google and Microsoft.
You have 25 horses and you want to pick the fastest 3 horses out of them. So you decide to conduct a race.
But you have only 5 tracks. So in one race, only 5 horses can run at the same time.
An important thing to note is, you don't have any stop watch/timer with you.
PUZZLE:
What is the minimum number of races required to conduct, in order to find the fastest 3 horses?
The video has complete explanation of the answer.
Please comment below your answers and suggestions. Also LIKE the video and SUBSCRIBE to my channel if you are new.
Please give a try to these Interview Puzzles and Riddles:
5 Interview PUZZLES || Episode #2 || Frequently asked Job Interview PUZZLES
• 5 Interview PUZZLES ||...
10 Interview RIDDLES || Episode #1 || Frequently asked Job Interview RIDDLES
• 10 Interview RIDDLES |...
For those of you who are unsatisfied with the answer, claiming stuff like "A4 can be faster than B1", you are misunderstanding what Ammar means when he says "eliminate". It doesn't mean that the eliminated horse is slower than those who aren't, in fact, the eliminated A4 can be faster than B1 which wasn't eliminated. But it does mean that it is not in the top 3. So even if A4 is faster than B1, it's still slower than A1, A2 and A3, which would be the top 3 in that scenario. It is possible that A4 is faster than B1, but there is no scenario in which A4 is in top 3, hence we eliminate it. I suggest you rewatch the video with this in mind.
However,
A horse beating another horse in a race is in no way a guarantee for that horse beating other horses or even hat same hose a second time.
So if horse a wins a race against horse b. And horse c beats horse b. Horse a could still beat horse c.
@@john_mckinney True. And I mean simply because A won against B once, doesn't mean that A would always win against B. If they race again, B could win this time. This really is just a logic puzzle that doesn't apply in the real world.
KineticManiac
But let’ssay A1 won the first race n 1 minute ad A4 and A5 came in 5th in 1:10
A4 and A5 are eliminated
In the later race A1 races against B1-E1. A1 finishes first in 1:30 B1 second in 1:31. B1 does not get eliminated even though it is considerably slower than A4 and A5
@@john_mckinney As I said we don't eliminate horses because they're slow, we eliminate them because it's confirmed they're not in top 3.
For the solution shown here to work, we need to assume the following:
1) If X is faster than Y, X will always win against Y.
2) If X is faster than Y, and Y is faster than Z, then X is faster than Z.
The example you gave is actually a bit problematic, because you said that A1 has completed the race in 1:30 against B1, but A4 and A5 completed the race in 1:10 against A1 (which had completed that race in 1:00). Now, does this mean that A4 and A5 could potentially win against A1 if they race again? 1:10 is faster than 1:30 after all.
A better way to think about this is to simply assume that each horse finishes the race in the exact same time. For example, A1 always finishes in 1:00, A5 always finishes in 1:10 and B1 always finishes in 1:30. Now in the first race A5 would be eliminated. In the second race B1 would not be eliminated. At first it seems as if we have a problem, because we eliminated a horse that finishes in 1:10, yet let a horse that finishes in 1:30 continue. This, seemingly a problem, gets solved when you think about how quickly A2 and A3 would finish the race. Surely they are slower than A1 (longer than 1:00), and faster than A5 (shorter than 1:10). So let's assume A2 finishes in 1:05 and A3 finishes in 1:06. So once B1 races against A2 and A3, it's going to lose, and get eliminated. So if B1 is slower than A5, it will eventually get eliminated, just that it will happen after A5.
This seems to be what's confusing most people, the objective of the question is to find the fastest 3 horses. It doesn't claim that you have to eliminate the slower ones first, you can eliminate them in any order you like, so long as you can guarantee that you can find the top 3. So here, we eliminate them once we're sure they're not in the top 3.
KineticManiac my example is not problematic, since te horse A1 could have run his fastest race the first time, eliminating A4 and A5, who were (in that race) faster then B1 and C1 in the second race.
I don’t always love these videos (as I’ve moaned about in other comment pages, because it’s often about some kinda gotcha mechanic), but I really like this one. A very logical answer, well explained, and well visualised. Thumbs up!
I just watched this SAME EXACT problem in a different video, but your visual explanation of eliminating horses is FAR SUPERIOR!!! And seven races is the optimal solution that will work for every scenario possible.
HOWEVER. There are two scenarios where six races could work. They are not statistically significant but they do work.
Race the first five horses, pass the winner on to the second race with four new horses. Pass that winner on to the third race, adding four new horses. Pass that winner on to the fourth race, adding four new horses. Pass that winner on to the fifth race, adding four more horses. For the sixth race, take that winner, and add the four remaining horses.
Scenario A: The horse passed on from the fifth race only places 4th or 5th. This means that the 3 fastest horses out of 25 were in the last four remaining horses.
Scenario B: The horse passed on from the fifth race placed 3rd. This means that the 2 fastest horses out of 25 were in the last four.
In either scenario, the 3 fastest horses were identified in only six races.
IF the horse passed on from the fifth race places 1st or 2nd in the sixth race, then you are stuck with having at least two runoff races to test horses eliminated from earlier races.
@@DougRayPhillips I didn't reconstruct anyone's meaning, thank you very much. I arrived at the optimum solution myself, AND I went a step further to point out additional possibilities. Thinking outside the box and going a little further than the rest of the crowd actually landed me the BEST jobs, I retired at 52 with a full pension and a seven-figure 401K. Don't lecture people when you know nothing about them.
While it is nice to potentially solve in six races, I think where this falls down is if the horse passed down wins the 6th race. There would be a total of 12 horses still in contention for 2nd and 3rd (to adequately test for if 2nd and 3rd came from the same preceeding race). That would require 3-4 more races to tease out (the third race would test the final two of the 12 remaining horses, against the 2 leaders of the first, and the leader of the second. If the leader of the second wins then a fourth race between the leader of the first and the second of the second).
Absolutely amazing!Thanks a lot!
Excellently coined. Enjoyed!
I really love watching your videos!
nicely explained ammar! love ur videos.
Absolutely amazing
Thank you for explaining amazingly :)
Today It was asked in SAP interview
great question
Thanks Santosh.
Excellent! Thanks.
I think it is enough to make 6 races. All the first-ranked horses in every group must have a sixth race and we just choose the first three fastest horses.
But you need the top 3, not just the top 1.
AWESOME ONE!!!
Condition: stamina of horses remains constant in all the races.
You are making things up. They didn't say anything about how much time between races. Could be a week between races. That's like saying... Condition: The horses are well fed and remains constant in all races
Awesome job, keep it up.. 👍💪
Thank you so much!!!!!!!!!
great!!
Great Explanation
loved this video
Great puzzle! I wonder how this can be extended to any number of horses or any number of top horses and if there's a formula for the solution.
Very good explanation
Thanks Manuel :)
Nice one
Great puzzles... Thanks u!
Very nice
Nice puzzle...
There is a possibility that b3 is also faster than c1. So we cannot eliminate b3
Since b2 is for sure faster than b3, even if b3 was faster than c1, b3 would still not take 3rd because b2 is faster.
At first, I had the same doubt but later, I realized. On 3:40, we know that B3 is slower than at least 3 horses; A1, B1 and B2. Since only top 3 matters to us , we can eliminate it.
It doesn't matter. If B3 is faster than C1, than A1, B1, and B2 are all already faster than C1. B3 is never going to be in the top three, so it's never worth considering.
Even any fourth cant be eliminated.
@@FirojAnsari-xo4hh how so?
Finally an easy one
It is not decided that A4 and A5 are slower than B1 or C1 or D1 and similar for other groups. How can you remove 4 and 5 rows at first step
Because if you want top 3 horses only hypothetically it can only be 3 from a. a1 a2 a3 can be fastest 3 theres no way a4 or a5 can be included in the top 3
@@kevinnijjar5238 i think you do not understand my comment. Obviously a4 and a5 are slower than a1,a2,a3. But that may not be same when compare with b1 or c1 or d1 etc...
Now here it was the matter of luck that houses of group B nd C got more chances to preforme but at the last we had to find the fastest 3.... so chill we ar giving nothing to houses who came 4th-5 th..... sooo don't worry their is no discrimination
@@kevinnijjar5238 yup ur right
@@smslca but it doesn't matter because if they are slower than a1,a2,a3 then obviously there are more than 2 faster horces than a4 and a5 and it also goes with b4,b5 c4,c5 d4,d5 e4,e5 . Because there are 3 horses faster than them means they cannot be in any condition among top3.
Nice..
6 is the minimum assuming the rules include that you can't slaughter 22 horses before the 1st race. Then it would be less. (This is a hypothetical scenario after all)
Cool
And how do you prove that your initial approach with racing separate groups of 5 is optimal? Maybe there's a different approach that mixes in old horses to get a result in only 6 races?
example:
you race 5 horses, suppose the 3 fastest horses are among them...
then if you take the 3rd fastest horse and race it with 4 other horses, that 3rd horse will be 1st in the 2nd race and every other race ... that would mean that you have used only 6 races overall if you're 'lucky' in your initial pick of horses.
So can you prove that 7 is the actual minimum and there isn't a better 'mixing' strategy that sometimes gives 6 races, and sometimes 7, but on average requries less than 7 races?
Can it not be done like conduct 5 race. Select 1st of each grp. Now conduct race between 1st of each group. Thus we will get top 3. So total number of race will be 5+1=6
Nice
Damn, I guessed 11, but this makes sense.
Semma
perfect
Excellent explanation.
But will it correct if we just conduct 6 races.6th race of the horses of 1st rank in previous 5 races. The top three horses were the horses of 1st ,2nd and 3rd rank.
but may be a2 is faster than b1
your way of explaining is very nice 👍 keep doing
Thanks Kanimozhi :)
@@LOGICALLYYOURS conduct 5 races to 5 groups and identify the first position of all 5 races..from the 5 horses( which got first position in five groups) conduct additional 6th race to identify first three positions
Amer I have a doubt please clarify. What if in final race C1 becomes first and B1 become second? In before race B1 overtook C1 and in final race C1 over took the B1. Then how can you decide the fastest among them.
The premise is that all horses will always complete a race in the exact same time. So if B1 finishes one race ahead of C1, he will finish all races ahead of C1. There is no scenario in which C1 will finish ahead of B1
Speed of horses in each race is same...
@@musicmantra3606 yes that's the assumption we must keep. Thanks
I got it
That was so easy
I've been asked this question in Oracle Second round in 2017. But i screwed it up :(
I think sorting would be better? Just race first five horses, race the top three with next two. Choose the top three in that, race them with next two and so on. The answer will come to 11 I guess if my calculations aren't wrong. Lemme know if they are.
Me solve this question in only one time in my classroom
Chapter -PNC
Can you please provide me the link for all video...
only six required first 5 of five group race after that all group's winning five , first 3 in second race are the winner
What if A2 is faster than B1 ??
@kiran kumar, No, because that only works if the three fastest horses were all in different groups during the first five races. There's a 45.6% chance that that is not the case.
@@LOGICALLYYOURS what if all the horses of any group are running slower than the rank 5 horse of any other group?
Then how and why did you eliminate several horses assuming incorrectly??
@@rochishmopidevi7617 The whole set running slower will be eliminated by the race of 5 winning horses. In fact, both sets that don't place at least 3rd there are holding only horses not faster than the top 3 sets.
@@LOGICALLYYOURS Same want to ask you what if A4 and A5 where faster than B1 , B2 and C1?
In real life, horses don’t get there fastest time every time they run
Real life and logic puzzles don't always intersect on a Venn diagram
If you answer like this.....
Interviewer : get out from here.
You : pls sir give me one more chance.
Interviewer : in real life you can't get 2nd chance immediately...
😂😂😂😂
@@dwezz100 w
This is what people say when they don't get correct answer
Agree with you ❤️
Um, this is a great solution but the question was to find a minimal number of races required to find the top 3 so you'd need to provide an argument why 6 isn't enough because it's not obvious at all. Perhaps some kind of entropy argument would work?
what if horses receive a handicap for winning their previous races?
Can use similar algorithm for finding median ish number
What if B5 is raced in gorup A and got any of the top three position?
Hey I have solved it
I got the answer correct
Same question I got in interview. And I solved it easily. Thank you amar
Can u plz explain clearly?
which company?
Excellent solution. Thanks
Today it was asked to me in persistent system higher package
Thats not optimal solution. Total number races needed is 6. If there are 24 horses, total number of races needed will be 5. Race 5 horses and compare 3rd one to new group of 4. Every time horse come before your 3rd horse from starting group, take second horse and mark one that come first. Repeat process until you tested all. Now compare winers and one that are left with remaining 2 races and you het 6 races. So for 5 horses you need one race, for 6-9 you need 2, for 10-14 you need 3, for 15-19 you need 4, 20-24 you need 5 and for 25-29 you need 6.
That strategy doesn't work 100% of the time though.
I got the same result
6 races are the optimum solution
It can be possible that top two horses are of same speed hence we have to choose four horses
6 Races here's how
Race 5 races of 5 and record the winners and map how many furlongs behind the 2nd and 3rd place horse was
Run the 5 winners and map the 2nd and 3rd place horse positions behind in furlongs
Then is just a mater of seeing if any horse would be ahead of the horses in the 6 th race
Poor B1 and C1. Because they participated in three rounds of race. Other toppers like A1, A2, A3 and B2 only participated in 2 rounds. I think Stamina also plays a part in speed of horses. What is your opinion?
Real life and logic puzzles don't always intersect on a Venn diagram
I answered 6, missed the thought
Think like me noob
6 can also do
5horses in 5 races- we got top 5 speedy horses
Then those 5 horses in 1 race.
Top 3 are best.
Only 6 races are needed..
@@testingfr7991 That's incorrect. What if the 2 fastest horses are in 1 group? In race 1 you've determined the fastest horse from each group but it does nothing for the relationship between any of the groups. If your fastest 3 horses A1 > A2 > B1 your solution would incorrectly place C1 as one of the 3 fastest despite being slower than A1, A2 and B1
No stop watch or timer but length of horse mesures how far each winner is. This is additional info that can eliminate more horses and reduce the results.
To understand this tricky part properly consider a simple question- u got three horses A,B,C and u need to mark the fastest horse( which scores 1st rank) condition is you can race upto 2 horses at a time.
1st race would between A,B/ B,C/ A,C (these three probabilities exist here)
(1) suppose 1st race is between A n B and A wins(scores 1st rank), this means B has scored 2nd rank .so 2nd race must be conducted between A n C not between BnC to get the fastest from these three ..why?! Let me xplain;
Suppose
(i) 2nd race is between B and C and B scores 1st rank in this race . So u can draw following conclusion that A is faster than B n B is Faster than C so A is the winner ...but
(ii) if C wins in 2nd race then you have to conduct a 3rd race between AnC and here you will find the fastest one in 3rd race. But you don't need this 3rd race.u can pick the 1st ranker in 2nd race , let me xplain how.!!
Suppose
u directly conduct 2nd race between AnC and
(i)if A wins then A is ultimately 1st ranker ,since A is winner in 1st race n A is winner in second race so A is faster than B and C
(ii) if C wins then C is ultimately 1st from remaining two bcoz C is faster than A n A is faster than B(already proved in 1at race) so C is aslo faster than B . Simple maths logic
(C>A n A>B → C>A ... 8>5 n 5>3→ 8>3 ..simpl no!!)
So you need only 2 races to decided who is fastet. Typing and den explaining is hard, doing it practically makes it easy to understand.
Simple no.. try it with your friends in front of u to understand better.
If you understand this probability and relation concept you will easily get my question into your solved question & answers list.
That question in the video is similar to this but quite hard bcoz u got many horses and u get stuck between probability and relation issue , even I got stucked until I tried this with 3 horses.
How do you know B4 isn't faster than C1?
Hey Tommy... as we know B4 cannot survive the competition so we simply eliminate it. But C1 has a chance to claim the 3rd position of overall competition. Also, we don't need to compare each horse with all other horses, rather we should keep on eliminating the horses which can't survive the competition.
I hope that helps !
Thanks for the reply Logically, I actually opened up excel and put horse times on just to see where I was going wrong. I cant believe I didn't see this...Thank you for your response.
you're welcome 😊
I still don't get it. Maybe A4 and A5 were faster than all the horses from groups B, C, D and E.
The solution given in the video only allow us to have an ESTIMATION.
Reality might be different !!
You will tell me: "As we know A4 and A5 cannot survive the competition so we simply eliminate them"
However the ASKED question is: Find the 3 FASTEST horses without a chronometer.
I might be finicky or trouble maker, but words have a meaning. For me, fastest means fastest.
The only ACCURATE solution is to put in competition every horses 2 by 2. and find out which horse has never been defeated, which horse has been defeated only once and which horse as been defeated only twice.
@Greg, "Maybe A4 and A5 were faster than all the horses from groups B, C, D and E."
Indeed, A4 and A5 may be faster than B1, C1, D1 and E1. However, if that's the case, then B1 and C1 will simply not finish in 1st or 2nd place in the seventh race; instead, A2 and A3 will win that race and prove to be the #2 and #3 fastest horse overall.
There's no estimation, the method in the video is accurate. But there's simply no necessity to include A4 and A5 in race 7, because they wouldn't finish in 1st or 2nd place anyway.
I can do it in by conducting 6 rounds
*I almost passed the test but I failed to reject last two horses and hence my answer came 8 which was wrong obviously.*
That's a nice mind your decisions video you have there
Hi Archana... or is it the other way around :) a comparison of date published would be useful :)
How do you know that D1 and E1 are slower without racing them with all first finishing horses.
Thats whats race 6 is for. D1 and E1 are the fourth and fifth horses of the sixth race among winners of races 1-5, and thus eliminated
sigh. I was on the right path with my anwser, but I calculated a total of 9 races.
Step 1: race all 25 horses in groups of 5. total: 5 races
Step 2: race all the horses that came in first, all the horses that came in second, and all the horses that came in third together. total: 8 races
Step 3: race the top 3 horses from the first place race, along with the winners of the 2nd place and 3rd place races, together. The first three horses to cross the finish line are the three fastest horses.
7 races
I think it would have been more accurate to state that the horses run at the same speed for each race, otherwise nice puzzle, thanks
Obviously will run at same speed ... Those are horses not moody
But I agree with William
First attempt I got 8 but then tried again ans got 7
So happy to see my comment of before 1 year.
This time video came in my recommendations, just one day after the interview at DE shaw. I was asked this same puzzle in the interview and I was able to ans correctly. 😇.
My guess was 6
What is all the horses in race 5 are faster than rest 20 horses.
When race 6 ends and its horse wins, the horses of race 5 represent A1, A2, A3
@@rubalsher well it doesnt after 6th race ends we'll simply make race between A1, B1, C1,D1,E1 and E1 will win. Boom E1 is fastest and you can do rest steps as shown in vid
You can in theory determine all the horses rankings in 7 races.
What if the result of 6th race is in different order?
Even if you change the order, you'll need to re-arrange the columns, which is just equivalent to the solution shown. It was only for the sake of simplicity by ensuring all combinations are taken care.
One race is needed. Sell 22 horses... Then have a race with the three remaining horses to find which horses are the fastest. Bonus you can have enough money to buy a timing system for your racetrack.
Hello sir is there any book which I solve puzzles
As much as treating this as a math problem, an actual horse like a human being can produce different race times and different times of races, not to mention that as you race the horses, they get tired.
Hi Tan, I truly agree with what you just said.... but a Puzzle always aims to identify the tricky things hidden in it. Since the puzzle doesn't mention the tiredness, you can simply ignore it :)
I was told this years ago but it was 'mechanical horses that always run at the same speed'...which gets rid of the issues of real life horses. It was fun to work it out again :)
Would the following formulation make you feel more comfortable? Let S be totally ordered set of 25 elements. If by choosing any 5 element subset of S you could determine the order of its elements (inherited from S), what is the minimal amount of 5 element subsets you have to choose before you can determine the largest 3 elements of S?
I agree with Mr. Tan. The assumptions (horses run the same speed each race, track conditions do not affect horses performance, etc.) must be stated at the intro (when the no stopwatches condition was listed) otherwise, the answer doesn't create a logical solution.
I made 5 horses run in 1 track at the same time and found the three fastest horses in 1 race! I am currently working for google.
Give them fair opportunities not dominating culture they have also come up with innovation
Does anyone have a nice proof that six races are not enough? Five races definitely don't work, but with six races, I almost immediately run into several case distinctions which I am not really willing to go through one by one...
A1 has currently won 2 races, the A group race and race 6. Since A1 won race 6, the 2nd and 3rd of the A group race has a chance to compete with the 2nd and 3rd of the 6th race (for cross-checking I think...) to determine which belong to the top 3. For B2 being able to compete in the 7th race, the horse is just there because it is within the range of a top 3 (3rd). idk if this is a plausable answer but i took the shot anyway.
Not all races feature horses that are equally fresh (raced same number of times previously) would this not alter the result due to potentially faster horses beng more tired than their competitors?
There is a limit to no of races. It should be minimum. But no cap over the time. So take as much time as needed to make them all fresh.
I just watched a video on this yesterday - same exact problem, the uploader stipulated mechanical horses, so fatigue not a factor.
I can find it within 6 races
Tell us how.
The vid would be much more clear if you didn't label the groups as A thru E before you raced the five winners against each other. Call the groups something else at first, and only rename them A thru E after race 6.
One, two, three, four, “fai”! Why “fai”?! 🤔
For fastest horse I am getting 4
How?
If this were in fact a problem posed for an interview with Google or Microsoft, I would simply answer "Shoot one of the horses. The other 24 will no run much much much faster."
I was asked this question in an interview. I answered like this, you make 5 horses run from one end of track and another 5 from other end of track. So in one race we can compare 10 horses. You Stand in middle of track so first 5 horses who reach at middle of track are the ones who win. We will get 5 from 1st race, 5 from 2nd race and in 2 races we would have covered 20 horses. We now we can again compare these 10 horses so we will get top most 5 from initial 20. Now last 4th race.
And you get top 3
With that method you can even get the top 3 from 31 horses in just 4 runs by taking the top 3 from 10 3 time, then let those 9 and the last one race again and take the top 3.
But this doesn't actually make any sense because you can't let horses run against each other in the same lane. They will just run into each other and get injured. If there were space you could just let them run together in the same direction.
@@1vader Yup 4 is good enough. Hypothetical questions.. hypothetical solutions...
You did not follow the instructions. It clearly states you can at most race 5 horses per race. I would have sent you home if I was the interviewer.
I'm particularly not convinced when you eliminate B3..... especially the last race includes C1....how do we know among C1 and B3 who is faster?....It can also be B1 < B2 < B3 < C1 (C1 can be slower than B3)
Kindly respond for my question
@@karthiks5722 B3 cannot be among the three fastest horses because A1 B1and B2 are faster.
@@rwb966 Thanks
A2
This was asked in SAP labs
I guess we can find fastest 3 horses in 6 races. If im not wrong.
We can put horses into 5 groups with 5 horses in each group. Then we'll conduct races for each group. In each race we shall select no.1 fastest horse. Then we will be remained with top 5 fastest running horses. If race is conducted among them. We can find fastest 3 horses.
Bruh watch the video again. There could be a chance that the horse who came 2nd from group 1 could be faster than horse who came 1st from the group 4.
finally someone explains the elimination process clearly. Still, this is an awful lot of assumption the horses on the first heat are not all faster than any horses in the other heat.
The elimination method accounts for every possibility, there were no assumptions made. Horses are only eliminated from the pool of contenders if there is no possible way for them to be one of the three fastest.
That is not an assumption being made. The methodology works for all groupings, no assumptions necessary.
I feel this puzzle is very much wrongly analazed...here u have considered A group as the fastest horses how and why?
In real life we have this variable called time
A tricky riddle