Novantas

www.novantas.com
www.novantas.com

Interview Question

Associate Interview(Student Candidate) New York, NY

You have 15 horses that run various speeds. You own a race

track on which you can race the horses, and this track holds a maximum of 5 horses per race. If you have no stopwatch or other means of telling exactly how fast the horses are, how many races would you need to run between the horses to be ABSOLUTELY SURE which horses are first, second, and third fastest?
Tags:

0

Once this question is answered successfully, a follow-up question is posed: if you now had 16 horses, how many races will you need to run to achieve the same 1st, 2nd, 3rd ranking?

Interview Candidate on Jan 20, 2010
1

Anonymous on Jan 21, 2010
1

6 runs for 15 horses and 7 runs for 16. You run 5 horses first, then in every next run you keep the top 3 winners from the previous run. Of course, since these are horses, you should always give them time to rest between the runs. You still cannot be ABSOLUTELY SURE though - a fast horse may have had a bad day.

Anonymous on Jan 22, 2010
5

I contend 5.

Run all horses in the first 3 races (call these heats). This will limit your pool to nine candidates for the top three spots (as you can remove the slowest two from each heat). Run the second place heat finishers and two of the original first place heat finishers (just for kicks) in the fourth race.

With the information from the second place heat finishers, we can determine the final 5 horses as follows:
* Slowest 2nd place heat finisher from fourth race and his 3rd place heat finisher counterpart are out (as we know that that his 1st placer, the other 2nd placers and their 1st placers - 5 horses - are faster). 2 down, 2 to go.
* Middle 2nd place heat finisher from fourth race and his 3rd place heat finisher are out (as we know that his 1st placer, and the fastest 2nd placer and his 1st placer - 3 horses - are faster). 2 down.

So, final race is between all first place heat finishers, fastest 2nd heat horse and his 3rd place counterpart. The order this race is won determines the fastest three horses.

A bit wordy but hopefully, you'll get the idea.

A Lars on Jan 22, 2010
1

How about you can't be absolutely sure about the fastest horses. Otherwise you'd be rich from bettin' the ponies and not interviewing for this job.

B.S. on Jan 25, 2010
0

Very good A Lars. I came up with minimum of 5 races, 6 max. Walked thru your example, and came up with 4 minimum, 5 max. Well done.

SJO on Jan 27, 2010
0

I don't think Lars is necessarily correct in all cases because you may choose the 5 fastest horses in the first race of the first heat, so horses 4 and 5, which are eliminated are faster than horses 1 and 2 in the second race of the first heat.

hjc on Jan 31, 2010
0

hjc,
That's why in the last race you have the 3rd place of the fastest 2nd placer heat, to see if he's faster than the other 1st placers.

I've also got 5 races but in different way than Lars.
1st race 5 horses.
2nd, 3rd and 4th race is the first two places of the previous race and 3 new horses.
so after 4 races we can determine the fastests 2 horses of 14 horses.
the fifth race is between the 3rd placers of the previous races and the last horse.

matias on Feb 1, 2010
0

btw, in Lars method you can even find the 3 fastest horses out of 16 also in 5 races.
in the last race you don't need the 1 placer of the 2nd fastest because you obviously know he's faster than his 2nd and 3rd placers. so that gives you an opening for the 16th horse.

matias on Feb 1, 2010
6

Assume that you have numbered the horses 1,2,...,15. Since each race can accommodate at most 5 horses, the first three races will be 1,2,3,4,5 then 6,7,8,9,10 and then 11,12,13,14,15.
Now assume that the order the horses finish in those races is numerical (for simplicity) - i.e. in the first race 1 wins, 2 comes in second, ..., 5 comes in last.
We now know that horses 1, 6, and 11 are the winners of their respective heats. So in the fourth race, we race just these three horses against one another to see who is the outright fastest. Assume (according to our previous simplification) that 1 wins, 6 comes in second, and 11 comes in third. We now are CERTAIN that 1 is the fastest horse.
However, we don't yet know which horses are 2nd and 3rd fastest. But what we do know is that the only possible horses that can be the second fastest are horse 2 (immediate runner-up to horse 1 in the first race) and horse 6 (immediate runner-up to horse 1 in the fourth race.) And the only possible horses that can be third fastest then are 2 or 6 (depending which is second fastest), the immediate runners-up to these horses (horses 3 and 7), and horse 11, winner of the third race.
Consequently, in the 5th and final race, we pit horses 2, 6, 3, 7, and 11 against one another. The horses finishing first and second in this race are the second and third fastest horses overall.

When 16 horses are involved, we still need only 5 races to determine outright the first, second, and third fastest horses. We simply add horse #16 to the fourth race - recall that only the three heat winners raced in this race, and we therefore have room for horse 16. The rest of the race methodologies are the same.
For instance, if 16 comes in last in that race, then trivially it is not 1st, 2nd, or 3rd fastest. If it comes in any place but last, then we exclude the last place horse from the final race (which would be horse 1, 6, or 11) and instead include horse 16.

Hope this helps, and I am glad to see so many people taking an interest in this problem. Soon I will post another (albeit easier) interview question from the same round of interviews at Novantas.

Interview Candidate on Feb 1, 2010
0

You aren't taking into consideration that one heat could be entirely faster than the next. Yes 1 might be the fastest in its heat but maybe all 11 - 15 are faster than 1, so I don't see how you can be certain that 1 is the fastest horse after the fourth race.

brouh on Feb 1, 2010
0

whats wrong with fastest horse from each race in a fourth race with 16th horse?

Anonymous on Feb 2, 2010

This post has been removed.

1

I also say 5, but have yet another method. ;)

I start like Lars, i.e., run all horses in the first 3 races and get down to nine horses.

Then I'll run the three horses that finished first and two of the horses that came in second. That way I'll know already what the fastest horse is. I'll take out the last two horses from that race because I already know that there are 3 horses that are faster.

So all I need to do in the final race is take the 3 winners from the fourth race and race them against the two horses I haven't included in the fourth race.

ruthie on Feb 9, 2010
0

8 races:
You need 3 races with each 5 horses - you take the 3 fastest of each race
You have 9 horses left.
You need 2 races with 4 and 5 horses resp. You take the 3 fastes of each race
You have 6 horses left.
You need 2 races with each 3 horses. You take the 2 fastest of each race.
You have 4 horses left.
You need one final race with 4 horses. You will identify the 3 fastest.
However, admittedly, they will be exhausted at the end ; )
So practically it is maybe not the best approach - but in theory it should be ok.

Winning Horse on Feb 12, 2010
0

I wanted to type this answer as if I were thinking out loud in an interview (and before I looked at the posted answers). Anyone can work it out and give the answer here, but maybe it took them 3 hours. Here goes:

3 races gets you the 3 fastest, but clearly you don’t know their relative rank and if a 2 or 3 in one group is faster than a 1 from another. So race 4 gets you fastest 3 of that 5 group and race 5 gets you fastest 3 of that race group, then you would have 6, and race 6 gets you 3 which you add to the 1 and have a final race 7. (at this point I realize that is too simple for an interview question/answer and say) That was not so hard to figure out, so there is probably a more efficient answer, so let me rethink it. So after first 3 races, set aside the #1 horse of each. Then you have 6 second and third place horses. So if the original 3 groups were A, B, C and finishing places were A1, A2, A3, etc, then you know some of the orders and can use that to eliminate some horses without racing them. So in a 4th race you race A1, B1 and C1, and they finish in that order (for example), then you Know B1 and A1 are faster than C2 and C3 so you can toss C2, C3 out. You also know A1 is absolutely the fastest so you set him aside on the gold medal stand. Now you have B1,2,3, an C1,A2,A3 still 6 horses, which would cause 2 more races. (so at this point I ask to go to the white board to write some things down, as I am starting to do on my paper here at home). So I write down a matrix with A1,2,3, B1,2,3, and C1. On the white board, I start writing some possible outcomes and talking out loud, but it is taking longer than I would like (the key in the interview is to stay calm). I came up with one method that could do it in 5 races by racing A1, B1, C1 and two random #2 spots (in race four), then I showed that I could eliminate enough to bring in A3 and B3 in race 5 and then determine a final order. But then I saw a better solution by looking at it again. I realized after race 4 that I can eliminate B3, because if B2 is faster then C1, then B2 will be at best in third place, so there is no more spots and we never have to race B3. So now we have only 5 possible horse that can be second or third: A2,A3,B1,B2, C1. We run race 5 and the first and second place get second and third overall.

The one point is, the first easy answer is usually wrong when trying to find the most efficient solution to a logic question. The other point is, keep talking it thru, use the white board or paper in the interview to “show your work” as you think out loud. Also, if you’re ever get one of these questions in an interview and you know the answer, either tell them, or fake it by thinking down some wrong paths. If you whip out the answer too fast they be suspect you knew and lied. That decision must be made by your moral compass ;-)

FYI, after looking, this answer is same as InterviewCandidate. I think Lars went down the same more complicated path as I did when just "thinking out loud", but it was not as simple. Winning Horse - why would you post an answer that is so much worse then correct answers already on the board? Odd.

Also, the assumption is the horses never get tired and run at the exact same speed every time. You just can time them or "judge" which is faster without a head to head race.

0

I did not know the followup before reading answers, but I agree with Interview Candidate - add it as 4th horse the the 4th race to see if he knocks of one of the top 3 (and therefore the #2 and #3 behind them.) In my example, if #16 knocks off B1 (therefore B2B3C1C2C3), the you just test him against A2, A3 in race 5. If it knocks off C1, then it takes the place of C1. If it knocks off A1, then it gets "gold" and C1,C2,C3 are eliminated and the A's and B's must race. B3 is logically eliminated like I said in my example.

3

Agree Five Races, but don't agree with the methodology.

Here's how I did it

Number the Horses 1-15
Run three races. Race One Includes Horses 1-5. Race Two Includes Horses 6-10. Race Three Includes Horses 11-15.

For Simplicity
Race One Result Order - Horse 1,2,3,4,5
Race Two Result Order - Horse 6,7,8,9,10
Race Three Result Order - Horse 11,12,13,14,15

What do we know at this point? Horses 1,6, and 11 COULD be the three fastest horses. However, horses 2,3,7,8, 12, or 13 could also still be in the top three if you take into consideration, for example, every horse in Race One was faster than every horse in Race Two.

So how do we solve for this? Run a Fourth Race with Horses 1,6, and 11. Let's say, again for simplicity, the outcome of this race, in order is Horse 1,6, and 11.

Now what do we know? Horses 7,8,12, or 13 CANNOT be in the top three anymore. We already know Horse 1 is the fastest, but candidates for the top three remain Horses 1,2,3,6, and 11 because it still hasn't been proven Horses 2 or 3 are slower than horses 6 or 11.

Race 5 (Final Race) - Horses 1,2,3,6,11

Top three finishers are you top three horses.

Rocko72 on Apr 9, 2010
0

Best case scenario = 4 races:

1st: 1 2 3 4 5 eliminates 2 horses
2nd: 3 6 7 8 9 eliminates 4 horses
3rd: 3 10 11 12 13 eliminates 4 horses
4th: 1 2 3 14 15

Race 1, 2 & 3 eliminate 10 horses from the pool of top 3. Race 4 determines final rank.

Worst case scenario = 5 races.

1st: 1 2 3 4 5 eliminates 2 horses
2nd: 6 7 3 8 9 eliminates 3 horses
3rd: 10 11 2 7 12 eliminates 3 horses
4th: 1 6 13 14 10 eliminate 2 horses
5th: 1 6 13 15 16 Final rank 16th horse is bonus

Anonymous on Sep 30, 2010
0

4 races... you don't need to know the fastest until the last race. You merely need to eliminate those that are not in the top 3 until the final round.

Round 1: 3 races of 5 each. Take the top 3 in each (9 remain)
Round 2: 2 races of 4 and 5. Take the top 3 in each (6 remain)
Round 3: 2 races of 5 and 1. Take the top 3 in each (4 remain)
Round 4: 1 race of 4. Line em up and see who comes in 1, 2, 3.

Anonymous... on Nov 4, 2010
1

I see some interesting answers here - up to and including folks mistaking a 'round' for a 'race', thereby racking up a total of 8 races!. This may help to demystify the problem.

You have to run 3 races to start to get the 1-2-3 ratings for the three sets of 5 horses, let’s call them A1 to A3, B1 to B3 and C1 to C3 respectively. If you race A1, A2, B1, B2 and C1 you will identify the fastest horse, and the results will dictate the next step, as follows:

IF ... The results are:

A1, B1 – regardless of order
C1
A2, B2 – regardless of order

THEN ... You are done. For example, let’s say the result is A1, B1, C1, A2 and B2. You will have established that A1 is fastest, given that it beat B1 and C1, B1 is next fastest, given that it is faster than A2 (i.e. all other A horses) and C1, and C1 is third fastest, given that it is faster than A2 and B2, and you already know that it is the fastest C horse.

So anyone who thought that you needed a minimum of 5 races was wrong.

IF ... The results are:

The #1 of A1 and B1
C1
The #2 of A1 and B1
A2, B2 – regardless of order

THEN ... You need to race the slower of A1 and B1 against C2 to see which horse is third fastest.

IF ... The results are:

C1
The #1 of A1, A2, B1, B2
The #2 of A1, A2, B1, B2
The #3 of A1, A2, B1, B2
The #4 of A1, A2, B1, B2

THEN ... You need to race the #1 and #2 of A1, A2, B1 and B2 against C2, C3 to see which horse is second fastest and which horse is third fastest.

There is not a scenario where you need a sixth race.

If you add another horse to the mix – let’s call it X – then you will need 5 races, as follows:

It is still most efficient to run 3 races to start to get the 1-2-3 ratings for the three sets of 5 horses - e.g. A1 to A3, B1 to B3 and C1 to C3 respectively – and it is still most efficient to race A1, A2, B1, B2 and C1 to get your next level of information. But then things will change a bit:

IF ... The results are:

A1, B1 – regardless of order
C1
A2, B2 – regardless of order

THEN ... You will need 1 more race with A1, B1, C1 and X, to see if things change..

IF ... The results are:

The #1 of A1 and B1
C1
The #2 of A1 and B1
A2, B2 – regardless of order

THEN ... You need to race A1, B1, C1, C2 and X to get your true 1, 2, 3 rating.

IF ... The results are:

C1
The #1 of A1, A2, B1, B2
The #2 of A1, A2, B1, B2
The #3 of A1, A2, B1, B2
The #4 of A1, A2, B1, B2

THEN ... You need to race the #1 and #2 of A1, A2, B1 and B2 against C2, C3 and X to get your true 1, 2, 3 rating.

ravi@ravi.com

SWITCH on Dec 13, 2010
0

One race. Line horses 1-5 at the starting line, line 6-10 1/3 of the way down the track, and 11-15 2/3rds of the way down. first, second and third place winners are those who break the tape at each starting line.

For sixteen, just line up four horses in 1/4 increments. same one race.

csm on May 11, 2011
0

The answer to 15 horses or 16 horses is: 4 races total. Just figure it out.

HireMe on May 27, 2011