HARD Google Interview Question – The 25 Horses Puzzle

hey this is pressure Locker there are 25 horses what is the minimum number of races needed you can identify the fastest three horses you can race up to five horses at a time 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 rake 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 would suggest to this problem by email from the puzzle maker terry nichols 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 to 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 finish 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 a two means the horse stepped in a second place in Group A so here's that final race we do one more race with a 2 a 3 B 1 B 2 and C 1 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 right I'll rearrange the horses if necessary so that it follows that the slow source 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 a 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 them are slower than a1 b1 and Siwon 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 B 2 so the horses in 3rd 4th and 5th 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 raise 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 any more 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 a 2 a 3 B 1 B 2 and C 1 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 runoff 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 milk 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 raise 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 among 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 blogs mind your decisions that you can follow on Facebook Google+ and patreon you can catch me on social media at Prashant Walker and if you like this video please check out my books there are links in the video description

39 thoughts on “HARD Google Interview Question – The 25 Horses Puzzle

  1. Help make this channel better!

    1. If there's a "hard" problem or any math topic you want covered, please let me know. Preferably send me an email–my address is listed on my blog and in the channel's "about" tab. I do extensive research so it takes me months to make some videos. The Google 25 horses puzzle, for example, was from an email I got in October 2016.

    2. I'm open to better video titles. If you do not like the title, suggest a better one. If enough people upvote it I will see it and consider changing the title.

    3. I have fulfilled almost every suggestion from supporters on Patreon (http://www.patreon.com/mindyourdecisions). If you make a pledge, even for $1 a month, it goes a long way to supporting videos that would take a long time to make but would get very few views.

    4. How do you feel about sponsors in videos? I ask since I personally get annoyed at seeing sponsors in a lot of the videos I watch. But I also understand creators need sponsors to make a living. I get many emails asking for sponsorship and I have passed on them for your sake. I'm curious what you think before I make a decision.

  2. How can you be sure that, for example, a3 is not faster than b1,c1 d1, or e1? I think you should keep the top 3 finishers each time. So that the final answer will be 12

  3. Is it 12?
    From 25, Top 3 3 3 3 3 = 15 left
    From 15, Top 3 3 3 = 9 left
    From 9, Top 3 3 = 6 left
    From 6, Top 3 of the 5, and a final race with the remaining 1.

  4. Start with the diagram after they eliminate the for losing horses from Group C. The winner of Group C is slower than the horse that won Group B. So what's how to say that the 3in limited horses from Group B are not faster than the winner of Group C the answer is flawed I think you need an eighth race to decide that but I'm done thinking about this

  5. That's a flawed answer. What if a horse that loses a race but comes in second.and that horse is faster than the winner of a different groups race. You my friend have a wrong answer. The only way to find the three fastest horses is to run 1 race with all the horses at the same time. Those who place 1st , 2nd , and 3rd are the fastest horses. That is the only way. You think your so smart.

  6. Has this video been edited since it was first posted? I don't understand how anyone can doubt the answer after having watched the explanation???

  7. I don't like your explanation of why 7 is minimum. You said: "we need another race to compare the winners to find the fastest horse". That is not the goal, you don't need to know what is the fastest horse, only that it is in the top 3. You can get that without knowing which one is the fastest. For example, let's say that there are only 10 horses. After race a1..a5 (a1 is the fastest), if in the next race you use a3 and other 4 horses and if a3 is faster from all horses but one, you will know that now that one is among the 3 fastest 3 without knowing if it is the fastest. So maybe you can arrange 6 races in a such a way to get more information than if you raced all different horses in the first 5 races. Maybe it is the correct result but your proof is not correct.

  8. Too long explanation.
    5×5 race, get rid of 10 horses.
    1×5 winners race get rid of 2 horses and keep the main winner.
    Bring 2 horses from winners group + second place and his second from first race + 3rd place. Race these 5 and take first and second. These 2 with main winner will be first 3.

  9. In step 2 you may also race all the second place horses. Have the winner of the 2nd best horses race with his original group along with the two horses I will describe next. Take the horses who had placed first against the second and third place finishers of the “race of the second best horses”. The top 3 finishers of this race are the fastest 3 horses.

  10. Interesting brain puzzle. I have gone to multiple interviews at Google and never once was I given a brain teaser as an interview question.

  11. It is possible to do this in 6 with a different method, though it would be inconsistent. You could race one group of 5 (group A). Keep the winner, A1 possible second A2 and possible 3rd A3. Eliminate A4 and A5. Divide the remaining hosed into groups of 4, so you have groups B-F. Race A1 in group B. eliminate the 4th and 5th place horses. If A1 gets 3rd or less, we can also eliminate A2 and A3. If A1 gets second, we can eliminate A3 while B3 and A2 become possible third place horses. If A1 gets first (the worst case scenario) B2 and A2 are possible seconds and A3 and B3 are possible thirds. Repeat this process of racing the winner from the previous group into the next group. On the sixth race , F, if the winner of E takes third or less we will know our 3 fastest horses. On the other hand, if that horse got second or first one or more races would be required.

    In the worst case of A1 taking first in every race, we would have {A2, B2, C2, D2, E2, and F2} as possible seconds and {A3, B3, C3, D3, E3, and F3} as possible thirds. We could race A through E in one race and take the winner the possible third of the winner's group, the second place F2 andF3 in a final race to get the final second and third place horses in a maximum of 8 races.

  12. We will make 6 different group kk
    Select winer from them after that last race between winer horses and slect no1,no2,no3 is the fastest horse all over

  13. Since we have established that group a holds the fastest horse , how can you know that A4 and A5 are slower than horses from other letter groups you are including? They could have faster passing time, just slower than the A.

  14. The real answer is 5, because i will just bring my autistic friend who will count in his head. No watch needed.

  15. First thing came up to me was 11. Race 5 random horse. Take first three finishers and 2 random horses that didnt race before. Repeat until no horse left. 7 was quite clever.

  16. The correct answer is 5… not 7… You specifically state "minimum." So you need to just see all the horses race, which gives you 5.

  17. 6 races 5 races with 5 horses in each to identify which horse that is the fastest in each race then take the 5 winners and put them together in a single race and take the 3 horses that crosses the finish line first

  18. The Protest Flag went up after race 7 and the stewards have been called in. Form reversal! The horses came in a3b2c1b1a2 when the punters were expecting either b1 or a2 to run in second and third place to come from one of the groupings c1a2 b2 or b1a3. You can avoid the protest flag by not racing two horses that have already been in a race together. There would need to be a race off for second and another race off for third from one of the groupings depending on which horse lost the first race off for second place. All up that’s 8 races to keep the punters happy.

  19. Everybody say that you will take winner of each group. But what if all 20 horses from last 4 groups are slower the slowest horse from the first group? I think there is no solution as you don't know the times of each group 🙂

  20. I thought it was 11. As there are 25 horses and we aim to get the fastest 3 among the whole group, 22 horses would have to be removed. Of each race of 5, i'd eliminate the slowest 2. Add 2 more horses at random, repeat the race and eliminate again the slowest 2. We'll have to do 11 races to eliminate 22 horses and be left with the fastest 3. That way, each winner were able to race against all of the other horses, we'd no longer think of "what if the fastest 3 were placed in the same row? "

  21. I dont think that is possible because what if every hore in group "b" is faster that the first horse in group "c". what I mean is that every horse in group "b" could run a round in like 30sec but the fastest horse in Group "c" is slower and it takes up to 40sec. so you cant wipe out "b5 and b4" cause you dont know if they maybe faster then "c1". pls correct me if im wrong.

Leave a Reply

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