Recebtly, I was asked an IQ qurstion during an interview. The question is: There are 25 hourses. Each race, you can put 5 hourses. You don’t have a stopwatch, but only pen and paper. What is maximum races needed to find out the top 3 hourses? Assuming that each hourse has a unique speed, and they always run at that speed no matter how many races they’ve taken.
I spent like 15 minutes during the interview to solve this but didn’t get to the correct answer. In the end, the interviewer said my approach was correct and gave me the final answer.
First, I divide 25 hourses into 5 groups of 5 to gwt the fastest one of each group. Then I put those 5 hourses together in a race to know the top 3 of them. But this does not guarantee that the 2nd and 3rd is in top 3 of 25 hourses. And I couldn’t think of a way to sort out the 2nd and 3rd in correct order. And then I go try other apporach but ended up with a brute force solution. First I put 5 random hourses in a race and get out top 3. Then add new 2 hourses to race with current top 3. So the total number would be 11 races. Of course this is not the best solution. I just tried to show how I think with the interviewer.
Now back to the correct approach that I gave up during the interview. I have made 6 races so far, it should not take more than 4 races to find the 2nd and 3rd to defeat my brute force solution. Let’s start from scratch.
Round 1:
Make 5 races, with 5 hourses in each race. We can find the
best hourse of each race.
Round 2:
Make 1 race with the bests in round 1. We then number the groups
by order of thier best hourse in round two (the 1st hourse is in
group 1, the 2nd hourse is in group 2 and so on).
The guys made it to round 2 deserve a name, let’s call them #1, #2,
#3, #4 and #5 by their finish order.
We know for sure that #1 is the fastest one.
But the 2nd and 3rd of all hourses is not decided.
Because they might be in group 1 and already lost to
#1. Or in case #2 is the 2nd best, and the 3rd have lost
to it in group 2.
That’s why we need an other round to find out the actual
2nd and 3rd fastest hourses.
Round 3:
From group 1, we pick the next 2 hourses finish after
#1. From group 2, we pick the next one hourse finish
after #2. And finally, we add #2 and #3 to the race as well.
The first 2 fastest horses of round 3 are the 2nd and 3rd
fastest hourses of all.
Why?
Because 2 guys in group 1 are only defeated by #1, so they
have even chance to be in top 3.
In group 2, we only pick 1, because it’s slower than #2, so
it must be slower than #1, but not necessarily slower than #3.
We add it to the race to see #3 is really worth it.
So after round 3, we can guarantee top 3 are concluded.
The number of races needed is 5 in round 1, 1 in round 2 and 1 in round 3. So total is 5 + 1 + 1 = 7.