Wednesday, July 16, 2014

With My Eyes: 25 Horses, 5 lanes, no clock, top 5 (not 3)


The idea is that you have 25 horses, a 5 lane track, no timer, and want to find the fastest 5 horses. How many races can you do it in?

The idea is that you have 25 horses, a 5 lane track, no timer, and want to find the fastest 5 horses. How many races can you do it in?

NOTE THAT THE ORIGINAL PROBLEM WANTED ALL 5 IN ORDER, AND THIS WAY JUST GIVES THE FASTEST 5 POSSIBLY OUT OF ORDER AND NEEDS A 9TH RACE TO ORDER THEM PROPERLY.

I stayed up all night once to come up with an 8, and thought i did, but in the morning realized that I had made a mistake. BruteForce found a description of a solution for 8. It was on the same track as me, but he didn't make the mistake I did. I take no credit.

Anyhow, here's the write-up so it's a little more visual and easier to parse than the text answer he found.

You start by running 6 races. 5 races let every horse run, and the 6th is the winner's race. You're left with:

Ordering after race 6

Note that "1" is clearly the fastest horse, since he was never beaten, and we have some information about every horse relative to at least one other horse. We can also remove some as hopeless, since they're too far back along the known relative speed graph to possibly be in the top 5.

Let's remove those.

Losers removed

Now what? Well, if we want the top 3 in order we'd race 1.2, 1.3, 2, 2.2, and 3. That's 5 horses and the answer to the "top 3 in 7" problem. That's not what we want, though.

We're going to instead race 1.3, 2.2, 3, 3.2, and 4. Why? We know that at least one of 1.2 and 2 are in the top 5, and can figure that out based on the result of our race 7. Here's our race 7.

Race 7

Let's take the easiest result case first. 3 and 4 are the top 2. 3 had to have beaten 4, since we knew it was already faster. 2 is therefore in the top 4 in second position, and the final horse is one of 1.2, 2.2, 3.2, 4.2, 5. That's 5 horses and we can just race them. Brown indicates horses to be in race 8.

Simple 7 result

Now let's look at a complicated result. 1.3 and 2.2 are the top 2, in that order. What do we know?

The key piece of information is that since 2.2 beat 3, 3 cannot be in the top 5. Why? For 3 to be in, 2 would have to be in, as well as 2.2. Both beat 3. But that also means, since 1.3 beat 2.2 that 1.2 is in there too. We ran out of places. The same logic rules out 2.3. Depending on the result of race 7, you might have to flip the graph but can then apply the same reasoning as it ends up being symmetrical.

So in this case, which is an example of the most complicated situations from race 7, ends up looking like this:

Complex 7 result

1.3 and 2.2 run again, and 1.2 doesn't need to run because it has to be in the finals anyhow. The top 3 from this race are in the top 5 with 1 and 1.2.

This was a much better problem than the "top 3" version.
ses-5-race-tracks-How-many-races-you-have-to-run-to-select-top-5-horses-QTN_136645.htm
Read full article from With My Eyes: 25 Horses, 5 lanes, no clock, top 5 (not 3)

No comments:

Post a Comment

Labels

Review (554) System Design (293) System Design - Review (189) Java (178) Coding (75) Interview-System Design (65) Interview (60) Book Notes (59) Coding - Review (59) to-do (45) Knowledge (39) Linux (39) Interview-Java (35) Knowledge - Review (32) Database (30) Design Patterns (29) Product Architecture (28) Big Data (27) Soft Skills (27) Miscs (25) MultiThread (25) Concurrency (24) Cracking Code Interview (24) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Distributed (20) Interview Q&A (20) OOD Design (20) System Design - Practice (19) Security (17) Algorithm (15) How to Ace Interview (15) Brain Teaser (14) Google (13) Linux - Shell (13) Spark (13) Spring (13) Code Quality (12) How to (12) Interview-Database (12) Interview-Operating System (12) Redis (12) Tools (12) Architecture Principles (11) Company - LinkedIn (11) Testing (11) Resource (10) Solr (10) Amazon (9) Cache (9) Search (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Company - Uber (8) Interview - MultiThread (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Scalability (8) Cassandra (7) Git (7) Interview Corner (7) JVM (7) Java Basics (7) Machine Learning (7) NoSQL (7) C++ (6) Design (6) File System (6) Highscalability (6) How to Better (6) Kafka (6) Network (6) Restful (6) Trouble Shooting (6) CareerCup (5) Code Review (5) Company - Facebook (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Be Architect (4) Big Fata (4) C (4) Company Product Architecture (4) Data structures (4) Design Principles (4) Facebook (4) GeeksforGeeks (4) Generics (4) Google Interview (4) Hardware (4) JDK8 (4) Optimization (4) Product + Framework (4) Shopping System (4) Source Code (4) Web Service (4) node.js (4) Back-of-Envelope (3) Company - Pinterest (3) Company - Twiiter (3) Company - Twitter (3) Consistent Hash (3) GOF (3) Game Design (3) GeoHash (3) Growth (3) Guava (3) Interview-Big Data (3) Interview-Linux (3) Interview-Network (3) Java EE Patterns (3) Javarevisited (3) Map Reduce (3) Math - Probabilities (3) Performance (3) Puzzles (3) Python (3) Resource-System Desgin (3) Scala (3) UML (3) geeksquiz (3) AI (2) API Design (2) AngularJS (2) Behavior Question (2) Bugs (2) Coding Interview (2) Company - Netflix (2) Crawler (2) Cross Data Center (2) Data Structure Design (2) Database-Shard (2) Debugging (2) Docker (2) Elasticsearch (2) Garbage Collection (2) Go (2) Hadoop (2) Html (2) Interview - Soft Skills (2) Interview-Miscs (2) Interview-Web (2) JDK (2) Logging (2) POI (2) Papers (2) Programming (2) Project Practice (2) Random (2) Software Desgin (2) System Design - Feed (2) Thread Synchronization (2) Video (2) ZooKeeper (2) reddit (2) Ads (1) Advanced data structures (1) Algorithm - Review (1) Android (1) Approximate Algorithms (1) Base X (1) Bash (1) Books (1) C# (1) CSS (1) Chrome (1) Client-Side (1) Cloud (1) CodingHorror (1) Company - Yelp (1) Counter (1) DSL (1) Dead Lock (1) Difficult Puzzles (1) Distributed ALgorithm (1) Eclipse (1) Facebook Interview (1) Function Design (1) Functional (1) GoLang (1) How to Solve Problems (1) ID Generation (1) IO (1) Important (1) Internals (1) Interview - Dropbox (1) Interview - Project Experience (1) Interview Tips (1) Interview-Brain Teaser (1) Interview-How (1) Interview-Mics (1) Interview-Process (1) Jeff Dean (1) Joda (1) LeetCode - Review (1) Library (1) LinkedIn (1) LintCode (1) Mac (1) Micro-Services (1) Mini System (1) MySQL (1) Nigix (1) NonBlock (1) Process (1) Productivity (1) Program Output (1) Programcreek (1) Quora (1) RPC (1) Raft (1) RateLimiter (1) Reactive (1) Reading (1) Reading Code (1) Refactoring (1) Resource-Java (1) Resource-System Design (1) Resume (1) SQL (1) Sampling (1) Shuffle (1) Slide Window (1) Spotify (1) Stability (1) Storm (1) Summary (1) System Design - TODO (1) Tic Tac Toe (1) Time Management (1) Web Tools (1) algolist (1) corejavainterviewquestions (1) martin fowler (1) mitbbs (1)

Popular Posts