## Citrix Online Interview Question Software Engineer in Tests

- 0of 0 votes
Classic 25 horse problem,

25 Horses,

Have a 5 horse track,

No stopwatch,

How many races are required to determine the 3 fastest horses.

Total of 8 races

5 races = 25 horses = take top 3 ==left 15 horses

from 15 horses run 1 race ==of top 5 horses == we get the 1st fastest horse

then run the rest 4 faster + next to fastest horse in 1 race = now we get 2nd fastest horse

then run the race again without 1st and 2nd fasterst horses and get the next fastest

total of 5+1+1+1= 8 races

@lyzoridc

3rd point is not clear to me, because d1/e1's performance may be better than b2/a2/b3. d1 and e1 are faster than b2,a2 and b3 in the first race.

@kaps84

because d1/e1 is slower than b1/c1, if there is b1/c1, d1/e1 can never reach top3

we only know b1 is faster than b2, a2 is faster than a3, b1 is faster than c1.

but we should continue judging whether b1 is faster than a2/a3, whether c1 is faster than a2/a3, or b2 is faster than c1, or their opposite results.

6 races are sufficient

Run race between winner of each 5 races

and take out first 3 winner those are the best 3

Step 1. Divide the lot into 5 groups such that each group contains 5 horses. Conduct a race of each group.

Total races = 5

Step 2. Conduct race between the topmost horses in each group. The winner in this race eliminates all other 24 horses. He is the fastest. Now we need 2nd and 3rd.

Total races = 5+1 = 6

Step 3. Take the horse who got second from the group that the fastest horse belonged to. Conduct a race between it and rest four from step 2. The firsr and second in this race are the second and third fastest horses.

Total races = 5+1+1 = 7

It cannot be 8 . Infact last race would be conducted with just two horses. Second horse from the group that the fastest horse belonged to and the horse who got second in step 2.

Correct me if i am wrong .

hi guys , u have randomly created the groups of horses , ok .

so how you guys can sure that my d2 is not better than a2 . if my a1 complete its first race in 5 mins and a2 complete in 6 mins and similarly my d1 complete race 5.1 mind and d2 complete in 5.5 min then how u guys remove d group completely if he lost in toppers race . may be d2 would be eligible for 2nd. and let suppose my b1 complete its race in 5.7 min then b1 is winner for b group but it is not better then d2 . Then how you can directly remove d group or e group. with this solution every horse did not take part or compete properly.

Found this good explanation so I cant take the credit for this but this helps explain well.

Split the horses into 5 groups and race each of the 5 groups (5 races). After that, you have the horse placements for each group. I laid it out like this:

A B C D E

1 1 1 1 1

2 2 2 2 2

3 3 3 3 3

4 4 4 4 4

5 5 5 5 5

Five columns, one for each group of horses, lettered A-E. Each number represents a horse... say horse A1 is the one that came in first place from group A, C2 is the horse that placed 2nd in group C, and so on.

You can eliminate all 4's and 5's from the chart, since we know that there are at least 3 horses that are faster for each 4th and 5th place horse.

A B C D E

1 1 1 1 1

2 2 2 2 2

3 3 3 3 3

Now race all the 1's (race #6). This will give you the fastest horse from the initial 25. But what about 2nd and 3rd place?

Let's say A1 got 1st, B1 got 2nd, C1 got 3rd, D1 got 4th and E1 placed last in race #6. A1 is definitely the fastest horse, but B1 may or may not be. Horse A2 can still be faster than B1- we have never raced them together before.

Approach it this way: which horses can we eliminate? Find all horses that we know have at least 3 horses faster than them. We can eliminate D1 and E1, because we know that A1, B1, and C1 are all faster than them. We can also eliminate all other horses in columns D and E below them. We can't eliminate C1, but we can eliminate C2 and C3. We also eliminate B3, since B2, B1, and A1 were all proven to be faster.

A B C D E

1* 1 1

2 2

3

The only horses left to race are A2, A3, B1, B2, and C1. (Race #7). The 2nd and 3rd place finishers are then 2nd and 3rd fastest from the original 25.

8 races

Do 5 races, let's group them to A, B, C, D, E

Fastest horse from each group, call them 1A, 1B, 1C, 1D, 1E, do 1 race, winner = fastest horse.

Say that the winner is horse 1D, now do 1 race between 1A, 1B, 1C, 2D, 1E, and the winner is the 2nd fastest horse because you are racing the fastest horses from each group (excluding the #1 horse)

1 last race, say the winner from before is horse 1B, so then race 1A, 2B, 1C, 2D, 1E. The winner of this race is the 3rd fastest horse. Say, 2B wins.

1st, 2nd, 3rd = 1D, 1B, 2B

Not true, Just because they are the fastest horses in their respective race doesn't mean that they are faster than horses from the other 4 races. Pose the example that H20-25 are in the final race, that doesn't mean that H 1 or 2 couldn't be faster than the 2nd place-5th place of that H20-25 vs. race.

No stop watch but they dint say no measuring tape right?

if we can measure the distance.. then we will need a max of three races..

5 horses start running from both the ends of the track.. if we have a measuring tape its trivial to find the fastest five horses as the horses that traveled the longest distance. do this thrice we can get the top three.. if this method is not ridiculous and no one abuses me.. i can tell u one more way to get to just 2 races :) anyone up?

should be 8 races.

what about all 3 fast horses are in same team. 7 races can't determine that case.

7 races can still determine. there are initially 5 teams. you note the top three horses in each team.. others are out of competition.. then have a race between winners of all races (6th round) cos the fastest has to be from these 5. Now again note the top 3. 1st one is surely fastest. second and third can be among

1 and 2 --> horse which came second and third in fastest horses team in first 5 races

3 and 4 --> horses that came second and third in 6th round

5 --> the horse which came second in first five races in the team to which second horse of round six belongs.

all other horses are eliminated. Thus only one more race is needed.

7 races should do the job. Lets assume a1, a2, a3, a4, a5, b1, b2, b3, b4, b5, c1, c2, c3, c4, c5, d1, d2, d3, d4, d5, e1, e2, e3, e4, e5 are the horses belonging to five groups a, b, c, d, e.

First race all 5 individual groups: 5 races

Now assume a1, a2, a3, b1-b3, c1-c3, d1-d3, e1-e3 are the top 3 in each group in the same order(a1 - fastest).

Now race a1, b1, c1, d1 and e1 - 1 race -> this should give us the fastest horse in all. Assume a1 - is fastest. Eliminate a1 from the group. Next assume b1 - 2nd, c1- 3rd, d1- 4th, e1- 5th in this race. So this eliminates d1, e1 and d2,d3,e2,e3 from the race.

Now we need to race a2,a3,b1,b2,c1 - last race. Here the top two horses would be second and third respectively.

So 7 races will do.

@pp how do you know a2, a3 are not faster then b1, c1,d1,e1...

and same case with b2,b3,c2...

Ans: 6 Races

Explanation: Let horses be numbered 1 to 25

R1: Race among horses 1 to 5. Note the relative speeds.

R2: Race any one of 1 to 5 with 6 to 9. You get relative speeds of 1 to 9.

R3: Race any one of 1 to 9 with 10 to 13. You get relative speeds of 1 to 13.

R4: Race any one of 1 to 13 with 14 to 17. You get relative speeds of 1 to 17.

R5: Race any one of 1 to 17 with 18 to 21. You get relative speeds of 1 to 21.

R6: Race any one of 1 to 21 with 21 to 25. You get relative speeds of 1 to 25.

With the relative speeds you can find out not just top 3 but top 25. :)

This is a partition sort problem. You won't be able to know the relative speeds of 1 to 9 after R2, because you don't have a stopwatch, and the only information you obtain after each race is the inequality chain.

In your R2, for example you pick #1 in R1, even if #1 tops in R2, it could be #1<#6<#7<#8<#9<#2<#3<#4<#5, it also could be #1<#6<#7<#2<#8<#3<#9<#4<#5

Step 1. Divide the lot into 5 groups such that each group contains 5 horses. Conduct a race of each group.

Total races = 5

Step 2. Conduct race between the topmost horses in each group. The winner in this race eliminates all other 24 horses. He is the fastest. Now we need 2nd and 3rd.

Total races = 5+1 = 6

Step 3. Take the horse who got second from the group that the fastest horse belonged to. Conduct a race between it and rest four from step 2. The firsr and second in this race are the second and third fastest horses.

Total races = 5+1+1 = 7

I have tried this problem and solved it using following code. There is room for improvement but for me this code worked perfectly :

1. RacingGame.java

```
package game;
import gamingObject.Horse;
import gamingObject.Race;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.concurrent.Executor;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
public class RacingGame {
/**
* @param args
*/
public static Map<Integer, List<String>> raceToWinners = new HashMap<Integer, List<String>>();
public static int currentRace = 1;
public static boolean trackComplete = false;
private static boolean newTrackBegin;
private static boolean flag = true;
private static boolean race6Begin = false;
private static boolean race7Begin = false;
private static Object mutex = new Object();
private int frstHorseInNextRace = 0;
public static void main(String[] args) throws InterruptedException {
ExecutorService exeService = Executors.newFixedThreadPool(5);
/*
* Logic to conduct first 5 races (total horses/total track) so here
* total horses = 25 and tracks = 5 hence initial and compolsuary races
*/
RacingGame rg = new RacingGame();
for (int race = 1; race <= 5; race++) {
trackComplete = false;
currentRace = race;
while (!trackComplete) {
rg.startTrack();
}
}
/*
* Before 6th Race lets have right candidate for 6th race
*/
List<String> horseNames = chooseHorsesForRace6();
/*
* Race among 5 tops horses from 5 races
*/
currentRace++;
synchronized (mutex) {
while (!race6Begin) {
race(horseNames);
}
}
/*
* Choose candidates for last race 7
*/
horseNames = chooseHorsesForRace7();
currentRace++;
synchronized (mutex) {
while (!race7Begin) {
race(horseNames);
}
}
printResults();
System.exit(0);
}
private static void printResults() {
// TODO Auto-generated method stub
Iterator<Integer> iter = raceToWinners.keySet().iterator();
while (iter.hasNext()) {
int raceNum = iter.next();
StringBuffer sb = new StringBuffer();
System.out.println("Race" + raceNum + " : ");
List<String> horses = raceToWinners.get(raceNum);
for (int i = 0; i < 3; i++) {
sb.append(horses.get(i));
if (i < 2)
sb.append(",");
}
System.out.print(sb.toString());
System.out.println();
}
}
private static List<String> chooseHorsesForRace7() {
/*
* Adding First horse at first rank among 25 horses
*/
List<String> winners = new ArrayList<String>();
winners.add(raceToWinners.get(6).get(0));
raceToWinners.put(7, winners);
/*
* Taking first horses from races 2 and 3
*/
List<String> finalTrackHorses = new ArrayList<String>();
finalTrackHorses.add(raceToWinners.get(6).get(1));// firstHorse
finalTrackHorses.add(raceToWinners.get(6).get(2));// secondHorse
/*
* Rejecting all horses from race track whose first horses are at 4th
* and 5th rank of race 6
*/
for (int i = 1; i <= 5; i++) {
if (raceToWinners.get(i).contains(winners.get(0))) {
finalTrackHorses.add(raceToWinners.get(i).get(1));// thirdHorse
finalTrackHorses.add(raceToWinners.get(i).get(2));// forth horse
} else if (raceToWinners.get(i).contains(finalTrackHorses.get(1))) {
finalTrackHorses.add(raceToWinners.get(i).get(1));// fifth horse
}
}
return finalTrackHorses;
}
private static void race(List<String> horseNames) throws InterruptedException {
if (currentRace == 6)
race6Begin = true;
else
race7Begin = true;
newTrackBegin = true;
flag = true;
trackComplete = false;
while (flag) {
if (!trackComplete) {
/*
* Create thread for each horse
*
* Here taking slot of 5 horses and keep them running in a
* single loop.
*/
if (newTrackBegin) {
List<String> horses = Arrays.asList(horseNames.get(0),
horseNames.get(1), horseNames.get(2),
horseNames.get(3), horseNames.get(4));
Race r = new Race(horses);
r.start();
}
newTrackBegin = false;
mutex.wait(1);
} else if (trackComplete) {
mutex.notify();
flag = false;
}
}
}
private static List<String> chooseHorsesForRace6() {
List<String> lstHorses = new ArrayList<String>();
for (int i = 1; i <= 5; i++) {
/*
* Take only 1st Position Holders of first 5 races
*/
lstHorses.add(raceToWinners.get(i).get(0));
}
return lstHorses;
}
public Map<Integer, List<String>> getRaceToWinners() {
return raceToWinners;
}
public static synchronized void addTrackWinnerInList(String horseName) {
List<String> horses = raceToWinners.get(currentRace);
if (horses == null) {
List<String> raceHorses = new ArrayList<String>();
raceHorses.add(horseName);
raceToWinners.put(currentRace, raceHorses);
} else {
horses.add(horseName);
raceToWinners.put(currentRace, horses);
}
if (raceToWinners.get(currentRace) != null
&& raceToWinners.get(currentRace).size() == 5) {
trackComplete = true;
}
}
public static boolean isTrackComplete(){
return trackComplete;
}
public void startTrack() throws InterruptedException {
// TODO Auto-generated method stub
synchronized (mutex) {
flag = true;
newTrackBegin = true;
trackComplete = false;
while (!trackComplete) {
/*
* Create thread for each horse
*
* Here taking slot of 5 horses and keep them running in a
* single loop.
*/
if (newTrackBegin) {
List<String> horses = Arrays.asList("Horse"
+ (++frstHorseInNextRace), "Horse"
+ (++frstHorseInNextRace), "Horse"
+ (++frstHorseInNextRace), "Horse"
+ (++frstHorseInNextRace), "Horse"
+ (++frstHorseInNextRace));
Race r = new Race(horses);
r.start();
}
newTrackBegin = false;
}
}
}
}
```

2. Horse.java

```
package gamingObject;
import game.RacingGame;
public class Horse extends Thread{
String horseName;
public Horse(String horseName){
this.horseName = horseName;
}
@Override
public void run() {
for (int i = 0; i < 5; i++) {
try {
sleep(1);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
RacingGame.addTrackWinnerInList(this.horseName);
}
}
```

3. Race.java

```
package gamingObject;
import game.RacingGame;
import java.util.List;
public class Race extends Thread {
List<String> horses;
private boolean flag = true;
private Object obj = new Object();
public Race(List<String> horses) {
this.horses = horses;
}
public void startRace() {
synchronized (obj) {
run();
}
}
@Override
public void run() {
synchronized (obj) {
boolean newTrackBegin = true;
while (!RacingGame.isTrackComplete()) {
/*
* Create thread for each horse
*
* Here taking slot of 5 horses and keep them running in a
* single loop.
*/
if (newTrackBegin) {
Horse h1 = new Horse(horses.get(0));
Horse h2 = new Horse(horses.get(1));
Horse h3 = new Horse(horses.get(2));
Horse h4 = new Horse(horses.get(3));
Horse h5 = new Horse(horses.get(4));
Thread t1 = new Thread(h1);
Thread t2 = new Thread(h2);
Thread t3 = new Thread(h3);
Thread t4 = new Thread(h4);
Thread t5 = new Thread(h5);
t1.start();
t2.start();
t3.start();
t4.start();
t5.start();
newTrackBegin = false;
}else{
if(!RacingGame.isTrackComplete()){
try {
obj.wait(10);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}else{
obj.notify();
}
}
}
}
}
}
```

first race consists of 5 horses, from that one will be selected.

and the second race will be the same as the first. Follows the third, fourth and the fifth.

Now among 25, 5 horses will be selected from each race.

Now conduct another race with this selected horses amongst the 5, the horse which comes will be the winner.

So 5+1= 6 races will be sufficient.

I think we need 11 races to find the top3 fastest horses.. Here is my approach

R1 : First 5 (Untested 20 )

R2 : best 3 From R1 Plus 2 from Untested (Untested 18)

R3 : best 3 From R2 Plus 2 from Untested (Untested 16)

.....

R10 best 3 from R9 Plus 2 from Untested (Untested 2)

R11 best 3 from R10 plus 2 from untested ( untested 0 )

I think any grouping to 5 team approach may not find the fastest since the worst horse in first team could possibily run faster than the best horse from the next team .. Anyone agree?

@anbu

Worst horse in the first team can run faster than best horse's of all the other team but that worst horse is already out of picture because he is already at the 5th position and we are looking for top 3 :)

@ramesh

You did not answer anbu. Why is he out of the picture? In terms of fastest, it is quite possible for the slowest of one heat to be faster than the winner of another heat. So to assume that scenario is impossible just means that the people who wrote this problem never ran track.

I cannot find support for my claim but would love to be told why my logic is wrong.

From a perspective this is a sorting problem and whose solution is nlogn

5log5 = 7 or 8, it depends on the input order. correct me if wrong. Thanks

My answer

Initial 5 Races

Take winner from each race and put in one race (FASTEST IDENTIFIED) 1 Race

Only need to identify second and third fastest now. Take 2 fastest from other 4 races and next two fastest from the winners race 10 horses = 2 Races

Take winner and runner up from the 2 races put them in 1 Race

First and second in that race are second and third in overall

Total: 9 Races

Remember we only need to identify 3 horses to start with, and after the winners race we only need to identify 2. Thus, after identifying the fastest, 2 from each race is enough to identify the remaining 2 horses.

Never mind,

This is better

5 races to identify fastest from each group of 5

1 race to identify fastest of the fastest

2 races made up of 2nd and 3rd place in winners race + 2nd place from their groups + 2nd and 3rd place from the first round winners group

1 race made up of 1st and 2nd from each of those races

Total 8 races to be certain

After the overall winner is identified 2 are needed from each of the original 5 groups that had a top 3 position in the winners race to be sure you have the 2 fastest.

Total 12 races.

1. pick 3 out from each group - so 5 races ,now horse left are 15

2. pick again 3 out from each group - 3 races , now horse left are 9

3. pick again 3 out of each group - 2 races(1 race for 5 horse,1 race for 4 horse) , now horse left are 6

5. pick again 3 out of 5 horses - 1 race , horse left are 4

6. Pick 3 out of 4 horses - 1 race ,

So total races are: 5+3+2+1+1 = 12

answer :7 races

- lyzoridc on March 12, 2010 Edit | Flag Replyreason details:

1. we have 5 races for 25 horses that 5 horses on a team, define each team as a, b, c, d, e.

2. carry a best horse race for each team first place, define them as a.1,b.1,c.1,d.1,e.1

3. assume prior best horse race 's top 3 places are a.1 b.1 c.1 , so we know the fastest horse is a.1, we only need to take last race to know who are second and third quickest horse. The horses that participate in this race are b.1 b.2 a.2 a.3 c.1 , this race 's top 2 places are 2nd and 3rd quickest horses