Amazon Google Interview Question Developer Program Engineers Software Engineer / Developers
Nice logic. Just make sure top 4 win all the games against the rest, then top 4 share the wins among themselves.
It's 11:
Let number the teams : 1 , 2.. 8, and say 8 beats all 1..7, 7 beats all 1..6 we will have this:
8: 14
7: 12
6: 10
5: 8
4: 6
3: 4
2: 2
1: 0
Ok for now it seams that 8 is a good answer, but is it?
Let's make very equilibrated, and make team number 4 closer to the top:
1) Let's assume Team 4 bets team 8 twice: that will result in:
8:12 (14 - 2)
7:12
6:10
5:8
4:8 (6 + 2)
3:4
2:2
1:0
Now it seams that 8 is not good, and it's 9, but is it?
2) Let assume Team5 beats team 8 twice
8:10 (14 - 2 - 2)
7:12
6:10
5:10 ( 8 + 2)
4:8 (6 + 2)
3:4
2:2
1:0
Now it seams that 10 is just perfect , but is it?
3) The final match: Team4 beats Team 7 twice:
8:10 (14 - 2 - 2)
7:10 (12 - 2)
6:10
5:10 ( 8 + 2)
4:10 (6 + 2 + 2)
3:4
2:2
1:0
It seamns that if this would happend 11 is the perfect number
Another reason is that the 5 team beats all the team, but still, remains 6 points( beacause there must play Team3 vs Team2 twice, T3 vs T1 and T2 vs T1) and remains 50 points
50/5 = 10 points in the perfect case . and because of that 11 is the number.
i think ur solution is wrong .......
answer is 12 ...
(team) (matches played) (win) (lose)
1 14 11 3
2 14 11 3
3 14 11 3
4 14 11 3
5 14 11 3
6 14 1 13
7 14 0 14
8 14 0 14
8 teams will play other 7 teams twice, so they would play 14 games in all. Now say 1 game win is 1 point, ideally best team winning all will have 14 points. the next best will have 13,12,11. So worst case when the rank 1-3 teams wins as above, teams need to win at least 11 matches to reach semifinal. There can be best cases when team rank1 wins 10 matches
when best team wins 14 points, it has won all the games right? that means with the second best team it has won all 2 games. then second best team definitely losses two matches. then how come it can score 13 points.? it can score only 12 points.
true...
its possible all qualifying 4 teams lose 3 matches with other 3, and tie with winning 10 games each. So team scoring 11 could win
11 is the correct ans....
in worst condition no. of winning match:
Team A = 11
Team B = 11
Team C = 11
Team D = 11
Team E = 3
Team F = 3
Team G = 3
Team H = 3
why not atleast 11 matches. Let say we have 4 teams A,B,C and D these teams have won all matches with E,F,G and H. So Each team wins 8 Matches. Now A has to play 6 Matches(2 each with B, C and D), lets say A lost 1 match and won 1 match with each B,C and D. Same is the case with B, C and D. So each of A,B,C and D has won 11 matches and they are in semifinal.
but wen you said A,B,C,D won all matches with E,F,G,H. they will have 8 points.now the maximum points that E,F,G,H can score at this situation is 6 only. so, irrespective of no. of points A,B,C,D score they will be definitely more than E,F,G,H. so by that time itself A,B,C,D will be in semis.
but still as you said answer is 11 only, but in other way.. think the other possible way?
Yes there is one more way. It could be possible that
A, B, C , D and E each will win 10 matches and its a Tie. So to be on Safe Side each team will think it has to win atleast 11 matches..
it's 8..do you ppl know bout deadlock..7 is the number where they re deadlocked..so one must win atleast 8 to ensure to succeed..
all those who are saying 11 just try to find a scenario where someone wins 8 matches but still fails to qualify. in the process of finding that example you will be enlightened ;)
Note: If u say someones winning do remember to count a loss for wwhos losing.
total no. of games can be played are: (8c2)*2. that is 56.so, 56 points can be scored overall if for one win one point is considered. consider one team losses all matches . second team wins 2 matches and 3rd team wins 4 matches. now totally 6 points are csored. now 50 points left for 5 teams. consider remaining five teams score 10 points each. even in that case also tie may happen for all 5 teams. so, you need to score 11 points to be in semi final.
I came up same answer using a different idea. Total points is 56. I assume win (1) - lose (0), i.e. no tie. I partition 8 teams in 2 sets, S1 = {A,B,C,D} and S2 = {E,F,G,H}. There are 2*4c2 = 12 matches among S2. Hence, 12 points can't be go to any member of S1. Hence each member of S1 should have (56-12)/4 = 11 points to make it confirm that it'll be in semi final whatever the other outcomes is.
Using the same approach it seems if number of teams were 10, it needs 2*(10c2 - 5c2)/5 = 14 games to win.
@putta.sreenivas u r assuming everything how u make sure thats u r correct i means u r asuming
consider one team losses all matches . second team wins 2 matches and 3rd team wins 4 matches. now totally 6 points are csored. now 50 points left for 5 teams. consider remaining five teams score 10 points each. even in that case also tie may happen for all 5 teams. so, you need to score 11 points to be in semi final.
can u please eloborate more..??
@putta.sreenivas...so say to enter in samifinal one team need atleat 11 matches win so what points remaining 3 team shoud earn to get inside semifinal is it 11 or something else ..can u explain ..???
as its obvious 4 team will go into samifnail so m aksing about all 4 teams what everyone shoud earn to get inside samifinal from 8 teams..???
@Martin: read my comments posted below. Minimum number of wins could be 5 for a team to go to semi. Here's how:
A => 14 wins
B => 13 wins
C => 12 wins
D => 5 wins
E => 3 wins
F => 3 wins
G => 3 wins
H => 3 wins
11 is the answer that guarantees team will go whatever rest 45 matches outcome are. Don't mix the two scenarios.
In this case, if team A has won all 14 matches, then all the other teams have lost to team A. ie. B can not have 13 matches won. It can only has 12 matches won. Also if B has won 12 matches and lost both the matches against A, it should win against all the remaining teams. ie. C cannot have 12 wins. It can have at max 10 wins.
A team will play total of 7*2 = 14 games so 8 games is needed for a team to advance to next stage
A team will have to play 7x2 matches. Just for example a team has to play 7 matches with all other team once in home ground and other 7 matches in away ground once.
For an example teams won their home games and lost their away games. That means all the 8 teams will have same points bcoz all the teams won 7 matches each(which is the worst case)
For a team for qualifying semi-final it has to win atleast 8 games.
It has to be 8.
Consider the case when every one has on the same number of matches, this is possible when out of 14 each win 7 and lose 7. so all will have same points 7 right. Then if any team would have won 8 times then his place would be confirm in the semifinals.
@Baba: you are assuming the "lowest possible" number of matches to win to go to final which is dependent on other team's results.
The question asked for lowest number of matches to win that guarantees without considering any other match outcome. Being said that, it is 11 matches if one team win, it DOES NOT matter what other matches outcome are. It WILL go to semi round for sure.
Just to say that it's even possible for one team to win MINIMUM 5 matches to go to next round. Here it's how:
As I explained above the winner 4 teams can get at max 44 points out of 56. Each team in loser 4 teams may get (56-44)/4 = 3 points each. Now, out of 44 points, first top three may get 14+13+12 = 39 points. Hence, even getting 44-39 = 5 points one team may go to semifinal. One crucial observation is that it CAN'T be 4 points, because in that case one team (from loser 4 teams) also score 4 points - that's a tie.
Why you are breaking heads,
You will be guaranteed to be part of semifinalist only if you win all the games in first round and be in top 4 in second round.
In case of 8 teams -
First round - 7 points (win all the games)
Second round - Be top 4 teams.. so you have to get only 4 points
so total is 11.
In case of 10 teams -
First round - 9 points (win all the games)
second round - Be top 4 teams.. means 6 games you have to win.
total = 9+6 = 15.
But here there is a problem, what if everyone plays the same way.. so to avoid that add 1 more point extra so that all can't get the same points..
This applies to all different possible combinations..
8 is correct.
Here's my reasoning:
Each team has to play 14 matches in total
Team A wins all 14 matches
Team B can win a maximum of 12 matches (because it has already lost 2 matches against Team A)
Team C can win a maximum of 10 matches (because it has already lost 2 matches against Team A and 2 matches against Team B)
Continuing like this, Team D can win a maximum of 8 matches.
Answer is 11, using the formula given above 2*(8c2-4c2).
but for 10 teams, answer should be 15, because only 4 teams are going to play semifinals.
so 2*(10c2-6c2) = 60 matches for all the teams in the semifinal; hence, at least 15 wins are required.
a simplified formula could be 2*(N-M)+(M-1)
where, N - total no of teams
M - no of teams to be selected
Suppose there is a team won 'k' games. How does it know it will go to the semi final?
That is:
"even if there are three teams won greater and equal than 'k' games, there can not be a forth team who won more than 'k' games.
1. Suppose there is no "even" game.
2. There are total 56 games to win.
3. So the number of games won by those teams who won greater or equal to 'k' games are "4k+a". a >= 0.
4. So the remain games could win are "56 - 4k - a".
5. 56 - 4k - a < k
6. So, 56 - a < 5k
7. To find the greatest k, set a == 0
8. 56 < 5k -> 11.2 < k
9. so k == 12
wfchiang - it is incorrect even when you think intuitively - no disrespect though.
Answer = 8 games.
Total games played: 8 teams * 14 games = 112 games
Games won: 112/2 = 56 games (because when one team wins, other loses - assuming no ties)
What is the most competitive situation case: 56 games/8 teams = 7 games won by each team.
So when all teams win 7 games each, it means they all have equal place.
To get to 1st place, it must be 8, but other team win should be diminished to 6
To get into 2 winning teams, it again must be 8, making 2 other teams win =6 and so forth, until we have 4 teams having 8 wins and 4 teams having 5 wins
So, in most competitive situation, you will need 8 wins to get through. If someone has better mathematical explanation, I will appreciate that
have to correct myself.
All 5 teams beat 3 teams twice. Each team now has 6 points (30 points total) and 8 games to play with other top teams (20 points to split). Should they each win 4 games and lose 4, each of them will have 10 points. Or 50/5=10. To avoid the draw a team has to win 11 games.
11 is correct. 4 teams can tie at 11 wins each. Demonstrated with the following matrix, the top row and left column are the team numbers. The rest of the numbers indicate which team won. X is for no match (you cannot play yourself). ? is for does not matter who won.
X 1 2 3 4 5 6 7 8
1 X 2 3 4 1 1 1 1
2 1 X 3 4 2 2 2 2
3 1 2 X 4 3 3 3 3
4 1 2 3 X 4 4 4 4
5 1 2 3 4 X ? ? ?
6 1 2 3 4 ? X ? ?
7 1 2 3 4 ? ? X ?
8 1 2 3 4 ? ? ? X
Look at this situation below. 1st 5 teams split 11 wins each (11 * 5 = 55)
Total is 56 wins. In that situation, you do need 12 wins to guarantee to get through.
Just put that in Excel. So wfchiang is correct I take my words back - 12 wins is the answer
Team No Wins
1Â Â Â Â Â Â 11
2 11
3 11
4 11
5 11
6 0
7 0
8 0
Hi ielisman
Answer is 11 match
coz in your situation it is not possible that last 3 teams having 0 wins. as they ll play amoungst themselves also
so last 3 team will have 6 games within themselves.
so out of 56 games 6 gone
Now in must reach situation if u take 10 win
then 5 teams can have 10 win each. So this doesnt ensures reaching into finals.
so you can do it in 11 matches,
To make sure that a particular team makes it to the semi-finals without worrying about other teams performance the team has to win 11 games/points. In a real world there can be a win/lose/draw(tie).
Here is the explanation:
Each team plays the other team = (8 X 7) / 2 = 28 games
(Divided by 2 as each game has 2 teams
As the teams play each other twice it is 28 X 2 = 56 games in total
To find out a minimum number of games required to qualify, lets assume that there is atleast 1 more team (5th team) competing. Assume the worst case that the remaining 3 teams don't win any matches with the competing top 5 teams.
But those botton 3 teams still play a total of 6 games with each other and would get points for those games.
So from above the top 5 teams get points from the remaining 50 games. Dividing them equally its 10 points or wins each team.
And hence to qualify for sure without considering any other teams performance, any team that wins 11 games or in real world gets 11 points (considering 1 point for a win and half a point for a draw) would qualify for semis.
So the correct answer is 11 points (1 point for a win and 0.5 point for a draw/tie)
I think answer is 12.
Each team plays 14 games, and there are 56 games in total.
Let the minimum number of wins to ensure a top 4 finish be X.
The number of wins are closely bunched when the top teams all win X games.
To ensure progress to semi-final, the 5th team (by order of most wins) must not be able to get X wins.
So, we have
56 - (4*X) < X
=> X > 11.2
So X is 12.
Cases:
With X = 11, top 4 teams win 11 each, there are 12 games remaining to be won. The 5th team can still win 11 games. Thus, progress to semifinal is not ensured.
With X = 12, top 4 teams win 12 each, there are 8 games remaining to be won. This ensures 5th team can in no way progress to semifinal.
Full mark would be 14.
if team T got 13, that means it is possible an other team T1 win all the game except losing one to T(there two matches). T and T1 are all at first place with 13 wins.
if team T got 12, that means there are two situations:
a > it exists a team T3, wins all game(including the two lost by T), T is the second place.
b > it exists two teams, T4 and T5, they won T once, and T4 to T5 once and T5 to T4 once, they got 12 points too. So, will three are at fist place.
If team T got 11, that means it lost 3 games:
a > it exists a team T6, wins all game, including 2 of T. another team tie T7 to T got 12 points(lost one to T6).
b > it exists another 3 teams, all get 11 points. That's the minimum we can accept.
So 11 is the answer.
Answer is 10,
let us assume there all win same number of matches, where no one goes to semi
8 * number of wins = total matches
total matches = 8C2 *2 = 72
number of wins where no one goes to semi's = 9
Inorder for 4 to go, 4 teams have to win above 9
i.e 10
where 4 teams win 10 matches and remaining win 8 matches,
you can secure you place in semi's if no of win is more than 10
8 is the right answer. Let there are 8 teams A, B, C,D,E, F, G, H. So consider that A has win over all so he has won 14 matches. Let at second place B is coming so B is all ready having a defeat with A so he can win only 12 matches then similarly C can win only ten matches and d can win only 10 matches. So winning 8 matches ensure you in semifinal
It has to be 11 matches.. 8th team scored 0 wins.. then 7th team have at least 2 wins.. 6th placed team can have at least 4 wins.. so we have 6 wins.. 50 wins left for 5 teams... now each team won 10 of matches.. so we have five teams each won 10 matches an d place in semis depends on run rate.. so if any team won 11 matches will go to semis without consideration of run rate...
please don't read this long chain of comments and save ur time .......following solution is correct
answer : 8
explanation :
all team played equally well then following is condition :
(team) (matches played) (win) (lose)
1 14 7 7
2 14 7 7
3 14 7 7
4 14 7 7
5 14 7 7
6 14 7 7
7 14 7 7
8 14 7 7
....................it means that no one can going to semi final or all are going to semi final...it means that answer is bigger than 7.....
Now, consider answer is 8 .....and suppose that 4 team won 8 matches and lose 6 matches out of 14 ..then following situation :
(team) (matches played) (win) (lose)
1 14 8 6
2 14 8 6
3 14 8 6
4 14 8 6
5 14 7 7
6 14 7 7
7 14 7 7
8 14 7 7
....here we can decide that team 1,2,3,4 can go to semi final ....so answer is 8 !!!
correcting stupid mistake .................
please don't read this long chain of comments and save ur time .......following solution is correct
answer : 8
explanation :
all team played equally well then following is condition :
(team) (matches played) (win) (lose)
1 14 7 7
2 14 7 7
3 14 7 7
4 14 7 7
5 14 7 7
6 14 7 7
7 14 7 7
8 14 7 7
....................it means that no one can going to semi final or all are going to semi final...it means that answer is bigger than 7.....
Now, consider answer is 8 .....and suppose that 4 team won 8 matches and lose 6 matches out of 14 ..then following situation :
(team) (matches played) (win) (lose)
1 14 8 6
2 14 8 6
3 14 8 6
4 14 8 6
5 14 6 8
6 14 6 8
7 14 6 8
8 14 6 8
....here we can decide that team 1,2,3,4 can go to semi final ....so answer is 8 !!!
Total no. of points is 56.
max points any team can ge is 14
No. of points someone can make to be sure of a playoff spot is 12.
56/12 = 4, so if 4 teams get 12 points then there are only 8 points left for the others to get into the playoffs which is not possible.
56/11 = 4, so if 4 teams get 11points then there are 12 points left for the other teams to get, thus if one of those teams wins all games against those not making 11 points then it will have 12 points.
thus the minimum amount of points that guarantees a playoff spot is 12.
The solution is 11 and I think the logic behind is as below:
Fact1: there are totally 56 matches, so the total number of winning and the number of losing should be 56. (for each match there should be a winner and a loser)
Fact2: each team would have 14 matches with the others, so for each team, the number of winning plus the number of losing should be 14.
In order to find the min number of winning times to ensure to get into semi, we assume the first four teams are supposed to get in. We let the number of winning for the first four teams be x, so they number of losing for them is (14-x). If the x is not large enough, we would find at least one team, let's say team 5, have the number of winning more than x. We need to avoid this happen. Let's assume the team 5 be our bottleneck and we let it has the winning as large as possible. We cannot ignore the last three teams at the same time. there are two matches between team 6 and team 7; two matches between team 7 and team 8, so there should be at least four winning time for team 6,7,8. So the first five teams should split at most 52 winnings. So the number of winning left for team 5 is at most 52-4*x. We let 52-4*x<x, we have x>10.4, so the solution is 11.
Let's use N represent the number of the matches that a team must win to
ensure semi final. Let divide the 8 teams into 2 4-team groups: A and
B. All the teams in group A enter semi final. N is obtained when the
following two conditions are satisfied:
1. Group A wins the most possible points.
2. The points of group A are distributed evenly to all 4 teams.
Condition 1 is satisfied when all teams in group A wins in games against
teams in group B. In such cases, group A has more than 32(4 * 8) points
than group B. Group A also has 12 points for games against each other
within group A. So group A has 44 (32 + 12) points in total. Distribute
44 points evenly to 4 teams. 44/4 is 11. So N is 11 points.
If a much rigorous solution is needed, condition 1 and 2 need to be
proved.
Here is a rigorous solution:
1) It is possible to construct a case, in which a team fails to qualify with 10 points. Suppose the first 5 teams beat the bottom 3 teams. That's 6 points for each of the top 5 teams. Suppose also the top 5 teams win their home games against each other, and lose the away games. That's 4 more points, for a total of 10 points each for the first 5 teams. One of the top 5 teams fails to qualify on "goal difference."
2) Next, we want to show that such a construction is not possible for a threshold of 11 points. Suppose a team has 11 points. Now notice that the bottom 3 teams have 6 games between each other, and will therefore always have at least 6 points in total. That means that the top 5 teams have at most 50 points in total. (Since there are 56 games in total.) But then, by the pigeon-hole principle, if one of the top 5 teams has at least 11 points, then another one has at most 9 points. Therefore it is impossible to be 5th with 11 points, i.e. with 11 points you are guaranteed to qualify to the semi-finals.
56 points are distributed to 8 team. In the worst case, team0 loses all the games, he gets 0 point. team1 win two games with team0 and loses all other games, he gets 2 points. In the same way, team2 gets 4 points, team3 gets 6 points. So there are 44 points left which can be distributed to the remaining 4 teams. So the assurance points for a team should be 11 points.
- wenlei.zhouwl May 22, 2012