Consider a series in which 8 teams are participating. Each team plays twice with all other teams.
4 of them will go to the semi final.
Minimum and Maximum how many matches should a team win, so that it will ensure that it will go to semi finals ?
Solution :
Lets consider that with each win , team gets 1 point.
8 teams play match against each other so 56 matches, so series consist of 56 points
Lets distribute and find minimum and maximum..
Say Teams are T1,T2….T7,T8.
To calculate Maximum points that a team can win and qualify for finals, lets best case consider scenario.
T8 wins all games and gets 14 points.
T7 wins all against T0 to T6 looses against T8 only, so T1 has 12 points
like wise …
T6 : 10
T5 : 8
T4 : 6
T3 : 4 (Won against T1,T0)
T2 : 2 (Won just against T1)
T1 : 0 (Lost all matches)
So Maximum a team can have is 14 points
If N teams are participating : TN team wins all 2*(n-1) games so 2*(n-1) points.
Where 2 is number of time each team plays against other team.
To Calculate Minimum points…Lets consider worst case scenario
redistributing above mentioned points
T8 : 10
T7 : 10
T6 : 10
T5 : 10
T4 : 10
T3 : 4
T2 : 2
T1 : 0
This is most worst case that can happen but as in semifinals only 4 team goes,
minimum can be 11 points as follows
T8 : 11
T7 : 11
T6 : 11
T5 : 11
T4 : 6
T3 : 4
T2 : 2
T1 : 0
So Minimum is 11, so that a team will surely go into semifinals….
Now lets consider scenario where with minimum points a team qualified for semis.
T8 : 14
T7 : 13
T6 : 12
T5 : 5
T4 : 3
T3 : 3
T2 : 3
T1 : 3
Here Team 5, could get just 5 but could qualify for Semis.
Comment for any other options..
Question was asked in Kony Labs Interview for SDE-I.