Google Coding Interview Question

There are 25 mechanical horses and a single racetrack. Each horse completes the track in a pre-programmed time, and the horses all have different finishing times, unknown to you. You can race 5 horses at a time. After a race is over, you get a printout with the order the horses finished, but not the finishing times of the horses. What is the minimum number of races you need to identify the fastest 3 horses?

11 I think. You race 5 horses first, then replace the two slowest horses with new ones each time, repeat for (25-5)/2=10 times.

I'm gonna give you a hint. You have 5 unsorted lists, and you have to sort them into one single list. You take the first 5 elements(1 from each list) and you put them into a min-heap. Pop the minimum, take another one. Do it until the heap is empty. Figure it out, faggot. It's easy. Oh, and the BIG-4 don't ask these kind of questions anymore, get with the times.

Fuck it, I'll give you the answer. 7 races. Now, this answer is useless if you didn't solve it yourself. You are supposed to solve these questions without any help, because you won't' get any during the interview, and believe me, if the interviewer is an engineer from Microsoft or Google, he is going to spot your bullshit instantly. They know what you're going to write on the whiteboard before you do.

you can do it in 8 races
5 races to find the 5 fastest horses in each 5 horse group, 6 to find the fastest horse (remove this horse, and take the next fastest from its group), 7 to find the second fastest horse (remove this horse, take the next fastest from its group) and 8 to find the 3rd fastest horse.

Got it in 7:
- race 5 sets of 5 horses (initial races)
- race 5 winners against each other (winner's race)
- fastest in that race is the 1st fastest
- 2nd fastest is either second in winner's race, or the second in the 1st fastest's race
- 3rd fastest is either the third in the winner's race, second or third in the 1st fastest's race, or second in the second place of winner's race
- so, there are 5 candidates for the last race, of which the top two are the 2nd and 3rd fastest
- second in winner's race
- third in winner's race
- second in 1st fastest's initial race
- third in 1st fastest's intial race
- second in second winner's initial race

no, wait, you can do it faster than that
after the 6th race, you have some good candidates for the fastest horses
the fastest horse in race 6 is definitely the fastest horse, but, the second and third horses in race 6 may not be the second and third fastest overall. Their only competition is the 5 horse group that the fastest horse belonged to. You can take the second and third fastest horses from race 6, and the second and third fastest horses from the group containing the fastest horse, and race them (in race 7). The result is guaranteed to give you the second and third fastest horses.

how about this
race each of the 25 horses once each in a separate race, that's 5 races

discard the bottom two horses from each race, so there are 15 horses remaining

take the a set of three horses (A) and add the top horse from two other sets (B and C) then do your method
if the top horses from B and C are bottom two you don't need to race any of the other horses from their sets

best case 7 races to find top 3
worst case 11

welp that was wrong

PAJEET CONFIRMED

>race each of the 25 horses once each in a separate race, that's 5 races
i'm laughing so hard thanls

is right

so close, forgot about 2nd horse from 2nd place's group

race 7 needs to contain
horses 2 and 3 from race 6
horses 2 and 3 from race 6 winning horse's initial group
horse 2 from race 6 2nd place horse's initial group

since the horse groups might have finishing times like this
a 1 4 8 ...
b 2 3 ...
c 5 ...
d 6 ...
e 7 ...

that's racist T_T

Wouldn't the horses naturally slow down after each consecutive race due to exhaustion? The winning horse could have a much slower time by it's third race than the horse in last place from the first race.

Correct?

Can't you do it in 6 races?

That was a stream of consciousness type post, so here's hopefully a better/clearer explanation:
- Race five sets of five horses, call them races A, B, C, D, and E.
- Race the winners of races A-E, call this race F.
- Let's say the top three of race F in order are from groups A, B, and C, call those winning horses A1, B1, and C1.
- The winner of race F is the fastest overall.
- B1 might be second fastest overall, but A2 (second behind A1 in race A) might also be
- C1 might be 3rd fastest overall, but it could be A3 or B2 (or it could be the loser between B1 and A2)
- So, we end up with 5 candidates for second and third fastest overall: A2, A3, B1, B2, and C1
- The first and second of the race between those 5 (call it race G) are our second and third fastest overall

they are mechanical horses
read the question
fucker

>mechanical
>pre-programmed time

if you can do it, i'd be interested in seeing your explanation

Never mind. Since there is no time given we can't compare the way I was comparing them.

How are these mechanical horses fueled?

if the time is given as an output of the race it takes 5 races

wind

Nine races.

5 races horizontally
5 races vertically
How will this work?

you only need one race to identify the most genetically fit horse, and that's the master race
>needing 7 races
>untermensch confirmed

they're racing on a racetrack so we only need to worry about their horizontal time

so the 7th race consists of the 4 horses from race F and the 2nd place winner of the group of the winning horse?

bait

The 7th race (G) consists of the second and third place from the 6th race (F), plus two of the horses that lost to race F winner in race A, and one of the horses that lost to race F runner-up in race B.

You know what I mean you smug fuck

I honestly have no idea

Create a matrix of 5 x 5 to compare horizontally and vertically