Microsoft Interview Question
Country: India
@Anonymous,
Can you please clarify the question?
What does
"each subset has one and only one matching number from any other subset"
mean?
1,2,3 has no matching elements with 7,8,9..Can you please clarify?
Hi,
In general { 1 2 3} and {1 2 4} both are subsets from a given set of {1, 2......9}, right?
here, there are two elements common in both these subsets.
but I think the question is about forming only such subsets where only one element is common.
Please get back if you need more clarification.
Thanks...
I guess the question is wrong, it should be "between any two subsets there can be at-most one common element", else the subsets {1,2,3} {7,8,9} has nothing in common.
That doesn't work either, because (1, 2, 3 ) and (1, 5, 9) and (1, 4, 7) all have 1, which is shared. What am I missing?
Here is another observation that I got
Consider the n*n as a matrix
1 2 3
4 5 6
7 8 9
The possible solutions are ;
a) All rows iterated
b) All columns iterated
c) Both diagonals iterated
d) Spiral or '7' shaped elements from all 4 corners
ie
1,6,8
3,4,8
9,4,2 (which is 2,4,9)
7,6,2 (which is 2,6,7)
In case of n=4, the similar structure will reveal all the elements.
The sort of '7' shaped path will have 4 elements
Please correct me if this is wrong.
Nice observation! But what is the math theory behind it? Why this way can find the max combination?
matrix is a great idea, but I think you miss something
for N=4,
1, 2, 3, 4
5, 6, 7, 8
9,10,11,12
13,14,15,16
besides the '7' shaped path you mentioned, there are '=' shaped path,
3,8,9,14; 2,5,12,15;
both '7' shaped and '=' shaped path are diagonal path.
actually, think about this
when we take a line (could be horizontal/vertical/diagonal/etc) with x elements out of matrix (x<=N), we still need to find (N-x) elements, which should be just another line, to the opposite direction of current line.
think the center of our matrix as a mirror, try to match two pararal diagonal lines with x and y elements, x+y = N.
look at this N=5 matrix
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
we have 4 full diagonal lines (x=5,y=0) , like 1,7,13,19,25; etc
4 (x=4, y=1 ) pair , like 2,8,14,20,21
4 (x=3, y=2 ) pair, like 3,9,15,16,22
no need to continue.
correct me if I'm wrong
I agree on the '7' shape thing, for dimensions higher than 3, 7 shape does not work, or in other words '7' shape looses its meaning (becomes too ambiguous)..
The idea is, there are 2*N (for NxN matrix ) +2 trivial solutions (N columns, N rows, and two diagonals), and we have to figure out other solutions.. which are zones of N numbers, and which do not share more than 1 points with any other existing solutions....
And this can be solved recursively, when we do.....
for each element of first row ( or first column)...figure out disjoint non-trivial solutions of minor matrix of that element.
* minor matrix of a given element is defined as - sub-matrix formed by excluding that row and that column.
#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;
}
n=4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
1 5 9 13
2 6 10 14
3 7 11 15
4 8 12 16
1 6 11 16
2 7 12 13
3 8 9 14
4 5 10 15
1 7 9 15
2 8 10 16
3 5 11 13
4 6 12 14
1 8 11 14
2 5 12 15
3 6 9 16
4 7 10 13
for n =4 ...ur code generate these 20 pattern...
and if u see....ammong these one is....
3 7 11 15
and one is
1 7 9 15
and these two has two element in common....:(:(
while as mentioned in problem ...there should not be more then one element commom in any of two subsets.
Please help me understand the question : if it is max. subsets (n*n+n)
why can't we just take one element of 1 to n^2 common for all ...then we have to fill n^2-1 elements in the subsets of size n where 1 element we have already places => n-1 elements ... (n^2-1)/(n-1)=(n+1) subsets that is less than (n*n+n) subsets..
e.g.
1,2,3,4,5,6,7,8,9
1,2,3
1,4,5
1,6,7
1,8,9
int permutationTest(int n){
int i, j, k;
printf("n=%d\n", n);
for(i=1; i<=n*n;) {
printf("\n");
for (int j=1; j<=n; j++) {
printf("%3d",i++);
}
}
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
printf("\n%3d%3d", i+1, n+j+1);
for (k=2; k<n; k++) {
int s = (i*(k-1)+j)%n + 1;
printf("%3d", k*n+s);
}
}
}
return 0;
}
for ( int i=0; i<n;i++)
for (int j=n; j<2*n;j++)
for (int k=2*n;k<3*n;k++)
cout<<"("<<a[i]<<" "<<a[j]<<" "<<a[k]<<")"<<endl;
Ashish, I'm afraid your solution is incorrect.
Please notice that when you are iterating using the k variable, you are printing the unchanged a[i] and a[j] which results in multiple subsets with a[i] and a[j].
BugoK
sqw, I too got the same logic, but that expression(s=i*(k-1)+j..) was bit difficult for me to frame. can you explain how you derived that expr?
ram,
1) treat the n*n numbers as an 2D array;
2) to generate a new subset, we need to pick one of number from each row to form a new sequence.
3) starting row 2, we need to pick up a number in a way that would have only one from each other subsets:
i * (k-1) + j
where j is the offset, i*(k-1) is the step distance.
your code is not returning the correct result for n = 4
n=4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
1 5 9 13
1 6 10 14
1 7 11 15
1 8 12 16
2 5 10 15
2 6 11 16
2 7 12 13
2 8 9 14
3 5 11 13
3 6 12 14
3 7 9 15
3 8 10 16
4 5 12 15
4 6 9 16
4 7 10 13
4 8 11 14
Duplicates from the above subsets:
1 5 9 13
3 5 11 13
5 and 13 are repeating in both the subsets!
There are other sets those have two elements common!
based on the question, if i can write the arrayas
1 2 3 1 2
4 5 6 4 5
7 8 9 7 8
then any parallel lines formed by three elements break the requirement of having exactly one match as they will have none.
so the only possible solution for this is
n+1 such combinations
1 2 3
1 4 7
1 5 9
3 5 7
any other combination will break the rule of having exactly one match with "any other set"
Is the solution provided in the question correct? I do see few subsets which don't have anything in common.
sub-set 1 and sub-set 12,
sub-set 1 and sub-set 11
sub-set 3 and sub-set 10
sub-set 4 and sub-set 6.
sub-set 2 and sub-set 5.
sub-set 7 and sub-set 10.
sub-set 11 and sub-set 12.
What I noticed is that for every sub-set listed has one sub-set not matching anything in this list.
This sub-set from 1-12 seems to be arranging of elements into n*n matrix.
sub-set 1 = 1,2,3
sub-set 2 = 1, 4, 7
sub-set 3 = 1, 5, 9
sub-set 4 = 1, 6, 8
sub-set 5 = 2, 5, 8
sub-set 6 = 2, 4, 9
sub-set 7 = 2, 6, 7
sub-set 8 = 3, 6, 9
sub-set 9 = 3, 5, 7
sub-set 10 = 3. 4, 8
sub-set 11 = 4, 5, 6
sub-set 12 = 7, 8, 9
Matrix approach is good.
Here is the formula that I derived by hit and trial...
for n = 1, there are two such sets, (1), (1).
for n = 2, there are 2*2+f(1) = 6...
e.g. for
12
34
12, 34,13,24 + (1) paired with disjoint sets of minor matrix of 1, (2) paired with disjoint sets of minor matrix of (2)..
*Minor matrix of (aij) = matrix formed by deleting rows and columns corresponding to aij..
Similarly, for n=3
e.g.
123
456
789
there are 2*n rows and column sets.. for others, we do recursively..
(1) paired with disjoint sets of minor matrix {(5,6), (8,9))..
(2) paired with disjoint sets of minor matrix {(4,6),(7,9)}
(3) paired with disjoint sets of minor matrix {(4,5),(7,8)}
So, all inner loops of recursive calls have to return disjoint sets.. only outer multiplication will allow for for 1 duplicate.... when pairing with outer elements
Another key thing while returning disjoint sets.. no two elements should not be on same row or column, otherwise it will intersect with row/column zones...
So, recurrence relation becomes
F(n) = 2*n + n*(n-1)
= 2n + n^2 - n = n^2 + n.
So, when taking cross product of outer elements with returned subsets of sub problem..
only consider non-trivial solutions (non rows/columns), which form disjoint sets and no two points are on same row/column.
Choosing minor matrix for inner solution ensures that when taking product, no inner subset would lie on same row/column..
Here's my solution, using matrix...
#include <iostream>
#define N 100
using namespace std;
int temp[N][N];
int main() {
int n = 3;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
temp[i][j] = i + 1 + j * n;
}
}
int count = 1;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cout << temp[i][j] << " ";
}
cout << endl;
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cout << temp[j][i] << " ";
}
cout << endl;
}
for(int i = 0; i < n; i++) {
cout << temp[i][i] << " ";
}
cout << endl;
for(int i = 0; i < n; i++) {
cout << temp[i][n-1-i] << " ";
}
cout << endl;
return 0;
}
Hi frnds,
- Anonymous May 16, 2012I was wondering first of all how this (n*n) + n possible ways.
After few trails I could get it and hence want to share.
Please correct if anything wrong:
Given n * n numbers, say for example n=3, means given numbers are
1 2 3 4 5 6 7 8 9.
1) make it into n blocks
( 1 2 3) (4 5 6) ( 7 8 9)
2) for every one element from 1st set, select another number from second set
this fills up two positions - possible n*n ways
third position is a sort of determined
something like - ( 1 4) ( 1 5) (1 6)
no option for placing third element, have to place it directly
1 4 7 is selected, we cannot say 1 4 8 now which is invalid
hence, n * n subsets formed
2) repeat the same with second element from first set, but this time the third set rotated once
so it will be ( 1 2 3) ( 4 5 6) (9 7 8)
follow similar procedure.....
at the end, each block themselves are a subset that is n subsets again
so all togethere (n * n) + n sets
Please correct guys, if my understanding is wrong.
Thanks