## Microsoft Interview Question for Software Engineers

• 3

Country: United States

Comment hidden because of low score. Click to expand.
1
of 3 vote

This is round robin tournament algorithm. Here is my implementation :

``````void scheduleTournament(int teams, int round) {
if (((teams%2 != 0) && (round != teams - 1))||(teams <= 0))
throw new IllegalArgumentException();
int[] cycle = new int[teams];
int n = teams /2;
for (int i = 0; i < n; i++) {
cycle[i] = i + 1;
cycle[teams - i - 1] = cycle[i] + n;
}

for(int d = 1; d <= round; d++) {
System.out.println(String.format("Round %d", d));
for (int i = 0; i < n; i++) {
System.out.println(String.format("team %d - team %d",cycle[i],cycle[teams - i - 1]));
}
int temp = cycle;
for (int i = 1; i < teams - 1; i++) {
int pr = cycle[i+1];
cycle[i+1] = temp;
temp = pr;
}
cycle = temp;
}
}``````

Comment hidden because of low score. Click to expand.
0

yes, robin algo is cool.

Comment hidden because of low score. Click to expand.
0
of 0 vote

@divm01986 - it shouldn't be hardcoded..algorithm should be made generic. Sorry for not including this in the question.

Comment hidden because of low score. Click to expand.
0
of 0 vote

You can solve this problem in O(n^2) time, n is the number of teams and m is the number of game days. There is a constraint that n is a power of two when n-m has a difference of 1. Simply use a circular linked list, and a hashset. Two pointers into the linked list (the "follower" approach), where one pointer is one element in front of the other, and insert the elements into the set, and store the pair. The pair will be part of your solution. After the set has a count of n, restart the pointers, and increase the jump distance of the leader by 1. Sudo code below

``````Given n and m
distance = 1;
HashSet visited = {}
Iterator A = teams, B = teams;
While (A != B) {
if (!visited.contains(*A) && !visited.contains(*B)) {
visited.insert(*A), visited.insert(*B);
}
if (visited.count() == n) {
visited.clear();
B = A + ++distance;
}
A++;
B += distance;
}``````

I am also convinced there is a way to solve this problem in O(nm) time in the general case using a dynamic programming. That I haven't figured out. I will edit my answer if I do.

Comment hidden because of low score. Click to expand.
0
of 0 vote

You can solve this is O(n^2) time using a hashset and a circular linked list, using the follower approach. I am positive you can solve this problem in O(nm) time through another solution, I'm just having a hard time seeing this.

``````given n and m
HashSet visited = {}
distance = 1;
Iterator A = teams, B = teams
while (A != B) {
if (!visited.contains(*A) && !visited.contains(*B)) {
visited.insert(*A);
visited.insert(*B);
}
if (visited.count() == n) {
visited.clear();
} else {
A++;
B += distance;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

You can solve this is O(n^2) time using a hashset and a circular linked list, using the follower approach. I am positive you can solve this problem in O(nm) time through another solution, I'm just having a hard time seeing this.

``````given n and m
HashSet visited = {}
distance = 1;
Iterator A = teams, B = teams
while (A != B) {
if (!visited.contains(*A) && !visited.contains(*B)) {
visited.insert(*A);
visited.insert(*B);
}
if (visited.count() == n) {
visited.clear();
} else {
A++;
B += distance;
}
}``````

Comment hidden because of low score. Click to expand.
0

you are right, another solution is divide and conquer approach.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi i implemented this using C#. I used two dementional Array and List<int>.
Two Dementional Array record team and match day. For instance a[0,1] = 2 mean Team1,Team2 will play at day2. a[1,2] = 3 means Team2,Team4 will play at day3.

``````public class Util
{
private int[,] gamedays = new int[4, 4];

public void Init()
{
for(int i = 0; i < gamedays.GetLength(0);i++)
{
for(int j = 0; j < gamedays.GetLength(1);j++)
{
gamedays[i, j] = 0;
}
}
}

public void SetSchedule()
{
for (int i = 0; i < gamedays.GetLength(0); i++)
{
List<int> days = new List<int>() { 1, 2, 3 };
for (int j = 0; j < gamedays.GetLength(1); j++)
{
// cannot match itself.
if (i == j)
{
continue;
}

if(gamedays[i,j] == 0)
{
bool bSet = false;
int index = 0;
while (bSet == false)
{
int day = days[index];
bool bocuppied = Ocuppied(i, j, day);
if (bocuppied == false)
{
gamedays[i, j] = day;
gamedays[j, i] = day;
bSet = true;
days.Remove(day);
}
else
{
if(index+1 < days.Count)
{
index++;
}
else
{
break;
}
}
}
}
else
{
days.Remove(gamedays[i, j]);
}
}
}
Display();
}

private bool Ocuppied(int i,int j,int day) {
// validate if the opponent team already is ocuppied by other team
for (int x = i - 1; x >= 0; x--)
{
if (gamedays[x, j] == day)
{
return true;
}
}
return false;
}

private void Display()
{
for (int i = 0; i < gamedays.GetLength(0); i++)
{
for (int j = 0; j < gamedays.GetLength(1); j++)
{
Console.Write(" " + gamedays[i, j]);
}
Console.WriteLine();
}
}

public static void Main()
{
Util util = new Util();
util.SetSchedule();
}
}``````

Comment hidden because of low score. Click to expand.
0

for(){... for(){... if(){... while(){... if(){}else{...if(){}else{}}}} } }

Comment hidden because of low score. Click to expand.
0
of 0 vote

c# implementation.
"Divide & Conquer" approach.
result is a 2D array, where each element is the team with which team "i" must have play on day "j".

``````using System;
using System.Collections.Generic;

namespace Tournament {

class Program {

static private int[,] GetSchedule( int teams ) {

if ( teams == 2 ) { return new [,] { { 1 }, { 0 } }; }

var halfTeams = teams / 2;
var tmpRes = GetSchedule( halfTeams );

var days = teams - 1;
var halfDays = days / 2;
int[,] res = new int[ teams, days ];

for ( int i = 0; i < teams; i++ ) {
for ( int j = 0; j < days; j++ ) {
var val = ( i < tmpRes.GetLength( 0 ) && j < tmpRes.GetLength( 1 ) ) ? tmpRes[ i, j ] : 0;
res[ i, j ] = val;
}
}

for ( int i = halfTeams; i < teams; i++ ) {
for ( int j = 0; j < halfDays; j++ ) {
res[ i, j ] = res[ ( i - halfTeams ), j ] + halfTeams;
}
}

var list1 = new List<int> { halfTeams };
var list2 = new List<int> { halfTeams - 1 };

for ( int j = 0; j < halfDays; j++ ) {
list1.Add( res[ 0, j ] + halfTeams );
list2.Add( res[ teams - 1, j ] - halfTeams );
}

Action<int, List<int>> action = (i, lst) => {
int t = 0;
for ( int j = halfDays; j < days; j++ ) {
res[ i, j ] = lst[ t ];
t++;
}
var first = lst[ 0 ];
lst.RemoveAt( 0 );
};

for ( int i = 0, j = teams - 1; i < halfTeams; i++, j-- ) {
action.Invoke( i, list1 );
action.Invoke( j, list2 );
}

return res;
}

static void Main( string[] args ) {
int n = 2;
var teams = (int)Math.Pow( 2, n );
var res = GetSchedule( teams );
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public void computeMatches(int teams, int days)throws InvalidInputException
{

if(teams%2!=0||days<=0)
{
throw new InvalidInputException();
}

int teamMatchesPerDay=(teams/days)+(teams%days);
int maxRotation=teams-1;
int rot=0;
int dayIdx=1;
int[] teamArr=new int[teams];
for(int i=0;i<teamArr.length;i++)
{
teamArr[i]=i+1;
}
while(rot<maxRotation)
{
for(int i=0;i<teamMatchesPerDay && rot<maxRotation;i++)
{
rotate(1,teams-1,teamArr);
rotate(2,teams-1,teamArr);
rot++;
System.out.println("day " + dayIx+":" + Arrays.toString(teamArr));//Neighboring values represent teams playing one another.

}
dayIdx++;
}

}

private void rotate(int start,int end,int[] arr)
{
int i=start;
int j=end;
while(i<j)
{
int tmp=arr[i];
arr[i++]=arr[j];
arr[j--]=tmp;
}

}

//Time: O(n^2) where n is the number of teams. Space is O(n) where n is the number of teams.``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple Solution:

Team = {T1, T2, T3, T4}. i will play index 0 to index 1 and index 2 to index 3 in all 3 games. but my team array have to change in some way. So

First game => Team = {T1, T2, T3, T4}
Second game => Team = {T1, T3, T2, T4}
Third game => Team = {T1, T4, T2, T3}

if you look the above array carefully, you will see that index 1 value is swapped with index 1+loop counter value.
play index 0 to index 1 and index 2 to index 3, you get the correct output.

Algo:

``````int j = 1;
for(int i = 1 : 3)  // 3 is total # of games{
swap(team[i], team[j]);
game<i-1, <team, team>>      // game should be a multi map
game<i-1, <team, team>>
}``````

any comment is appreciated

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
#include <string>
using namespace std;
int main() {
const int TEAM_COUNT = 4;
const string TEAMS[TEAM_COUNT] = {"A","B","C", "D"};
for (int i = 0; i < TEAM_COUNT; ++i) {
int day = 1;
for (int j = i+1; j < TEAM_COUNT; ++j) {
cout << TEAMS[i] << " vs " << TEAMS[j] << " DAY " << day << endl;
day++;
}
}
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

This is wrong as day 1 would then be team 0 vs team 1 and team 1 vs team 2ans so on... One team can't play more then 1 game a day

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
#include <string>
using namespace std;
int main() {
const int TEAM_COUNT = 4;
const string TEAMS[TEAM_COUNT] = {"A","B","C", "D"};
for (int i = 0; i < TEAM_COUNT; ++i) {
int day = 1;
for (int j = i+1; j < TEAM_COUNT; ++j) {
cout << TEAMS[i] << " vs " << TEAMS[j] << " DAY " << day << endl;
day++;
}
}
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Create a circular link list=> O(n) time and space complexity
2. copy all element to array=> (O(n)) time and space complexity
3.ScheduleGame()
{
for(i=0;i<arraySize/2;i++)
{
StartGame(array[i],array[n-1-i];
}
}
4.RoatateClock wise the circular link list by keeping 1 st element fix=> o(n)
5. Repete 2 to 4 steps arraySize-2 times more

Comment hidden because of low score. Click to expand.
-1
of 1 vote

public void printTeamPlays()
{
int[][] m=new int;
//teams 1,2,3,4
m=1;
m=2;
m=3;
m=4;

System.out.println ("day 1: " + m + "vs" + m + "," + m + "vs" + m);
System. out.println("day 2:" + m + "vs" + m +", " + m + "vs" + m);
System.out.println("day 3:" + m + "vs" m + "," + m + "vs" + m);
}

Comment hidden because of low score. Click to expand.
0

@divm01986 - it shouldn't be hardcoded..the solution should be made generic. Sorry for not including this in the questions.

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.

### 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.