Difficult Interview Questions

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.

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.

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.

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, 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.

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.

OFFICIAL ANSWER: 5 races 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. NOTE ABOUT FOLLOW-UP QUESTION: 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.

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.

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

View the answer on my blog at http://bit.ly/b8riKs

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.

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.

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.

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.

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. Comments Welcome

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

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.

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

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.

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

Does anyone have a logical method for this madness?

So i figured out the method. you start with 2500 which needs 3 pick ups. You drive the 3 first pick ups to a distance so that afterwards the new amount will only require 2 pick ups. Because you cannot lose 500 apples exactly with 3 pick ups at the same distance (3 doesn't divide 500) you need to lose 501 apples, so you drive 167 miles for each pick up initially. Now you have 1999 apples which requires 2 pickups, again you want to drive it such a distance so that you lose enough apples to make it the rest of the way in one go. Because u can't lose 999 apples in 2 drives of equal distance, you will need to lose 1000 apples, which brings us to driving 500 miles. Now you have 999 apples a distance of 133 miles from the end. You put it all in your truck and finish the trip and end up with 866 apples in Orlando. Definitely one of the hardest questions I have done.

Since the problem says that you drop an apple every mile and that you can store the apples along the road, I propose the following answer: - load fully the truck with 1000 apples, drive 0.5 miles, drop apples on side of road ( since drove less than 1 mile, no apples are lost). - go back (truck empty) load another 1000 apples, drives 0.5 miles and drop them off-together with the 1000 apples dropped off earlier (again no apples lost since drove 0.5 miles). - go back load 500 apples remaining, drive 0.75 miles this time and drop apples on side of the road. - go back to where have the 2000 apples on side of road, load 1000 apples, drive 0.5 miles and unload on side of road. - repeat sequence until reach destination - Will be able to transport all apples to destination

really easy on paper, in your head, not so easy. In your head, here's how I'd do it: 13 squared is 169- that's easy. then, 10 times 19 is 1690, and 3 times 169 is approx 500, so 2190 is an easy approximation. Only 7 off from the actual answer!

13*13 = 169. Then do 13*170 = 10 * 170 + 3 * 170 = 1700 + 510 = 2210 Then, 2210 - 13 = 2197

Do it on your head. 13*13 = 169. For 169*13 first 3*169 = 507 second 10*169 = 1690 Finally 169*13 = 507 + 1690 = 2197.

Travel to Hawaii to fire a rep. It was bad because there was no time to stay and relax. The owner insisted that I return immediately!

Had to terminate a female employee who was badly injured from a fire. It had been proven via testimony to us that she covered herself with gasoline and lit it off to get even with a boyfriend, but she said it was due to an accidental kitchen fire. Fire Marshall report also verified she was not telling truth. Our policy said no coverage from 'self-inflicted' incidents and she had lied to us about the cause of the fire. As I told her she was being terminated, I was looking at a melted face, and compresses on each of her arms, and in a torso cast. This was three months post incident and investigation. You don't feel good after a day like that one!

This is a comment. Steve... wow. THAT'S not hard... that's unreal.

The hardest thing I had to do is doing something for others

The answer is 7. Let monkeys be numbered 1-n. Each number less than or equal to 100 can be written as a 7 bit number. Hence, bottle one(0000001) is given to monkey 1. bottle three(0000101) is given to monkeys 1 and 3 and so on. Now say monkeys 1 3 5 died, it means that the number is 0010101 which means the bottle 41 is the poison!

The way it's written, it seems like one would be the answer, or perhaps considering a monkey's tolerance for wine, N = 100 / (number of drops of wine a monkey can drink before passing out)... When asked with the condition that the monkey will die some time later, i.e. not immediately, the binary number technique described by Sri Krishna is best.