HARD Google Interview Question – The 25 Horses Puzzle



There are 25 mechanical horses and a single racetrack. Each horse completes the track in a pre-programmed time, and the horses all have different finishing times, unknown to you. You can race 5 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 3 horses?

I was suggested this puzzle via email by Terry Stickels. This is also a popular interview question at tech companies like Google. See a list of all sources in my blog post for this video:
https://wp.me/p6aMk-58P

If you like my videos, you can support me at Patreon: http://www.patreon.com/mindyourdecisions

Connect on social media. I update each site when I have a new video or blog post, so you can follow me on whichever method is most convenient for you.

My Blog: http://mindyourdecisions.com/blog/
Twitter: http://twitter.com/preshtalwalkar
Facebook: https://www.facebook.com/pages/Mind-Your-Decisions/168446714965
Google+: https://plus.google.com/108336608566588374147/posts
Pinterest: https://www.pinterest.com/preshtalwalkar/
Tumblr: http://preshtalwalkar.tumblr.com/
Instagram: https://instagram.com/preshtalwalkar/
Patreon: http://www.patreon.com/mindyourdecisions

Newsletter (sent about 2 times a year): http://eepurl.com/KvS0r

My Books

“The Joy of Game Theory” shows how you can use math to out-think your competition. (rated 3.8/5 stars on 27 reviews) https://www.amazon.com/gp/product/1500497444

“The Irrationality Illusion: How To Make Smart Decisions And Overcome Bias” is a handbook that explains the many ways we are biased about decision-making and offers techniques to make smart decisions. (rated 5/5 stars on 2 reviews) https://www.amazon.com/gp/product/1523231467/

“Math Puzzles Volume 1” features classic brain teasers and riddles with complete solutions for problems in counting, geometry, probability, and game theory. Volume 1 is rated 4.4/5 stars on 13 reviews. https://www.amazon.com/gp/product/1517421624/

“Math Puzzles Volume 2” is a sequel book with more great problems. (rated 5/5 stars on 3 reviews) https://www.amazon.com/gp/product/1517531624/

“Math Puzzles Volume 3” is the third in the series. (rated 3.8/5 stars on 4 reviews) https://www.amazon.com/gp/product/1517596351/

“40 Paradoxes in Logic, Probability, and Game Theory” contains thought-provoking and counter-intuitive results. (rated 4.7/5 stars on 12 reviews) https://www.amazon.com/gp/product/1517319307/

“The Best Mental Math Tricks” teaches how you can look like a math genius by solving problems in your head (rated 4.7/5 stars on 4 reviews) https://www.amazon.com/gp/product/150779651X/

“Multiply Numbers By Drawing Lines” This book is a reference guide for my video that has over 1 million views on a geometric method to multiply numbers. (rated 5/5 stars on 3 reviews) https://www.amazon.com/gp/product/1500866148/

source

Fahad Hameed

Fahad Hashmi is one of the known Software Engineer and blogger likes to blog about design resources. He is passionate about collecting the awe-inspiring design tools, to help designers.He blogs only for Designers & Photographers.

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

  • September 26, 2017 at 7:03 am
    Permalink

    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.

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    i got a minimum of 6 races.. race A : you get a winner just like races B,C,D, and E. SOOOOOOOO, then, you take the winner of each race ( there would be 5 winners ( obviously ) ) and race them.. Botta Bing Botta Boom, NOW, to see if i am wrong.

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    wait wait wait u can make 6 races becouse you said that u see who came 1st 2nd 3rd 4th 5th

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    1 set of race is enough to get the fastest 3 horses. The scenario didnt require to test all 25 horses.

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    How can you arrange the horses from fastest to slowest (of the fastest) if you have no stop watch? Also, it's entirely possible that you could have all the fastest horses in one of the first races. Is this video an April Fool's?

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    Correct answer is 10
    Because the second fastest horse in a group may be the second fastest overall. OR the fastest horse in a group may be the 21 st fastest horse overall

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    6 races only second place and third place would be the the other two fastes horses

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    You may have the all the horses in group E faster than all other horses except wthe fastest of all other group.
    I.E: From fastest to slowest: A1, B1, C1, D1, E1, E2, E3, E4, E5, A2, A3, B2, B3, etc.
    Impossible to tell without the times.

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    How is racing the three final horses different from racing the last five horses in the sixth race other than leaving no remanders?

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    Why not just take top 3 finishes from the 6th race? That would be the top 3 fastest in minimum of 6 races.

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    answer is 6,,,,
    after dividing the horses in 5 groups ,, each group having 5 horses,,,,,
    in 5 races we can find out the fastest 5 horses just by picking the fastest horse from each race.
    now in 6th races, we can directly find out the top 3, just by looking at the print…..bec there we have order…..

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    There is a fatal error in your deduction. You cannot eliminate the other horses because by the time the final race is done, the participating horses are exhausted, at which point, the eliminated horses will actually run faster than the winners. Also, depending on the horses' stamina, the results in the 6th or 7th race may vary (ex. the second placer in race 6 may actually finish last in race 7 because it has been exhausted by 2 races)

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    amazing video.. i calculate minimum 6…after i understand 7 race is more important

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    Well…i guess I won't be working for Google anytime soon. What kind of questions will I get If i just want to clean toilets at Google?

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    Umm, how is the solution not 6? First you take 25/5 = 5. Have one more race and take the first second and third place winners. Boom your done. That's 6 races you tried to make the problem more complicated then it is.

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    Minimal 6 races…
    25/5 =5 races
    We pick 5 winners from 5 races and race them together and after completing the race we pick them as a 1 2 3 number simply..

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    I may be misinterpreting something along the line, but from my understanding the answer is 6. The question as a whole seems misleading. The question mentions a watch, but does not actually ask for you to list the finishing time, so having a watch is irrelevant. It also says to identify the three fastest horses overall, It does NOT ask you to rank the three fastest into 1st, 2nd, 3rd. So as I have interpreted, unless there is a 4-way tie in the 6th race, any further races would be unnecessary. Perhaps if the question was worded differently to include listing the finishing positions of the final three horses then a 7th race may be needed, but as it stands whichever three horses win the 6th race are the 3 fastest out of the entire 25.

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    Straight off I thought 6 then considered the runner up horses could be faster against #1 horse, which left another race of five. Got 7. I'm right, yaay!

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    i will just race the 25 horses in sets of 5 take the winners and race once more stand on the finishing lines and get the first 3 winners so i wont have to waste another round of race✌️😊

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    I didn't watch the video yet but couldnt you just do 5 races and time all the horses and take the 3 horses with the fastest times? Lol

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    Ain't nobody got time for that. Determine if you are going to be evaluating horses often enough to justify using capital to increase the capacity of the race track so you can race all horses at once in order to achieve optimal efficiency.

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    I don't get it. Using the Google question you do not have a stop watch so how do you know that the horses in group e are slower then group d?

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    My solution before finishing the video was 8. I'm glad my line of thinking was actually pretty close with the correct answer except for the final bit of optimization. If I had taken the time to fully visualize the problem, I might have figured out the last bit.

    Basically my thinking was the same, five races for five groups of horses. The sixth race, you race the fastest. The seventh race you replace the winner of race six with the runner up of his group. Same with race eight. I see now that racing the two slowest of race six for race seven and eight is redundant. This was an interesting problem.

    The next issue I was thinking about is repeat ability. If you wanted to find the fourth fastest, would the same model be successful for one more race? Does it scale well if you have 50 horses or want to find the top 5? I guess that's a fun way to extend the problem.

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    The proof that 7 races is minimal is not a proof. I don't question the fact that it is minimal just the presented proof is shaky. The reason is that we do not need to find the fastest horse only the 3 fastest ones.

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    Did anyone take more than 90 seconds to solve this puzzle? The second one was just more details to try to cause confusion.

    Reply
  • September 26, 2017 at 7:03 am
    Permalink

    You are not selecting the fastest horse and put it in group A. It is a random pick of 5 horses to put in a group, so there's NO WAY that you can tell that the 2nd fastest horse in group A is more faster than the 1st place horse in Group E. The more acceptable answer is just 6 races. The last race would be the race of winners of 5 groups. The top 3 horses that win the race is the TOP 3.

    Reply

Leave a Reply

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