Microsoft Interview Question
Software Engineer / DevelopersCountry: India
it will take 2*n days to complete tournament because consider only n/2 matches can be held in one day
Hint:
1. Circular array of all teams
2. Day 1 & 2 array plays array offset by 1 (depending if &1 of first array evaluates to 0 or 1)
3. Day 3 & 4 array plays array offset by 2 (depending if &2 of first array evaluates to 0 or 1)
etc till array offset by (floor)(N/2) (if N is even then only 1 day, else 2 days)
Let's brainstorm little bit...
N=1 -> Can't be happened
N=2 -> 2-1
N=3 -> 3-2, 3-1, 2-1
N=4 -> 4-3, 4-2, 4-1, 3-2, 3-1, 2-1
You can see this can be handled recursively... Not smart approach but below code spinet should do trick (I hope)
public HashMap<int, int> getMatches(int N, HashMap<int, int> matchMap)
{
}
We should use different approach for odd and even N:
-N is even:
F(N) -> number of days in tournament
We partition the teams into two groups each has N/2 teams. Then schedule matches in each group. => F(N/2)
If the number of teams in each group is odd (means that N=4K+2 => N/2 = 2K + 1 =>Odd) at each day we will have a free team in each group => we add a match between these two free teams at each day (** later reminder!)
After all matches in groups are done, we will go to find possible matches between these two partition. This is a classic problem of finding possible matching in a two partition graph. Here, the number of matchings is equal to N/2. But for (**) cases, we should decrease it by one! (Guess why)
F(N) = F(N/2) + N/2 - (((N/2)%2)?1:0);
At the end we will have N-1 days of matches.
- N is Odd
We have the following nodes in our graph: a1, a2, ..., aN. Assume these nodes in a Circle.
At each day one of the nodes is free. At each day we will make a match between two teams which have the same distance from the free node. For example if N=7 and a4 is free at a day, then matches will be as follows at that day: (a3, a5), (a2, a6), (a1, a7).
At the end, we will have N days of matches.
There can be maximum of [N/2] matches per day.(here N/2 is int devision i.e 3/2 is 1 and 5/2 is 2)
Total number of matches possible are N*(N-1)/2. Since this is uniform distribution we can always choose max of N/2 matches each day. Below is the code (for clarity run the below code)
static void scheduleMatches(int N){
if(N<=1)
return;
int totalMatches = N*(N-1)/2;
int MAX_MATCHES_IN_DAY = N/2;
int days = 0;
int[] a = new int[N-1];
for(int i=0;i<N-1;i++)
a[i] = i+1;
while(totalMatches!=0){
int j=0;
int num = MAX_MATCHES_IN_DAY;
System.out.print("\n Day " + (days+1) + " Matches :");
while(num!=0){
// Check if team j has played all the matches
if(a[j]<N){
int matchnumber = N*(N-1)/2 - totalMatches +1;
System.out.print("Match " + matchnumber +": " + "Team " + (j+1) + " Vs Team " + (a[j]+1) + " ");
a[j++] += 1;
totalMatches--;
num--;
}else
j++;
}
days++;
}
System.out.println("\n Total Number of Days is " + days);
}
@Manan , one team can play single match per day. but by ur program single team can play with 2 different teams.
so please modify accordingly.
suppose we have 4 team then your program will give following output.
Day 1 Matches :Match 1: Team 1 Vs Team 2 Match 2: Team 2 Vs Team 3
Day 2 Matches :Match 3: Team 1 Vs Team 3 Match 4: Team 2 Vs Team 4
Day 3 Matches :Match 5: Team 1 Vs Team 4 Match 6: Team 3 Vs Team 4
Total Number of Days is 3
Since every one has to play match with other.
Total number of matches = n(n-1)/2
Now,
If n is even:
We can schedule n/2 matches every day, completing all matches in n(n - 1)/2n = n - 1 days
If n is odd:
Scheduling n/2 matches one person is left out every time and so completing all matches will take one more day than when n is even
We can schedule matches in n days when n is odd.
Round-robin algorithm:
public class GameSchedule {
public static void scheduleGames(int nmb) {
int days = (nmb % 2 == 0) ? nmb -1 : nmb;
for (int i=0; i<days; i++) {
System.out.println("\tDay " + (i+1) + ":");
for (int j=0; j<nmb/2; j++) {
int t1 = (j+i) % nmb + 1;
int t2 = ((nmb - j -1) + i) % nmb + 1;
System.out.println("\t\tTeam " + t1 + " v.s Team " + t2);
}
}
}
public static void main(String[] args) {
for (int i=1; i<12; i++) {
System.out.println("Schedule for " + i + " teams:");
GameSchedule.scheduleGames(i);
}
}
}
@zproqd : This approach works only when n is power of 2. Can someone explain how to generate the schedule in other cases.(I know that answer is n for odd n and n-1 for even n but can some prove this or justify by giving an algo for doing it)
Let's brainstorm little bit...
N=1 -> Can't be happened
N=2 -> 2-1
N=3 -> 3-2, 3-1, 2-1
N=4 -> 4-3, 4-2, 4-1, 3-2, 3-1, 2-1
You can see this can be handled recursively... Not smart approach but below code spinet should do trick (I hope)
public HashMap<int, int> getMatches(int N, HashMap<int, int> matchMap)
{
}
For example we have 8 teams:
1 2 3 4 5 6 7 8
Divide they onto 2 groups and let play each team one group with each team another group:
All teams one group just had games with all teams another group. But teams inside one group didn't have game between each other.
Repeat that algorithm recursively for every group
Once again divide every group
That's all :-)
- zprogd June 27, 2012