Tencent on the other hand, I was puzzled by the "horse race" problem

Classic interview questions that are difficult to answer right at one time , Everywhere is the pit

Hello everyone , I'm fish skin .

Today, I'd like to share an interview question that I have been baffled by , It is also an interview question often asked in the interview of a large factory , The question of horse racing .

The problem is not difficult , But the first time I was asked , A bit careless , You get the wrong answer . therefore , Let's study together ！

problem

Yes 64 horse Race , There is no timing tool like a stopwatch , Only... Are allowed on the runway at a time 8 horse Simultaneous ratio , ask least It takes several races to choose the fastest one front 4 name ？

There are so many descriptions , You can think about it first , Then give the answer in the vote ~

（ vote ）

Here are the solutions and answers .

Their thinking

This topic is full of pitfalls , Any number change in the title will affect the final result , So be sure to clarify the key figures on the topic .

There are also many variations on the Internet , such as 36 horse 6 Look for the top three on each runway , But the ideas are the same , Let's simulate the whole course of the competition .

The first round

First , A maximum of... Is allowed on the runway 8 Horses compete at the same time , Then we must make the best use of resources , Every game should be full 8 horse .

So the first round is the easiest , No brain take 64 Horses are divided into 8 Group , Each group 8 A horse race Just fine , total 8 game .

Group number	Contestant
Group 1
Group 2
Group 3
Group 4
Group 5
Group 6
Group 7
Group 8

After this round , Because the title requires that before the election 4 name , therefore , The first of each group 4 The horse after the first place can be eliminated directly , And then there were 32 horse .

Group number	Contestant （ = The champion in the group ）
Group 1
Group 2
Group 3
Group 4
Group 5
Group 6
Group 7
Group 8

The second round

The second round begins , We must budget carefully .

The simplest way is to take the rest 32 Horses are divided directly into 4 Group to play , But in fact, using the information from the last round , We can have a better way .

Let the last round of competition , Each group 1 We will compete together 1 site , Then according to the results of this round of competition , Before election 4 Group .

The field ：

The result of the game ：

Group number	Contestant （ = The champion in the group ）
Group 1
Group 2
Group 3
Group 4
Group 5

The reason for this is ： If the first place in a group can't get ahead 4, Then the rest of the group, Ma Keng, will not be able to get ahead 4, The whole group can be eliminated directly .

Up to now , There is still left 16 horse , Is this round of elimination over here ？

Not really , Take the group of the fourth ranked horse in this round as an example , The highest champion in this group is only the fourth , Then the other horses in this group can also be eliminated . Empathy , More horses can be eliminated , The remaining 10 horse .

Group number	Contestant （ = The champion in the group ）
Group 1
Group 2
Group 3
Group 4

Now there are still 10 horse , It seems that victory is close at hand , But in fact , The next step is the key ！

The third round

Our next goal is to start from 10 Before the horse is chosen 4 name , But a game can only accommodate 8 horse , That seems to be at least two more games .

Step by step , Choose... First 8 A horse race , The question is which one to choose 8 Where's the horse ？

I don't know if you found out , Inadvertently , The champion has been born , That's the horse that hasn't failed both inside and outside the team , The best of the best ！

Group number	Contestant （ = The champion in the group ）
Group 1
Group 2
Group 3
Group 4

therefore , It doesn't have to be compared , The goal becomes , From surplus 9 Choose the second horse from the horses 2 - 4 name .

Let's choose whatever 8 Let's race the horses first , Before election 3 name .

Group number	Contestant （ = The champion in the group ）
Group 1	To play
Group 2	To play
Group 3	To play
Group 4	🦓（ A horse that has not competed ）

So the last round , We also need to keep the horse that was not compared with the previous round with the front 3 Namebee 1 site , What if someone is a dark horse ？

The field ： 🦓

thus , The answer comes out , Minimum need 8 + 1 + 1 + 1 = 11 site .

However , This is a wrong answer ！

Actually , There are better solutions ！

There is still 9 When the horse , If you don't choose 8 A horse race , Instead, remove the group first 2 The winner of the , Leave 8 A horse race .

If this game , Group 3 The champion won the first place , So, since the group has been proved before 2 The champion is better than the group 3 The winner of the , Before 4 The name has been determined , Just compare 10 site . If it's not the first , Then it's still more than one game .

So the correct answer is , Minimum need 10 site , Did you do it right ？

---

Last , Why does this question appear in the programmer interview ？ Smart you must have found out , The above-mentioned horse racing problem is essentially a TopN（ Take the top ） problem , It can be solved by divide and conquer , It is a classical algorithmic thinking . If it is in a distributed system , It shows Parallel computing The advantages of , Available resources （ Such as the 8 A track ） Calculate simultaneously for each group , So as to improve the operation efficiency . Besides , It is also very important to use the existing data results .

Have a good weekend , Don't forget to order the fish skin Fabulous Support me ！️