Microsoft Interview Question for Software Engineer / Developers


Country: India




Comment hidden because of low score. Click to expand.
2
of 8 vote

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:

day 1:
1 2 3 4
5 6 7 8
day 2:
1 2 3 4
6 7 8 5
day3:
1 2 3 4
7 8 5 6
day 4:
1 2 3 4
8 5 6 7

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

day 5:
1 2                5 6
3 4                7 8
day 6:
1 2                5 6
4 3                8 7

Once again divide every group

day 7:
1          3          5          7
2          4          6          8

That's all :-)

- zprogd June 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice

- Vikas October 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

it will take 2*n days to complete tournament because consider only n/2 matches can be held in one day

- kararicky August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

It will take n-1 days to finish the tournament.

Total number of matches = nC2 = (n^2-n)/2
Total number of matches/day = n/2

Dividing both we get n-1

- Vikas October 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- sri July 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have 5 teams...How do i plan,so that every one will get equal chance to play...

- pradeep November 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

codepad.org SYVdJ3Fx

- Old monk June 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

There are only 4 matches possible in days 2,3,4,5,6,7 and only 2 matches possible in 8,9,10,11,12,13,14,15.

In days 2,3,4,5,6,7 there can be a maximum of 5 matchs are possible instead of 4.

So total days of 15 can be reduced to n-1(9).

- SantiagoYemmiganur June 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)
{

}

- TS June 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- Atefeh June 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

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);	
		}

- loveCoding June 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

downvoter care to explain?

- loveCoding June 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- Gupta June 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- Aayush Bahuguna June 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

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);
        }
    }
}

- sqw June 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think this is wrong.
For nmb = 6, for i = 0, j = 2 and i = 3 and j = 0 teams 3 and 4 play, repeating matches.

- Naveen Reddy Mandadi August 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@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)

- Anonymous June 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it was homework to sketch the odd case :-)

for 1 2 3 4 5:

day 1 (divide onto 2 group):
1 2 
3 4 5
day 2:
1 2 
5 3 4
day 3:
1 2
4 5 3
day 4 (divide every group by 2):
1       3
2       4 5
day 5:
3
5 4

- zprogd June 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

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)
{

}

- TS June 26, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More