Wednesday, July 16, 2014

25 horses 5 tracks 3 fastest puzzle



Let’s say that you have 25 horses, and you want to pick the fastest 3 horses out of those 25. In each race, only 5 horses can run at the same time because there are only 5 tracks. What is the minimum number of races required to find the 3 fastest horses without using a stopwatch?

Draw out a table
we’ve had 5 different races, we can eliminate the slowest 2 horses in each group since those horses are definitely not in the top 3. This would leave these horses:

X1   X2   X3
X6   X7   X8
X11 X12 X13
X16 X17 X18
X21 X22 X23

We also know the 5 fastest horses from each group, let's race them, Let’s say that the 3 fastest in that group are X1, X6, and X11 – automatically we can eliminate X16 and X21 since those 2 are definitely not in the top 3, also X12, X13.

we don’t need to race X1 anymore, as it is fastest in all groups.
We can eliminate X8 as it at most can be 4th fastest when X6 is the 2nd fastes.

X2   X3
X6   X7
X11

Now we can have 5 + 1+ 1 = 7 runs to find  3 fastest horses.

Read full article from 25 horses 5 tracks 3 fastest puzzle

Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts