Math / Logic Interview Question

This is an interview question asked to potential programmers or sales analyzers for major tech firms. No cheating and back your answer up.

I'm also going to wait a while to tell people if they are right or wrong.

 

Alright. If I can race them five at a time, it only takes five times for all of the squirrels to race. I take the fastest squirrel out of every group, then I would have five left. I race them, take the fastest three out. Going by this method, it's six times?

Another method is after you take the fastest squirrel out of each group. Race them, take the fastest one out each time. Going by this method, it would take eight times.

 

What if group A's whole group is faster then group B?

 

5 races, take the 3 fastest from each. 15 squirrels now. 3 more races, take 3 fastest from each. 9 squirrels now. 2 more races, take 3 fastest from each. 6 squirrels now. 2 more races, and you can find the three fastest.

12 races overall.

That's probably not the best answer.

No, because what one group if the first group has the three fastest squirrels?

 

You have 25 race squirrels. You can race them 5 at a time. You do not have any timing device. All will race to their fullest potential every race. You want to figure out the fastest 3 squirrels. What is the minimum number of races you must run in order to figure out the three fastest?

Heres how I'd work it out.

5 races of 5 squirrels = 25 Race Squirrels.
No timing device, therefore First 3 squirrels move on to the next set of races.

15 Are left.
3 races are done, and the first 3 of all these races are taken to the next phase.
9 are left, 8 races done so far.

(Now I realize it's harder than I thought)
2 more races are conducted, the top 3 are taken to the next race.
6 are left, 10 races done so far.

Assuming ALL squirrels run to their fullest potential ever race, and this variable is not changed.

5 are chosen to run a race, and the top 3 get to stay.
The last squirrel will also run a race, to ensure he does not get a bye (This is optional, but to maintain the best degree of fairness, essential)

4 are left, 12 races done so far.

The top 3 stay.

Result:

3 are left, 13 races are done in total. (12 are done if you decided to give the squirrel a bye.)

 

Oh, dang! You have the point there. My money is on Malakadang now.

 

I wouldn't put my money on it.

 

I stand by my answer, unless you don't run 5x5 initially, however if thats the case then I'm too lazy to work that out =,=

 

I think this is what wulfspade said.

I would split the 25 squirrels into 5 groups, containing 5 each.

Take the #1 squirrel from each group. That will take 5 races.
Put the 5 #1 squirrels into the same race. Take the top 3 and there you have your top 3 fastest squirrels. It takes a total of 6 races. Pretty much the same as in track meets.

 

The problem is, what if you have the actually 3 fastest squirrels all in one race?
So you knock the 2nd and 3rd fastest out, leaving only the 1st.

 

First I thought 6, now I'm going with 12 what two people I think have said so far.

I'm trying to think of a way where there will be less but I'm not seeing it.

EDIT: The answer is actually 11 I think. Whenever you have a race with the 5 people, you kick out the bottom two. So with 11 races, you kick out 22 squirrels leaving you with the top 3. To save that race whenever there are squirrels left that aren't in multiples of 5, don't race them without 5. Let 5 race, take the top 3 and race them again with 2 that haven't. If this is repeated, 2 will keep dropping out till 1 last race of 5.

 

You still do the 5x5 first.

 

O, now I got it.

25 Squirrels - 0 races
15 Squirrels - 5 races
9 Squirrels - 8 races
7 Squirrels - 9 races
5 Squirrels - 10 races
3 Squirrels - 11 races.

What koot said xD.

 

I'm gunna go out on a limb here and go with 53,130 races. Its probably wrong but heres what I did:
C(25,5)=53130

 

You can get farther than that. It took me awhile to figure that out though.

Your over mathifiying it.

 

Would take 7 races. (trying to pretty up / make sure my explanation is clear.) My original answer was 8, but looking over my work I was able to get it down to 7.

I've given every squirrel a name based on their original groups / place.

Once a squirrel has been beaten by at least 3 other squirrels, it is unable to place in the top 3, so it is useless to continue racing them

a1 a2 a3 a4 a5 - race one
b1 b2 b3 b4 b5 - race two
c1 c2 c3 c4 c5 - race three
d1 d2 d3 d4 d5 - race four
e1 e2 e3 e4 e5 - race five

Every squirrel that didn't place in the top 3 is unable to win because they were beaten by atleast 3 squirrels.​

Race every squirrel that placed first in their orignal group.

a1 b1 c1 d1 e1 - race six.

The winner of this group is the fastest (a1), and it is now pointless to race him.

All squirrels in the d and e groups are now unable to win because they've all been beaten by at least 3 squirrels

At best, c1 can be the third fastest squirrel because it's been between by two squirrels, meaning every c squirrel besides c1 is unable to win.

At best b1 can place second, meaning b2 can still come in third, making b3 unable to win.

Both a2 and a3 can still place in the top 3, since they've only been beaten by a1

​

This leaves us with only 5 possible squirrels that can fill the second and third place slots

b1 a2 c1 a3 b2 - race seven

The top two in this race are the second and third fastest (b1, a2)​

Can explain more if needed. Think I've got it right tho. If you don't want to post whether I've got it correct or not please pm me.

 

8 races, not going to bother explaining myself unless I'm right.

 

Thats right!

 

Take all the squirrels and make a yummeh stew?