Microsoft Interview Question Software Engineer / Developers
Country: United States
Interview Type: Written Test
This is a good observation.
First combinations are obtained as rows and columns in the 2-D array. All other can be obtain as solution for the 'chessmen arrangement on the chessboard' broblem.
But in this case they should be not queens but rooks (beat each other only in vertical and horizontal directions). All other principles are the same.
Each subset does not have to match every other subset. Each subset must only be able to match at most 1 number from a given subset. ie. you will see that there are no other subsets where 7 and 8 are in the same subset or a 7 and 9 or an 8 and 9 other than in set 12.
The followup question is exactly what you're getting to:
Once you have the sub-sets described in this problem, then improve the algorithm to have one subset match exactly 1 number with every other subset.
It seems question itself has the answer. Arrange the numbers in a 3 X 3 matrix (2 D array) and take each row, column and diagonal numbers.
Haha cool question. Ramesh's answer was partially correct. Here is the code I came up with.
The first "n" sets would be 1..n,n+1..2n,2n+1..3n,...,..n*n. From then, the fun starts.
1. The next lists of sets would follow this pattern.
2. Set n+1 = {1,1+n+1,1+2n+1...,1+n(n-1)+1}
In the set, if any value crosses n*n then mod the value with "n" and fill the bucket which is empty.
What I mean by bucket is - (1...n) is bucket - 0, (n+1...2n) is bucket 1 etc... so there are n buckets.
Fortunately math works for this solution :)
Here is a working code.
//If you want to return the set's itself, you can do that as well
public int ReturnTotalSetsCount()
{
// First n sets
// For n = 3 - add the base case to the set
// 1 2 3
// 4 5 6
// 7 8 9
for (int i = 0; i < n; i++)
{
List<int> temp = new List<int>();
for (int j = i * n; j < i * n + n; j++)
{
temp.Add(j + 1);
}
temp.Sort();
_sets.Add(temp.ToArray());
}
// Corner cases
if (n == 1) return 1;
if (n < 0) return -1;
if (n == 0) return 0;
//Filling buckets and finding the empty bucket
for (int incrementBy = n; incrementBy < 2 * n; incrementBy++)
{
for (int i = 1; i <= n; i++)
{
int[] buckets = new int[n];
InitializeBuckets(buckets); //Initializes all value of array to -1
for (int j = 0; j < n; j++)
{
int value = (j*incrementBy) + i;
if (value <= n * n)
{
buckets[(value - 1) / n] = value;
}
else
{
int leftOutBucket = FindEmptyBucket(buckets); //Finds the one bucket which still has a value of -1
buckets[leftOutBucket] = (leftOutBucket * n) + (value % n);
}
}
Array.Sort(buckets);
_sets.Add(buckets);
}
}
PrintAll();
return _sets.Count;
}
Point number 2 should be like this.
2. Set n+1 = {1 + 0(n),1+1(n),1+2(n)...,1+(n-1)(n)}
3. Set n+2 = {1 + 0(n+1),1+1(n+1),1+2(n+1)...,1+(n-1)(n+1)}
4. Set n+3 = {1 +0(n+2)........................}
...
till 2*n (Start from n and end at 2n-1)
Now we did it for value 1. We need to do the same for value 2,3....,n.
Substituting n=4 in the above equation
2. Set n+1 = {1, 5, 9, 13}
3. Set n+2 = {1, 6, 11, 16}
4. Set n+3 = {1, 7, 13, 19%4}
2 & 4 have 1 & 13 common.
#include<stdio.h>
int n;
int main()
{
int i, j, shift, a, b;
printf("\nn=");
scanf("%d",&n);
for(i=1;i<=n*n;)
{
j=0;
printf("\n");
while(j<n)
{
j++;
printf("%3d",i);
i++;
}
}
for(shift=0; shift<n; shift++)
{
for(i=1;i<=n;i++)
{
printf("\n%3d",i);
a=i;
for(j=1;j<n;j++)
{
a=a+n+shift;
if(a>(n+n*j))
{
b=a%n;
a=j*n+b;
}
printf("%3d",a);
}
}
}
return 0;
}
Looks okay. C++ code
{{
#include <iostream>
#include <vector>
#include <boost/bind.hpp>
#include <boost/lambda/lambda.hpp>
template<typename T>
inline void vtos(std::vector<T> &v) {
std::ostringstream s;
std::for_each(v.begin(), v.end(), s << boost::lambda::_1 << ' ');
std::cout << s.str() << std::endl;
}
using namespace std;
int main(void) {
int n;
cin >> n;
vector< vector<int> > v(n, vector<int> (n)), soln;
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
v[i][j] = n*i+j+1;
vector<int> v1;
for (int add=0; add<n; add++) {
soln.push_back(v[add]);
for (int i=0; i<n; i++) {
v1.clear();
for (int j=0; j<n; j++)
v1.push_back(v[(j+add)%n][i]);
sort(v1.begin(), v1.end());
soln.push_back(v1);
}
}
for_each(soln.begin(), soln.end(), boost::bind(&vtos<int>, _1));
}
}}
well, for even number input, your solution will fail. subset will have 2 common numbers when shift = 2,3 ... < n
I was trying to analyze and believe that the number of subsets can't be n squared + n when 'n' is even.
yoursandmyideas.wordpress.com
Hi Sunil Singhal,
Consider there are n^2 by n^2 matrix. there are n^2 elements in the diagonal so we can leave those.
Every time we create a set of n items we mark a '1' in the matrix at i,j if the number (i,j) is associated. So we set (i,j) and (j,i) to 1. At the end this matrix will have 1 in all the places and no 1 will be overwritten.
Total no of places = n^2*n^2 - n^2
Subtracting n^2 to remove the diagonal.
Each time we create a set of n element it puts n(n-1) 1's in the matrix. So the total no of sets which will put 1 in all the places is
(n^4 - n^2) / n(n-1)
= n^2(n^2 - 1) / n(n-1)
= n(n+1)(n-1) / (n-1)
= n(n+1)
= n^2 + n
So for any n, the no. of sets is n^2 + n.
Thanks & regards
arc
Here is my approach :
placing the numbers in the matrix as below :
1 2 3
4 5 6
7 8 9
print the rows : 123 , 456, 789
print the columns: 147, 258, 369
now for the rest of the numbers, there is some kind of a pattern for columns with (1, 2 &3 )
Its permutation of 123(columns )
Example :
for i from 1 to 3 // standard rows
for j in 1 3 2 // taking one of the permute (columns)
print matrix[i][j] // print 168
So get the all permutations of 123 in a list (for example). Do the above for all the elements in the list.
Similar to 8 queens problem for a 1,2,.....9 2D matrix
- Ankur May 16, 2012