Google Coding Interview Question

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

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

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

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

>>61665935
>>61666313
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

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

>>61666146
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

>>61666776
welp that was wrong

>>61666933
PAJEET CONFIRMED

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

>>61666496
is right

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

>>61666997
>>61667066
that's racist T_T

File: woah.jpg (66KB, 640x640px) Image search: [Google]

66KB, 640x640px

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?

>>61666496
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

>>61667137
they are mechanical horses
read the question
fucker

File: good_job_horse_ribbon.jpg (34KB, 500x581px) Image search: [Google]

34KB, 500x581px

>>61667137
>mechanical
>pre-programmed time

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

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

How are these mechanical horses fueled?

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

>>61667191
wind

Nine races.

>>61667211
5 races horizontally
5 races vertically
How will this work?

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

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

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

>>61667339
bait

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

>>61667299
You know what I mean you smug fuck

>>61667482
I honestly have no idea

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