Citrix Online Interview Question for Software Engineer in Tests






Comment hidden because of low score. Click to expand.
9
of 11 vote

answer :7 races

reason 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

- lyzoridc March 12, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice

- Anonymous March 12, 2010 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

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

- Tarun Phaugat March 12, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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 March 13, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- lyzoridc March 13, 2010 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Amar December 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 .

- Amar December 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- prashant gupta August 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
6
of 6 vote

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.

- Axl August 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

oops. 7 races. 5 horses track.
round 1 to 5:
h11, h12
..
h51, h52

round 6:
start: h11, h21, ... h51
result: h61, h62, h63, ...

round 7:
h61's previous race before race 6, the number 2 and 3 horse,
h62
h62's previous race before race 6, the number 2
h63
out: h61, h71, h72 the result.

- Anonymous March 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- b March 14, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Scmoo December 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If the fastest of one group beats fastest of other group then he beats rest all in that group.

- IntelsCreed December 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

hmm.. 5-ary tournament?

- Zaphod March 22, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- jj April 02, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous April 19, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 April 20, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

PP is absolutely right!!!

- Anonymous July 02, 2010 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

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

- ravi September 10, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ohh yeah @pp is right

- ravi September 10, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

why can we choose all 5 in next round and choose the fastest...assuming they consistently do perform...otherwise any way we can not find...

- uno March 12, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

faint. one race, and everybody in the same race track, the fastest 3 are the answer.

- Anonymous March 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't think you read the question. 5 HORSE TRACK, NOT 25 HORSE TRACK.

- um no October 06, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

7 races !! thats correct

- Anonymous March 23, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- clrs March 24, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what happens if one pair of horse runs at 40m/h, 0 m/h and other pair runs at 50m/h, 60m/h. so when they meet, first one will have more distance on its name.

- Anonymous May 11, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

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. :)

- Vasant February 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- yurongzhen December 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Amar December 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Infact the last race is between just 2 horses.

- amar December 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution is not quite correct if the three fastest horses are in the same group, step 3 is not the way how to find the third fastest

- Tung January 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
						}
							
					}
					
			}

		}
	}

}

- Kailash Dalmia July 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Vivek August 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

First divided the 25 horse in to 5 groups randomly and then keep a race to all the 5 groups and then pick the first horse from all the groups and then keep a one more race to determine 1, 2 and 3 places.

So total 5+1 = 6 races are needed

- Pavan Hitesh August 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Answer- 7 Races

Give names H1....H25
Divide into 5 groups as 5 can run at a time

H1, H6 , H11, H16, H21 are fastest in there groups

Now we can remove last two from each groups as we need fastest 3 now we left with 15 horses

6th Race- between all fastest in groups

After 6th Race

H1> H6 > H11> H16,>H21

Now H21 was fastest in group but is 5th in 6th race so H22 and H23 who already slower than H21 can't be in first 3

Same thing applied for H17 and H18 as H16 was fastest in group race but 4th in 6th race

Same applied for H12 and H13 as H11 was fastest in group race but 3th in 6th race

Already three horses are faster than H16 and H21 so they both also can be rules out

Now we left with H1, H2, H3,H6, H7, H8 and H11

But H8 is slower than H7 and H7 is slower than H6 in group race and we have H1 on top already so H8 also can't be in fastest 3

Now we left with H1, H2, H3,H6, H7, H11

H1 we know is fastest..so lets 7th race between H2, H3, H6, H7 and H11 and find the other two

After 7th race you will get fastest 3

- Ashish Gupta May 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution:

Step 1: First, we group the horses into groups of 5 and race each group in the race course. This gives us 5 races.



W11   W12   W13   W14   W15

W21   W22   W23   W24   W25

W31   W32   W33   W34   W35

W41   W42   W43   W44   W45

W51   W52   W53   W54   W55


Step 2:we race the 5 level 1 winners(w11,w21,w31,w41,w51) ans assume winning order of this race is w11,w21,w31,w41,w51

Step 3: BECAUSE WE NEED TOP 3 AND W41 HAS COME 4TH Position that is the reason we don't need to consider W41   W42   W43   W44   W45 and also W51   W52   W53   W54   W55
now we have


W11   W12   W13   W14   W15

W21   W22   W23   W24   W25

W31   W32   W33   W34   W35


Step 4: because we need top 3 then dont need W14   W15   W24   W25   W34   W35

now we have

W11   W12   W13   

W21   W22   W23   

W31   W32   W33


Step 5: because in 6th race W31 has come on 3rd position that is the reason we do not need to consider W32,W33 and also we will not consider W23
now we have

W11   W12   W13   

W21   W22  

W31

Step 6:  top 1 is already achieved which is W11(winner of 6th race)
remaining are 

 W12   W13   

W21   W22  

W31

Step 7: now race W12 w13 w21 w22 w31 to get 2nd and 3rd winner



Hence answer is 7 races.

25 horses 5 tracks 5 fastest horses puzzle | Google Interview Question
http://codinginterviewquestionsans.blogspot.in/2017/07/25-horses-5-tracks-5-fastest-horses.html

- rahulpatel11315 July 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

7 races
It is like the linear selection problem using median of medians concept.
5 races to sort the horses in each group
6th race between the winner of each group and sort rearrange the 2D grid based on this sorting.
Now we know the fastest horse. We can ignore the first 2 groups and 1st 4 horses of group 3.
We can select max 1 from group 3, max 2 from group 4 and max 3 from group 5. We don't need to consider max of group 5 because it is already the fastest. We just need to find out the next 2 fastest ones.
So winner of group 3, winner and runner up of group 4 and 1st runner-up and 2nd runner-up of group 5 would participate in the 7th race. The top 2 horses would join the max/fastest horse of group 5 as the 3 fastest horses.

- PJ May 06, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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 April 23, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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 October 18, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- jzzawop March 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes acc. to me also 11 races . due to this every horse can compete with top 3 racers.

- Prashantgupta7419 August 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- chennavarri November 09, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

why are you taking n=5 if there are 25 horses

- KM July 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- Jason June 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Jason June 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

That should still have read 9 races

- Jason June 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Anonymous September 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your approach can find the correct top 3 but is not the optimal one, because you didn't fully utilize the inequality information out of the first 5 races.

- yurongzhen December 20, 2012 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More