Citrix Online Interview Question
Software Engineer in TestsTotal 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.
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.
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...
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?
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.
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
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
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.
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 March 12, 2010reason 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