Microsoft Interview Question Software Engineers
Country: United States
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 = {}
List<Pair> answer = {}
CircularLinkedList teams = list of teams as circular linked list.
Iterator A = teams[0], B = teams[1];
While (A != B) {
if (!visited.contains(*A) && !visited.contains(*B)) {
visited.insert(*A), visited.insert(*B);
answers.add(new Pair(*A, *B));
}
if (visited.count() == n) {
visited.clear();
A = head();
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.
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 = {}
CircularLinkedList teams = linked list of all teams.
List<Pair> answer;
distance = 1;
Iterator A = teams[0], B = teams[1]
while (A != B) {
if (!visited.contains(*A) && !visited.contains(*B)) {
answer.add(new Pair(*A, *B));
visited.insert(*A);
visited.insert(*B);
}
if (visited.count() == n) {
visited.clear();
A = head();
B = head() + ++distance;
} else {
A++;
B += distance;
}
}
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 = {}
CircularLinkedList teams = linked list of all teams.
List<Pair> answer;
distance = 1;
Iterator A = teams[0], B = teams[1]
while (A != B) {
if (!visited.contains(*A) && !visited.contains(*B)) {
answer.add(new Pair(*A, *B));
visited.insert(*A);
visited.insert(*B);
}
if (visited.count() == n) {
visited.clear();
A = head();
B = head() + ++distance;
} else {
A++;
B += distance;
}
}
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();
}
}
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 );
lst.Add( first );
};
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 );
Console.ReadLine();
}
}
}
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.
Simple Solution:
Team[4] = {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[4] = {T1, T2, T3, T4}
Second game => Team[4] = {T1, T3, T2, T4}
Third game => Team[4] = {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[0], team[1]>> // game should be a multi map
game<i-1, <team[2], team[3]>>
}
any comment is appreciated
#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;
}
#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;
}
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
public void printTeamPlays()
{
int[][] m=new int[2][2];
//teams 1,2,3,4
m[0][0]=1;
m[1][0]=2;
m[0][1]=3;
m[1][1]=4;
System.out.println ("day 1: " + m[0][0] + "vs" + m[1][0] + "," + m[0][1] + "vs" + m[1][1]);
System. out.println("day 2:" + m[0][0] + "vs" + m[0][1] +", " + m[1][0] + "vs" + m[1][1]);
System.out.println("day 3:" + m[0][0] + "vs" m[1][1] + "," + m[0][1] + "vs" + m[1][0]);
}
This is round robin tournament algorithm. Here is my implementation :
- EPavlova January 06, 2016void 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[1]; for (int i = 1; i < teams - 1; i++) { int pr = cycle[i+1]; cycle[i+1] = temp; temp = pr; } cycle[1] = temp; } }