How To Solve Google’s 25 Horses Interview Question

How To Solve Google’s 25 Horses Interview Question

Hey, this is Presh Talwalkar There are 25 horses What is the minimum number of races needed so you can identify the fastest three horses? You can race up to five horses at a time, but you do not have a watch This problem is sometimes asked as a technical interview question at companies like Google But since it is a little bit vague, let me present another version which has some details that allow you to solve the problem There are 25 mechanical horses and a single race track Each horse completes the track in a pre-programmed time and the horses all had different finishing times, unknown to you You can race up to five horses at a time After a race is over you get a printout with the order the horses finished, but not the finishing times of the horses What is the minimum number of races you need to identify the fastest three of all the horses? I was suggest to this problem by email from the puzzle maker Terry Stickels And it is sometimes asked as an interview question at companies like Google So can you figure it out? Pause the video right now and give it a try When you’re ready keep watching the video for a solution The answer is you can find the three fastest horses in a minimum of seven races I will first describe the procedure in words, and then I will go over the solution in detail. So that you understand why it works The first step is to divide the 25 horses into groups of five and race the horses in each group This will be a set of five races Next, take the winner from each group and race those five horses The winner of this race, which is the winner of the winners is the fastest horse overall Now in order to get the second and third fastest horses, we’re going to have to do one more race But to describe that race I’m going to have to present some notation So label the five groups from step one as A, B, C, D, and E to correspond to the groups for the horses that finished in first, second, third, fourth, and fifth place for the race in step two In other words, label the groups in Step one according to the results of the winners race in step two Furthermore, write a subscript to identify the order that the horse finished within a group So A2 means the horse that finished second place in group A So here’s that final race. We do one more race with A2, A3, B1, B2, and C1 that is race the second and third fastest horses from group A The fastest and second fastest horses from Group B. And the fastest horse from Group C The top two finishers in this race will be the second and third fastest horses overall So now I’m going to show you this procedure in detail and explain why it is the correct procedure So we start up by dividing the 25 horses into groups of five In this race we have a race of five horses and I’m going to illustrate it so that the slowest horse is on the left and the fastest horse is on the right I’ll rearrange the horses if necessary so that it follows that the slowest horse is on the left and the fastest horse is on the right I’ll do this for all the horses in all of the different groups Now, we are going to take the winner from each group and race those five horses This will be the horse on the far right hand side of each group The winner of this race, which will be the winner of the winners, will then be the fastest horse overall I am again going to draw this so that the slowest of the winners is on the bottom and the fastest of the winners is on the top We’ll rearrange the groups as necessary to make this diagram work So now we have the fastest of the winners This will be the fastest horse overall We know that it’s beat every other horse within this group, and it’s beat the fastest horse in every other group So we have identified the fastest horse overall Now in order to get to the second and third fastest horses, We’ll have to identify the different groups so we’ve the fastest group being A and the slowest group being E So how are we going to get the second and third fastest overall? We’re going to do this by process of elimination We can eliminate any horse that is slower than at least three other horses If a horse is slower than at least three other horses There’s no way it could be the second or third fastest overall So to start out with, we can eliminate all the horses in group E Every single horse in this group will be slower than the fastest horses in groups A, B, and C This is because the fastest horse was slower than the fastest horses in these groups A, B, and C So all of the horses in groups, in group E, cannot possibly be the second or third fastest overall For exactly the same reason we can eliminate all horses in group D All of them are slower than A1, B1, and C1 We can continue this logic, and we can eliminate all the horses in Group C, except for the fastest horse All of these other horses will be slower than A1, B1, and C1 Now in Group B, we can eliminate all the horses except for the two fastest horses B1 and B2 All of them will again be slower than A1, B1, and then B2 So the horses in third, fourth, and fifth place in Group B can be eliminated From group A, we can eliminate the 5th and 4th fastest horses because they will be slower than the top 3 horses within their own group We’re left with 6 horses. We can only race five at a time, but we can actually get rid of one of these horses We’ve already identified the fastest horse overall, A1, so we don’t need to race it anymore We already know it’s the fastest overall we can’t learn any more information by racing it So we can actually remove this horse from our race So we now have A2, A3, B1, B2 ,and C1 and we do not know the relative speeds of these different horses So we can do one more race with these five horses The winner of this race will be the second fastest horse overall and the runner-up will then be the third fastest overall So these will be 7 races which will allow us to identify the three fastest horses Now just a quick note. We’ve shown that 7 races is sufficient. I just want to explain why it’s minimal We obviously have to race each of the 25 horses once And since we can race 5 horses at a time that means we’re going to at least start out with 25 over 5, which is 5 races We’re then going to need to compare the winners, which will be one more race, And we’re then going to have to compare at least the second place from group A to the fastest horse in Group B amongst other possible comparisons in order to find out the second fastest horse So we know at least seven races will be needed and we’ve shown seven races is sufficient Therefore the described procedure is optimal Did you figure this out? Thanks for watching this video please subscribe to my channel I make videos on math and game theory You can catch from my blog “Mind Your Decisions” that you can follow on Facebook Google+ and Patreon you can catch me on social Media at Presh Talwalkar and if you like this video please check out my books. There are links in the video description

100 thoughts on “How To Solve Google’s 25 Horses Interview Question

  1. i'll admit i never really "pause here to solve the problem", but i knew even in that short time for sure a elimination tournament was required, so it couldn't possibly be less than 7. i didn't know it would be exactly 7 though. didn't have enough time to think that far. i thought it would be more like 9 or something. the solution was a lot cleaner than i thought it would be.

  2. Without the added clarifications, you could very probably just do 5 races and eyeball it. You know, or you could get really cheesy and look up the horses’ times in past races etc. Lotta fun ways to answer this

  3. First, how can we assume that the horse a2 is faster than the horse e1? Lets assume that the speed of horse a1 is 30 and that a2 is 5. We can also say the b1 is 25 c1 is 20 d1 is 15 and e1 is 10. Then we can say that the speed of the horse e2 is 8. So in my opinion this method wont work if you dont have a timer or speed of the horses.

  4. I'm thinking 8:
    1-5: get 5 groups and get the fastest from each.
    6: race the fastest of each group
    7: take out the fastest, and replace it with the second fastest from its original group
    8: take out the fastest of race 7, and replace it with the next fastest from the winners original group

    The fastest three are the winners of races 6,7, and 8 respectively.

  5. Honest question:
    MINIMUM races NEEDED? What's the difference to the MAXIMUM races needed, which would assume worst case scenario/worst luck?
    So now if we have maximum luck, what does this mean? Just 1 race?

    It's clear obviously what is meant by the question, just I wonder whether the use of maximum, vs minimum makes any difference. Looks like the word "needed" dictates the interpretation anyways.

  6. What if the last 4 horses in group a and group b are the slowest of all the horses. Your process of elimination can not work this way.

  7. No wait. I don't get it. Why don't we just stop at step 2?
    We have done the race of winners. Now the we can find out 1st 2nd and 3rd from that race itself. You didn't explain why we need the 7th race?

  8. How small is the largest possible answer, to set an upper bound? Each race eliminates at least two horses so to eliminate 22 horses takes a sensible maximum of 11 races. Which is smaller than another famous upper bound IE Graham's number

  9. I says 7 on begining as well, but it can be 8 on the end needed. Because of on 7th race order on finish will be a2,a3,b2,b1 and c1 it's means that in group a we can have a 5 best horses overall… And now I get it, 7 is sufitian.

  10. I disagree with your solution. Theoretically, since you don’t know who the fastest horses are and you race the horses per your example, then after the first race results come in, the horses that came in second through fifth place would be eliminated. The problem is that the horses that came in second and third could be faster than all of the rest of the horses, but since they lost in the first race you would never be able to determine this because they got eliminated.
    In order to prevent this issue you would have to take the top three horses from each race and move them to the next heat. Then take the winners and race them against each other until you are able to determine the top three fastest horses.
    Start with 25 horse
    Race 5 horses in 5 races. You end up with 5 first place, 5 second place and 5 third place horses winners.
    Race the second and third place horses until you end up with 5 horses.
    Then race three more races to obtain the absolute top three fastest horses.

    Next solution: spend a little time and buy a stopwatch. As each horse races you will be able to rank each horse from first to last!

  11. You answer is wrong . If I had the time I would explain why your answer is riddled with flaws.
    A hint , your 5 races are independent events , however you are treating them as if they are dependent events.
    It takes 11 races to insure you have the fastest 3.

  12. The proof is bad, you can't follow ur own method in a general proof. It has to work for all methods, where information theory will probably provide a proper proof.

  13. I would say, it is seven races: make 5 races with 5 horses each, then take each winner and let them race and you get the fastest horse. Then take the horses that came in second and third from the winner's group, the winner and second from the second's group and the third of the 6th race. The horses that come in first and second in this race, will be the second and third fastest of all horses.

    This means, the fastest three horses could be in the same group right from the beginning (that's why you have to put the second and third from that group into the last race), or in two groups (that's why you also have to put first and second from the second horse's group into the race which could in fact be the second and third fastest of all horses), or in three groups which means that the fastest of each of these groups is one of the fastest three horses, so you have to put the third horse of the 66th race in as well.

    In other words, the fastest three horses could be:
    1-1 (first of 6th race and first of race 1-5, of course), (1)-2, (second of race 1-5 of the 6th race's winner), (1)-3 (third of race 1-5 of the 6th race's winner)
    1-1, (1)-2 (second of race 1-5 of the 6th race's winner), 2-1 (second of the 6th race, winner of race 1-5)
    1-1, 2-1, (second of 6th race, winner of race 1-5), (2)-2 (second of race 1-5 in the group of the 6th race's second)
    1-1, 2-1, 3-1, (winner, second and third of race 6, all winners of race 1-5)
    So, 1-1 is the fastest horse and the two fastest among (1)-2, (1)-3, 2-1, (2)-2 and 3-1 are the second and third fastest horses.

  14. Well.. You could get it in 6! Let the first 5 horses run. Then let the second horse of that first set run against the next 4.. If the horse gets first run it against the next 4.. And so on.. Hopefully this horse gets 2nd in the last run.. Than you know the 3 fastest horses for sure in only 6 runs! It was the first and second of the first run and the first of the last run… It is a gamble but still the minimum is 6 races!

  15. 6 is the minimum when all 3 fastest horses are already in the first race (by chance ofc): after the first race take the 3rd fastest horse and pair it every time with 4 of the remaining untested horses. It will always be the fastest of all the other groups.

  16. Six races are needed. After the 5 first races with groups of 5, make the 6th race with the winners. The first, second and third of the 6th race are the 3 fatest horses.

  17. Important clarification: This question is implicitly asking about worst-case optimization. That means that if a solution works sometimes with 6 and sometimes with 7, it counts as 7 for the purposes of this question.

  18. What if the 5 horses in group "a" were actually faster than all other horses … How you will solve it without a watch

  19. 6 races because after 5 first races you can find 5 fastest horses so the sixth race you can identify 3 fastest horses

  20. I didn't get it. How is it possible to identify the slowest group if we don't know their results? I mean, you can only know order in each group, but you cannot order the groups themselves. Correct me if I'm wrong, please. Thanks.

  21. My logic: we need the 3 fastest horses and can race 5 at once, this means we can eliminate 2 horses per race. We start with 25 horses and want to finish with 3, so we need to eliminate 22 horses, meaning we need 11 races.

  22. Your chart seems defective. You cannot compare the rows because we lack a watch.
    It seems that 6 horses remain, not 5. We cannot eliminate c2 because c1 and c2 can be the second and third fastest horses so we need to race them together, too. In other words, we can't make sure that c2 is slower than 3 horses. The only thing we know about it is that it is slower than c1!!!!

  23. How would you know for sure that the second place in one group is slower that the first place in the other group since you don't know the finishing times?

  24. My answer is 18. 6 races to find out the fastest one from the group. Do it three times to find out the three fastest.

  25. How can we just eliminate group e and group d. Wht if group a 4th hourse speed is 7 and group e 5 hourse speed is 6

  26. Somewhere in your explanation, you have confused overall maintainable (endurance) speed with single instance (top) speed. But that's okay. Language is tricky.

  27. Attempting to solve this one at the moment, haha…for one thing, I realized you can't just race groups of 5 (5 times) and assume the fastest 3 are among the five winners, haha…4 of those 5 might be slower than the one who lost to the 5th (the second in line on that race), hell, the 5 fastest might have been in the first race…so we have to compare all the horses somehow (unless I misunderstand the problem; you don't have a watch so you can't time them and note how fast each is and compare it later; you have to see one beat the other without a way to later compare to another)…so, the total number of ways to compare each individual horse to each other horse is 25×24=600, that's the maximum number of races…we need to reduce that but in a way that all the horses get compared to each other (using "transitivity", haha…if X beat Y and Y beat Z, then X is faster than Z…we don't have to race all the horses against each other, but we need a systematic way that they're all linked by a race that will allow us to compare them to each other)…

  28. 7 is not the right answer
    We can't be sure that the 2nd horse of group a is faster than the 2nd of group e

  29. If we are making groups and selecting fastest from the group then all the three horses should be taken from that race to choose No.1
    I.e. only 6 races will be needed

  30. Hey but the loser( from some group)of the rase could be faster than the winner(from some group) of some race so it should be minimum of 125 races

  31. You can do it in 6 races if you assume each horse runs its fastest time each time, and under a very specific set of conditions.

    Run your first 5 horses. Horse 1 wins. Run horse 1 against 4 other horses four more times. Horse 1 wins each heat. You have now established with those 5 races that horse 1 is faster than the other 20 horses.

    You now run Horse 1 against the last 4 horses. As long as Horse 1 finishes 4th or 5th, the top 3 horses in that race are the fastest.

    Granted this scenario is unlikely, but it is the minimum possible.

  32. Ok…I think I finally got it, haha…I need to work on paper more…but that's what I said last time before realizing I didn't have it yet, after writing it down (I almost always notice it's wrong when I write it down)…given all my previous false alarms, haha, I feel like I probably didn't solve it yet…I know there are holes, but I think I see how to fill them…

    Here's why 6 races aren't enough: if there are 6 races, then 5 of the winners must race twice (which means that there will be a "surplus" of 5 horses, which will require that all the races have 5 horses in order for the total of individuals racing (ignoring duplicates), will be 30): why: if not then at least 2 winning horses will only race once…how do we compare them, in such a case? (hole, but easy to fill, haha, one can just "compare" one of the horses that only races once to the one that's determined to be the winner and show that one couldn't really know which of the two is fastest, etc, etc…now, haha, I really hope that's as simple as I just said)…

    Now that we know that 5 of the winners will race twice (which means the 6th can't, otherwise there wouldn't be duplicates, and, remember, there are 6 races, so 6 winning horses) we need to "compare" them to the 6th winning horse which can only have raced once…since it won, if any of the winning horses "participated in a race" then it's faster…so it must be the fastest horse, since there is no horse "above it" to show that any of the other winners is faster (of course, not rigorous here either, but I think that's obvious and can be easily shown)…one of the other winning horses has to be "in the fastest horse's race", haha, so to speak, because otherwise every horse in that race only races once, again, no way to compare the top three to the other horses, so we wouldn't have "solved the problem" (again, not rigorous, but hopefully obvious — until I realize I made a mistake, haha)…

    …anyway, haha…now realizing I don't have a path to saying it's not enough, but I think I have shown that if there are only 6 races, then 5 of the winners have to race twice, and the winner that only races once has to be the overall winner (or the problem isn't solved)…

  33. Without the times, it is possible this is the minimum, but it leaves the chance of it being incorrect still.

    If group A possess both the fastest horse, and the 4 slowest horses as well, you only know they came in 2nd, 3rd, etc, not how far behind A1.

    Same is true for group B, which somehow has the 2nd fastest horse, racing against the next four slowest horses.

    Meanwhile, and still not having times, horse C1 has a neck and neck five way finish with all of its horses.

    Again, no times, you just know what order they finish in. So yes, this could correct, but the method does not guarantee you end up with the fastest three horses. You do get the fastest overall, but 2nd and 3rd place are not absolutes.

  34. Can't C2 be faster than A3? For example, C1 got there in 10 seconds but C got there in 8 seconds and A3 got there in 9 seconds and A1 got there 5 seconds.

  35. I think it could be solved in 6 races simply by taking note of the length of the gaps in order of finish of the first 5 races. I.e a2 finished 2 lengths behind a1 etc. Do this for all 5 horses in each of the first 5 races. Then based on the results and gaps of the 6th race, simply do a comparative analysis. i.e. b1 finished a head behind a1 in the 6th race and b2 (from the initial race) had finished a head behind b1… so b1 and b2 are both faster than a2. Etc. Etc. You can extrapolate the relative speeds of all 25 horses after only 6 races.

  36. But if you do 5 races, select the 1 st of each and then do another with the winners ( those which u selected) and select the 3 better of that last race, then u have the 3 fastest… No ?

  37. The proof that 7 is optimal is a bit unsatisfactory. Basically what you said is “7 races are necessary in order to use this method that requires 7 races, thus you need 7 races.” You didn’t show that, for example, it’s impossible to perform some of the steps simultaneously. To be clear, I do believe it’s correct to say that 7 is minimal, but I think it could’ve been demonstrated more clearly in the proof.

  38. I paused and played the video only after solving the problem, now most important question is how much time does Google give in interview? 😁

  39. ❌THAT’S NOT TRUE !! ❌
    Because in one of the 5 races could be the 3 fastest Horses !! THE RIGHT ANSWER IS 12 !!

  40. Ok…finally back after spending a lot of time (I think unnecessary time, haha) on another problem…I think the proof should go something like this…:
    Why six races don't suffice…:

    Since there are only 25 horses, if there are 6 races, they can't be done simultaneously (some horses needing to race in several races)…even if several races are done at the same time, we can pick one and call it "the first race"…or, better, "a first race"…we're gonna try to show that at least 6 horses have to "race twice", that if we touched every individual that races, that 5 horses aren't enough as "copies", as horses that race elsewhere, that have another "instance" (note that at this point we don't know that one horse might not race 6 times, or that each of the "5 extra horses" is different…we're trying to show that just having 5 "extra" horses isn't enough, which would mean that 25+5=30 individuals, so 6 races isn't enough)…

    If a first race includes the fastest horse but not the 2nd fastest horse (now, any configuration can occur on the "first race", because we don't have any information about the horses so can't pick them such that the fastest races with the 2nd fastest on the 2nd race, or with any given horse, for that matter…we can actually suppose any configuration we like for a first race, I think we'll need to suppose more), then one of the horses must race again (that is, must race twice), otherwise we won't be able to "compare" any horse inside the group of horses in the first race with any horse not included in that first race, so we won't be able to know if the fastest horses is the fastest of all 25, etc…of course, haha, not very rigorous, but obvious, it would probably be easy to prove that…note that it isn't true that each of the fastest horses must race again, the slowest could happen to be faster than any other horses outside the group so that it would suffice, we need to suppose that it isn't in order to show more races are needed…now, haha, this makes me think my proof that 5 aren't sufficient isn't exactly rigorous enough either…one could possibly not race the winners with each other, well…that's actually not possible but we'd need to prove it instead of just stating it)…

  41. 7:34 better stated: "We only know the relative speeds of these horses to /at most/ one other remaining horse."

  42. Did with bingo trick
    According to position number(hidden)

    A – 12, 14, 15, 18, 25
    B – 2, 3 ,17, 19 , 23
    C – 6, 7 , 10, 13, 22
    D – 1, 5, 16, 20, 24
    E – 4, 8, 9, 11, 21

    First 5 race will get 1, 2, 4, 6, 12 as winner.
    Then eliminate all from group 6 and 12 above as it is the last 2 group.

    Then eliminate all as the video said then we left with D (1,5,16) , B (2,3) and E (4)

    Remove horse 1 as it is the winner.
    Race the last race and u get the top 2 as the top 3.

  43. 5 races and just count…and estimate the number if length 2nd and 3rd are behind. Google employees aren't that clever anyway.

  44. This is a ranking problem. I would solve it by using a modified merge sort algorithm where horses which already are too slow (ranked 4th or worse) are dropped for any further comparison.

  45. shouldn't the answer be 18? five races then race the winners of the respective groups and the winner of the winners would be the fastest horse.
    2.Do the five races again but without the fastest horse , so one of the groups would have 4 horses instead of one, then do another with the winners and you get the fastest of the 24 horses.
    3.Do the 2nd step again to get third fastest horse.

    My logic :say in group A the fastest horse finishes in 10 seconds and the second fastest in 9.9.In group B the fastest horse finishes in 9 seconds so that means the second fastest in group A is much faster than the fastest in group B, since a watch is not given doing 18 races would ensure getting the fastest horse.

  46. Ok…my new attempt, haha…examining "a last race" instead of "a first race"…a last race would be any of the races conducted (in time) last, there must be a horse who last races, and even if many race last simultaneously, all the races in question are "last races"…so, the question is, can a last race involve only horses who have never raced before?…The answer is no, since that would mean the other 5 races would have raced each horse exactly once (since only 25 could have raced at this point), and remembering that all horses must race…so, if a last race involves only horses that have already raced, then it would mean that all 5 other races are "not connected", which we showed isn't possible (every race has to have a horse who races twice participating, as I showed…well, perhaps not rigorously)…so at least one horse in any last race must be a new horse…now, it could happen that that "new horse" is the fastest (it's easy to show that any horse can be the fastest horse and that we can't determine it by elimination, haha…I don't think I need to bother)…

  47. Trying another approach, though I haven't finished exploring the previous one, haha…thinking about the fact that all horses need to be "linked", and that 22 of them need to be linked to some horse in 3rd place and be "below it"…only 3 need to not be "below" a horse in 3rd place…sounds like a graph theory-type thing, haha, and I don't know any graph theory…

  48. What is the use of the 7th race? The first, second and the third horse from the sixth race are the ones which we are looking for.

  49. Hey i wonder why you eliminate every horses in group E in the elimination stage? Since that the human doesnt have a watch, that means he would know the exact time right? I mean say in the winner group every horse’s result is incredibly close to each other, like 0.25 sec difference on every horse, and in group A the fastest horse is significantly faster than every horse in the group, lets give the group A winner a 5 second difference from the 2nd in group A. And in the group E despite having their fastest horse become the slowest in the final race, all the horses in group E have a very small time difference from each other, lets say 1 sec difference.

    So by that condition if in the winner group the approximate time are
    1 – 10s
    2- 10.25s
    3 – 10.5
    4 – 10.75s
    5 – 11s

    And in group A the result was :
    1- 10s
    2- 15s
    3- 16s
    4- 17s
    5- 18s

    And in group E was :
    1- 11s
    2- 12s
    3- 13s
    4- 14s
    5- 15s

    Isnt eliminating group E horses would give a false result?

  50. Oh wow! I actually got this right. I almost never get any of your puzzles right so I’m beyond thrilled! Love your channel!

  51. My guess before watching the video:

    I make the assumption that each horse has a consistent and distinct speed, as otherwise there are no fastest three. (This is actually specified in the video itself, so… yeah)

    To begin, five races of five horses each, with each horse in one and only one race. Keep the fastest three from each five, for 15 total remaining horses.

    Then three races of five horses each as above, keeping again the fastest three of each five. Nine horses remain, with eight races so far.

    Race #9: Race five horses of the nine remaining. Keep the three fastest, discard the other two to leave seven total.

    Race #10: Race the fastest three of Race #9 against two of the four not used in that race. Keep the fastest three, discard the other two to leave five total.

    Race #11: Race the fastest three of Race #10 against the two remaining horses not in that race. The fastest three of Race #11 are the fastest three horses.

  52. Paused the video. My answer is: brute force it, run every combination of horses and sort them in the process (insertion sort) and keep the 3 fastest. Then you can optimize the solution to reduce the number of runs.

    If interviewer asks for a straight up number, remind them that Google stopped asking these questions in the interviews and strongly discourages such behavior.

    This may ruin your chances of working with people who ignore common sense and save you millions of dollars in medical bills.

    You're welcome 🙂

  53. Nice puzzle…I got 8 as minimum on pausing the video.
    I thought firstly to race 5 groups of horses each group consisting of 5 horses which after 5 rounds gives 5 winners and after 6th round of these 5 winners will give 1 fastest horse then take out the winner from them and take the second one in the winners group and then race these 5 then we get the second fastest horse.Now take the second one of the basic group of the winner or the third one if the second horse of the first group wins then on having the 8th race we can get the third fastest horse.

Leave a Reply

Your email address will not be published. Required fields are marked *