Difficult Puzzle || 25 Horses Race || Asked in Google and Microsoft Interviews

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
10 Interview RIDDLES || Episode #1 || Frequently asked Job Interview RIDDLES

[KineticManiac]

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.

[nobodyknows]

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.

[eddeh]

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!

[HARSHITKUMAR-wjex]

nicely explained ammar! love ur videos.

[ahnge]

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.

[pranavshete]

Condition: stamina of horses remains constant in all the races.

[john_mckinney]

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.

[martossssss]

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?

[TheAnirudh]

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.

[jennyjumpjump]

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)

[biasbias]

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.

[syamsundarpillalamarri]

There is a possibility that b3 is also faster than c1. So we cannot eliminate b3

[smslca]

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

[tommyv]

How do you know B4 isn't faster than C1?

[kirankumar-smzp]

only six required first 5 of five group race after that all group's winning five, first 3 in second race are the winner

[bsgauge]

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.

[hugh.g.rection]

what if horses receive a handicap for winning their previous races?

[shailabhprasad]

What if B5 is raced in gorup A and got any of the top three position?

[joshuatan]

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.

[KingXKok]

Can use similar algorithm for finding median ish number