Classic interview questions that are hard to get right in one go are riddled with mistakes

Hello, I’m fishskin.

Today, I would like to share an interview question that I have been stumped by. It is also a big factory interview question that is often asked.

It’s not difficult, but if you’re asked the first time, you’ll get it wrong. So, let’s learn!

The problem

There were 64 horses running, no stopwatches, and only 8 horses were allowed to race at a time. What was the minimum number of races needed to pick the top 4 fastest runners?

That’s it. Think about it for a moment, and then vote in our poll

(vote)

Here are the answers and ideas.

Their thinking

This question has a lot of holes, and any change to a number in the question will affect the final result, so be sure to identify the key numbers in the question.

There are also many variations of the topic on the Internet, such as 36 horses and 6 tracks to find the top three, but the idea is the same, let’s simulate the whole race.

The first round

First of all, the track allows a maximum of eight horses to race at the same time, so we have to make the best use of our resources and run all eight horses at each race.

So the first round is the easiest. Brainless, 64 horses are divided into 8 groups, each group of 8 horses is good for one race, for a total of 8 races.

Set no. The contestants
Group 1 🐴 🐴 🐴 🐴 🐴 🐴 🐴 🐴
In group 2 🐴 🐴 🐴 🐴 🐴 🐴 🐴 🐴
Group 3 🐴 🐴 🐴 🐴 🐴 🐴 🐴 🐴
Set of 4 🐴 🐴 🐴 🐴 🐴 🐴 🐴 🐴
Set of 5 🐴 🐴 🐴 🐴 🐴 🐴 🐴 🐴
Set of 6 🐴 🐴 🐴 🐴 🐴 🐴 🐴 🐴
Group of seven 🐴 🐴 🐴 🐴 🐴 🐴 🐴 🐴
Group of eight 🐴 🐴 🐴 🐴 🐴 🐴 🐴 🐴

At the end of the round, the top four horses were chosen, so the horses that placed fourth in each group were eliminated, leaving 32 horses.

Set no. Contestant (🐎 = Champion of group)
Group 1 🐎 🐴 🐴 🐴
In group 2 🐎 🐴 🐴 🐴
Group 3 🐎 🐴 🐴 🐴
Set of 4 🐎 🐴 🐴 🐴
Set of 5 🐎 🐴 🐴 🐴
Set of 6 🐎 🐴 🐴 🐴
Group of seven 🐎 🐴 🐴 🐴
Group of eight 🐎 🐴 🐴 🐴

​

The second round

Starting in round two, we have to count our pennies.

The easiest way would be to split the remaining 32 horses into four groups, but using the information from the previous run, we can do better.

In the last round, the top four teams will be selected according to the results of this round.

Venue: 🐎 🐎 🐎 🐎 disk 🐎 🐎

Results:

Set no. Contestant (🐎 = Champion of group)
Group 1 🐎 🐴 🐴 🐴
In group 2 🐎 🐴 🐴 🐴
Group 3 🐎 🐴 🐴 🐴
Set of 4 🐎 🐴 🐴 🐴
Set of 5 🐎 🐴 🐴 🐴

The reason for this is that if the first horse in a group doesn’t make the top 4, then the rest of the group doesn’t make the top 4 either.

With 16 horses left so far, is this the end of the round?

No, if the fourth-place horse is in a group, for example, and the winner of that group is as high as fourth, then the other horses in that group can also be eliminated. In the same way, you can eliminate more horses, you have 10 left.

Set no. Contestant (🐎 = Champion of group)
Group 1 🐎 🐴 🐴 🐴
In group 2 🐎 🐴 🐴 🐴
Group 3 🐎 🐴 🐴 🐴
Set of 4 🐎 🐴 🐴 🐴

With 10 horses left in the field, it looks like victory is just around the corner, but in fact, the next step is the key!

In the third round

Our next goal is to pick the top four out of ten horses, but there is only room for eight horses at a race, so it looks like there will be at least two races.

Take it one step at a time. Pick eight horses for a race. The question is which eight?

I don’t know if you have noticed, but by accident, the champion has been born, and that is the horse that has never lost in and out of the group, the best of the best!

Set no. Contestant (🐎 = Champion of group)
Group 1 🏆 🐴 🐴 🐴
In group 2 🐎 🐴 🐴
Group 3 🐎 🐴
Set of 4 🐎

So, he doesn’t have to race anymore, and the goal is to pick two to four out of the remaining nine horses.

Let’s pick any eight horses and race first, and pick the top three.

Set no. Contestant (🐎 = Champion of group)
Group 1 🏆 [🐴 🐴 🐴] enter the battle
In group 2 [🐎 🐴 🐴] Go to war
Group 3 [🐎 🐴] Go to war
Set of 4 🦓 (non-racing horses)

So in the last round, we need to put the horse that didn’t have a better race with the top 3, what if he was a dark horse?

Venue: 🐎 🐴 🐴 🦓

At this point, we have the answer, at least 8 + 1 + 1 + 1 = 11 games.

However, this is the wrong answer!

In fact, there is a better solution!

If you do not choose any of the 8 horses when there are 9 horses left to race, you remove the group 2 winner and leave the remaining 8 horses to race.

If the winner of Group 3 takes first place in this match, then the top four are already determined and only 10 matches are required, since the winner of Group 2 has previously been proved to be better than the winner of Group 3. If it’s not number one, there’s still one more game to go.

So the right answer is at least 10. Are you right?

Finally, why does this question pop up in programmer interviews? Smart you must have found that the above horse racing problem is essentially a TopN problem, which can be solved by divide-and-conquer, which is a classic algorithm thinking. If it is in a distributed system, the advantages of parallel computing are reflected. Resources (such as 8 runways) can be used to simultaneously compute for each group, thus improving the computing efficiency. In addition, it is important to use existing data results.

Have a great weekend and don’t forget to give the fish skin a thumbs up! ❤ ️