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.