Google Interview Question Software Engineer / Developers
@ wenlei.zhouwl: "The cars in the right and bottom of the center car should run faster than the center car. They can not be the 25th car."
This claim is not correct.
Take A[3][4] for example. Based on the above claim, A[3][4] cannot be the 25th car. In fact, it can.
What we can say for sure is that there are 11 cars slower that A[3][4] and 19 cars faster than it. The 11 cars include A[i][[j] where 1 <= i <= 2 and 1 <= j <= 4 and A[3][1], A[3][2], A[3][3]. The 19 cars are A[i][j] where 4 <= i <= 7 and 4 <= j <= 7 and A[3][5], A[3][6], A[3][7]. The rest of the 18 cars can be faster or slower than A[3][4]. If 13 out of the 18 cars are slower and 5 are faster than A[3][4], then A[3][4] is the 25th car.
After step 1 and 2, we can exclude 12 cars from being the 25th car. They are A[1][1], A[1][2], A[1][3],A[1][4], A[2][1], A[2][2], A[6][6], A[6][7], A[7][4], A[7][5], A[7][6], and A[7][7].
In any case, I tend to agree with remi.carton on October 15, 2010. The question asks for a number, not an algorithm. However, that makes the problem a lot less challenging.
We are looking for 'at least how many'. So we do not need an efficient algorithm, we just want an algorithm that in the best case, finds the 25th with the minimum effort.
So first race we find the median car, it's the 4th car. If we assume it's the 25th car, we only have to prove it's the 25th now.
We test it against the 42 remain cars, so
7* (6cars + our median).
Now assuming that for every single race it is the 4th car, we proved that there were 24 cars going faster (8*3 = 24), and 24 slower cars. As it was the median each time, we are sure that all the car going faster for one particular race are faster than the cars going slower for all the other races.
So that's 8 races to test our candidate versus all other cars.
Note that using this technique as an algorithm to find the 25th car would be just terrible (8*48 races or so).
Hence, at least 8 races, but note that I _did not prove_ that there were no better solution so far. I think you can prove it by saying that you need to test each car at least once, so 7*7, and you need a pivot of some sort to compare the cars between races, so at least 1 other race, so minimum number of races is 8, and we found one that works with 8 races in the best case, there is no better algorithm since the minimum is 8.
i agree with remi.carton. although i feel the question is a little unclear about whether it asks for just a number or an algorithm, i incline to think it asks just for a number. so 8 is correct.
I like this solution. Actually, we are just looking for the very median number among those 49 numbers.
Wrong answer. You have to answer without assumption the minimum race so you can make sure you get 25th fastest.
Otherwise according I can find this way by assumption as, 1st race I pick out 7th one, then same as you race 7*(6cars+7th one). say 2nd 3rd 4th race 7th place, 5th 6th 7th 8th race 1st place. so we have 6+6+6+6 cars ahead & 6+6+6+6 behind, but it is all assumption which is not what the google is looking
I think we just need to view the problem differently. To find the 25th fastest car in 49 cars is essentially a median-searching problem. Utilizing the method to find median in a sorted matrix (iirc someone posted a few days ago), I think it will take 7+7+1=15 races.
Imagine a 7 x 7 matrix, each with a different number representing the speed of a particular race car. It will take 7 races to sort them row-by-row (reposition the cars from slowest to fastest, say). Use the current matrix to start 7 more races, this time column-by-column, sort/reposition the cars again based on the results. Then it becomes clear that the median must lie on the diagonal from lower-left to upper-right, hence 1 more race is needed to find the median.
sorting by row doesn't mean it is sorted in order of speed. There is no relative ordering b/w row. I like your approach though.
By sorting by row I meant, race once and reposition the cars (in the matrix) based on their ranking. Maybe I should use a concrete example to explain better:
Suppose you have 9 cars, 3 tracks, and we want to find out the 5th fastest car (the median), considering such random matrix:
9 8 5
7 2 6
3 1 4
We first race the cars row-by-row (so 1st round 9 8 5, 2nd round 7 2 6 and 3rd round 3 1 4), after sorting/repositioning we have
5 8 9
2 6 7
1 3 4
Now we race the cars column-by-column (1st round 5 2 1, 2nd round 8 6 3 and 3rd round 9 7 4), sort/reposition the cars again we get
1 3 4
2 6 7
5 8 9
To get the 5th fastest car, we simply race one more time the cars lie on the minor diagonal and see which car comes in the middle. All I did was 3 + 3 + 1 = 7 races.
This can be generalized to the case with 49 cars, 7 tracks and looking to find 25th fastest car.
How is 7*7 different from 3*3 in principal? I chose 3*3 to explain the solution so it I don't have to write too many numbers.
@airfang613: wuht is correct... your claim that median will always come on the principal diagonal is correct only for 3*3 matrix and will fail even for 4*4 matrix, forget about 7*7. for ex consider the following matrix where elements in both columns and rows are in sorted order but both upper and lower medians(8 & 9) do not lie on principle diagonal.
1 2 9 10
3 4 11 12
5 6 13 14
7 9 15 16
I am able to find the 25th car in 18 races but don't know whether is it possible using lower races?
answer should be 8 in best case.
all the answers seem to involve finding local max .. for all you know, one of the top seven could be bottom 7, or it could be the 25th fastest... (since the car just have to be faster than any 6 to win)..or you cant take the median either... because it doesnt give any global information... in fact any algorithm that depends on doing something with local information won't work.
only sure way is to race each car against all 48. so if we are lucky, 8 race will suffice (one car can race 6 cars, need to do 8 times). But otherwise, if the car is faster than more than 24 cars, then we can eliminate and proceed with finiding car that only beats 24 cars, otherwise, we can find a car that beats 24-1 cars ... and vice versa.
so worst case, we'll need to race (races*car)= (8*6)-(7*6)+(6*6)+(5*6)+(4*6)+(3*6)+(2*6)+(1*6)=132 times...
may not be optimal solution, but this is best i can think of.
18 races at most. Here is the solution:
First after 7 races we have
A1 A2 A3 A4 A5 A6 A7
B1 B2 B3 B4 B5 B6 B7
C1 C2 C3 C4 C5 C6 C7
D1 D2 D3 D4 D5 D6 D7
E1 E2 E3 E4 E5 E6 E7
F1 F2 F3 F4 F5 F6 F7
G1 G2 G3 G4 G5 G6 G7
Then we race A4,B4,C4,D4,E4,F4,G4 to find the 4th fastest. Assume D4 is the 4th fastest in this race. Then we know A1 A2 A3 A4, B1 B2 B3 B4, C1 C2 C3 C4, D1 D2 D3 are faster than D4, which are 15 cars in total. That's to say we get 15 out of top 25 cars already! Now we have
A5 A6 A7
B5 B6 B7
C5 C6 C7
D4 D5 D6 D7
E1 E2 E3 E4 E5 E6 E7
F1 F2 F3 F4 F5 F6 F7
G1 G2 G3 G4 G5 G6 G7
Then we use bin sort to find the 10th fastest car in these 34 cars which only need 10 races. So the total races are 7+1+10=18 at most.
I am still trying to find a better solution.
You are wrong. Let's say D4 is the 28th fastest car and D3 is the 25th. You will never get the right car.
Correct approach..but answer will be 7+1+3+1=12
This problem is same as finding median in row and column sorted matrix.
10 times.
1. Divid 49 cars in 7 group. choose the 4th car in each group.
2. Race all 7 4th cars from each group, choose up the 4th again.
3. Divide the other 6 groups into 3 slower groups, and 3 faster groups by step 2.
4. Pick 3rd car from slower groups, and 5th car from faster groups.
5. Repeat this as step 2 3 times. The 4th one will the final result.
I don't quite understand step 3, 4 and 5, could you explain what exactly are 3 slower groups and 3 faster groups and how do you pick 3rds and 5ths then repeat step 2? Thanks!
Say if using the matrix described by the other guy:
A1 A2 A3 A4 A5 A6 A7
B1 B2 B3 B4 B5 B6 B7
C1 C2 C3 C4 C5 C6 C7
D1 D2 D3 D4 D5 D6 D7
E1 E2 E3 E4 E5 E6 E7
F1 F2 F3 F4 F5 F6 F7
G1 G2 G3 G4 G5 G6 G7
9 is definite answer.
7 runs first
8th run to run median.
the 9th run is primary diagonal.
my answer is 12.
for the first 7 times, we run cars in 7 groups to get the fastest 7 cars in each group.
since we already have 7 groups of sorted cars, we then can do something like a merge sort from these 7 groups of sorted cars:
for the 8th time, we run those fastest 7 cars in each at the same time to get the slowest one out of them, the other 6 cars should belong to the group of fastest 25.
for the 9th time, we run the slowest car from the last round with another 6 cars in the other 6 groups, still find the slowest one in this round, dump the other 6 cars again,
for the 10th and 11th times, we repeat this pattern again,
since every round we can find 6 fastest cars in the race, after 4 rounds, we already have 24 fastest cars. for the next race, the fastest car will be the 25th fastest one out of 49. so the total rounds is 7+4+1=12.
what do you think?
I dont think this is correct. You say for the 8th race, run the top cars from the prev 7 races and eliminate the first 6 thinking they will be in top 25. Assume A1...G1 won in this order. Now, all we know is that A1>B1>C1...>G1. There can be a possibility than all cars from A1..A7 to E1..E7 are faster than F1. Then how will F1 be still in the top 25? In this case it will be 36th.
if we keep 1 car aside and make 24 races between 2-2 cars, then after 24 races we will get such 24 cars which are in a group definitely faster than the other 24 cars. So after these 24 races, we are sure the 25th fastest is present in wither the slower 24 cars or the left out 1.
Similarly now, make 12 diff 2-2 races between 24 slower cars and we will get 12 such faster group and 12 slower group. Now again race in 12 faster group and will get faster 6 and hence again 2-2 race and faster 3.
Now race faster 3 and left out 1 in a 2-2 fashion which will lead to in total -
24 + 12 + 6 + 3 + 2 + 1 = 48 races
is it correct?
it needs 8 races.
divide the 49 cars into 7 group. do 7 races. from the result of each race select the 4th fastest car. This gives us 7 4th fastest cars. for these cars we know the following holds:
21 cars < (4ths) < 21 cars
(< == faster)
to find the 25 fastest car we just need to run a race between the 4th places. Then we pick the 4th of that group. It is the 25th fastest car:
21 cars < 7th, 6th, 5th, 4th, 3rd, 2nd, 1st < 21 cars
The best answer I have seen is 32:
7 races to sort seven groups of seven cars.
+
1 race between the fastest car in each pool will get you the fastest car overall.
(Eliminate it from the pool)
+
1 race between the fastest remaining car in each pool will get you the 2nd fastest.
(Eliminate it from the pool)
+
...
+
1 race between the fastest remaining cars in each pool (by now, some pools may be completely empty. Their spot will be blank) will get you the 25th fastest car.
7 races to sort plus 24 elimination races + final race = 32 races
The grid approach to find the median will not necessarily work. Take the following as the initial 7 pools:
Pool 1: 1, 6, 7, 8, 9,10,11
Pool 2: 2,12,13,14,15,16,17
Pool 3: 3,18,19,20,21,22,23
Pool 4: 4,24,26,27,28,29,30
Pool 5: 5,31,32,33,34,35,36
Pool 6: 25,37,38,39,40,41,42
Pool 7: 43,44,45,46,47,48,49
The grid remains unchanged if you sort the rows, then sort the columns. However, 25 is not on the median.
I think the answer is 76.
1. 1st race take topmost 4 cars out of 7 and do next race with these 4 and 3 from the 42(49-7) pool.this will be 15 races (1 first race with 7 from 49 pool and 42/3=14 for remaining 42 pool).
2.now we have 45 pool as we already got 4 top most speed cars in first step.do the same process here we will get 13+1 ( 1 first race with 7 from 45 pool and 38/3=13 for remaining 42 pool).
3.same as step 1 and 2 here we will get 12+1
4.same as step 1 and 2 here we will get 10+1
5.same as step 1 and 2 here we will get 9+1
6.same as step 1 and 2 here we will get 8+1
in above six rount you got 24 top most
7.In 7th round we have 25 cars(as in above 6 rounds we got fatest 24 cars) to find top most in this we need just 4 races)
total 15+14+13+11+10+9+4=76
correct me if i am wrong.
I think the answer is 76.
1. 1st race take topmost 4 cars out of 7 and do next race with these 4 and 3 from the 42(49-7) pool.this will be 15 races (1 first race with 7 from 49 pool and 42/3=14 for remaining 42 pool).
2.now we have 45 pool as we already got 4 top most speed cars in first step.do the same process here we will get 13+1 ( 1 first race with 7 from 45 pool and 38/3=13 for remaining 42 pool).
3.same as step 1 and 2 here we will get 12+1
4.same as step 1 and 2 here we will get 10+1
5.same as step 1 and 2 here we will get 9+1
6.same as step 1 and 2 here we will get 8+1
in above six rount you got 24 top most
7.In 7th round we have 25 cars(as in above 6 rounds we got fatest 24 cars) to find top most in this we need just 4 races)
total 15+14+13+11+10+9+4=76
correct me if i am wrong.
I think the answer is 76.
1. 1st race take topmost 4 cars out of 7 and do next race with these 4 and 3 from the 42(49-7) pool.this will be 15 races (1 first race with 7 from 49 pool and 42/3=14 for remaining 42 pool).
2.now we have 45 pool as we already got 4 top most speed cars in first step.do the same process here we will get 13+1 ( 1 first race with 7 from 45 pool and 38/3=13 for remaining 42 pool).
3.same as step 1 and 2 here we will get 12+1
4.same as step 1 and 2 here we will get 10+1
5.same as step 1 and 2 here we will get 9+1
6.same as step 1 and 2 here we will get 8+1
in above six rount you got 24 top most
7.In 7th round we have 25 cars(as in above 6 rounds we got fatest 24 cars) to find top most in this we need just 4 races)
total 15+14+13+11+10+9+4=76
correct me if i am wrong.
We are being asked to create a complete ordering from a partial ordering. Each race gives you a
Here's what I would do under pressure in an interview:
1) Build a min heap -- O(2n) = 100 races
2) Search for the 25th smallest car by repeatedly removing the min 24 times, O(24*log(49)) == maybe 125 races.
So maybe 225 races, ballpark. You could store results with adjacency lists and maybe save some races if you value fuel over space complexity.
A very simple solution: In seven races we find the 3 fastest ones in each lap. So we know the 21 fastest people. We have to find the 4th fastest among the other 28 people left. By doing 4 races we find the 4 fastest ones and finally by doing a single race between these 4 we find the 25th guy. The problem is solved by doing at least 12 races.
Answer is 14
Create a 7x7 matrix of the cars. Arrange each row in sorted order (by racing. 7 races, once per row). Then arrange each column in sorted order (by racing again, 7 races, once per column). The topology of this matrix causes something like this...
z = x^2 + y^2
on the interval {x: [0, 1], y: [0, 1]}
Every square along the diagonal is greater than every square directly to its left, and is also greater than every square directly above it. This means (by recursing this relationship), every nth square along the diagonal is greater than n^2 elements.
So, go to the 5th square along the diagonal, and this car is greater than 25 other squares.
I think the answer will be 30 races
consider this :-
from 7 race we get 7 top horses out of 49 so we remove these 7 and now we have to find 18th( 25-7) fastest horse in remaining 42
similarly again do 7 race and remove 7 . Now we have to find 11th fastest out of 35 remaining
then again do 7 races and remove 7 fastest . now we have to find 4th fastest out of 28 remaining.
now do 7 races and find TOP 7 horses
now race these 7 horses and find top4( top1-grpA , top2- grpB ,top3- grpC, top4 grp D)
now we need one more race to have fastest of remaining as:-
from grpA take 3 horses of position 2,3,4( removing top1)
from grpB take 2 horses of position 2,3( removing top2)
from grpC take 1 horse of position 2( removing top3)
from grpD take top4 itself
now race these 7 and fastest of these will the 25th fastest !!
so total number of races will be 30( 7+7+7+7+1+1)
are you stupid?
absolutely wrong solution
How can you say when you go for 7 races of 7 horses each, that you will find the top 7 horses??
There may be a case that top 7 horses come in a single race and remaining are distributed differently in different races.
In this case you will remove only one of the top 7 horses
Hence your solution is absolutely wrong
We can use seven track and put all cars on it, do one race of 49 laps and know all the ranking from 1 to 49. question never says one track one car.
no one ever said u can only race 7 cars at a time. u could possibly fill 49 on one track.
@MNS. You can also do billion other "out-of-the-box" answers, say use half of the track to rank first 7, or use speedometer because question never says we don't have one.
All these do not help with the interview and the actual answer.
I agree; you are basically saying you need more information. In a real Google interview, if the question was posed like this, I would ask how many cars can race per track. This is a trivial solution and you know they would not ask it this way.
Hmmmm......Select Algorithm. 7 races. Choose the median cars. Run the 8th race take the median.
32 races.
After 7 races, we can iteratively find the ith fastest in every extra race. So 25th fastest would be 7+25=32. Wonder how?
Take for simplicity, there are 9 cars and 3 tracks and we are supposed to find the 4th fastest one.
Let the cars be 1,2,3,4,5,6,7,8,9. After first three races, teh results look like..
(2 1 3) (6 4 5) (7 9 8)
To find the 1st fastest - try , 2 6 7
Assume the results come out to be (2 6 7) [The same order]
So fastest is 2.
To find the 2st fastest, you only need to race 1 6.
Case1 :
Say 1 wins. So 1 is the 2nd fastest. The 3rd fastest can be found by racing 3 and 6. If 6 wins, the 4th fastest can be found by racing 3 and 4...so on..
Case 2:
Say 6 wins. The 3rd fastest can be found by racing 1 and 4. and so on..
So overall if eveey ith step, you only need to race 2 cars(total tracks -1 ) except when i=1.
I can see mistakes or less efficient algos in every solution above. Also I am not claming that the above solution is optimal.
@amshali I don,t think yuor solution is correct.
I think 137 races are needed.
43 to remove last 6.
then 37 to remove last 6 again.
similarly then 31 and 25 to remove last 6.
now we are left with 25 cars we find best car in 4 races.
so total 137 races are needed.
your answer is not correct. In first 7 races you are getting local maxima of each race. In 8th race you are just finding global maxima. It doesn't give you any information where 25th car should be at. It could be in bottom 4 car slots..
Yes, you are correct, my answer is wrong,
so if we apply brute force,
7+1=8 races will give me 1st fastest car,
and for remaining 24 cars (25th fastest) we need 24 races (eliminating fastest car and selecting next fastest from the same lot)
so 24+8=32...?
I am sure there is a better answer to this question...
The result should be 10.
- wenlei.zhouwl May 24, 20121. Create 7 * 7 matrix. Take race row by row. So it costs 7 races and every row is in increasing order.
2. Race the middle column, and sort the rows in the order of their middle column value. So the cars in the left and top of the center car of matrix should run slower than the center car. The cars in the right and bottom of the center car should run faster than the center car. They can not be the 25th car. Now we get
A[1][5],A[1][6],A[1][7]
A[2][5],A[2][6],A[2][7]
A[3][5],A[3][6],A[3][7]
A[4][3],A[4][4],A[4][5]
A[5][1],A[5][2],A[5][3]
A[6][1],A[6][2],A[6][3]
A[7][1],A[7][2],A[7][3]
and we want to find the 25th car in the 7*3 matrix.
3. Race the middle column, and sort the rows according to their middle value. Similar to the step 2, we can delete the cars which can't be the 25th car. And here remains a one-column matrix.
4. Race the remaining column and we get the middle car as the 25th car.
So the result should be 10 races.