Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
Update :
The time has to be changed to : C(n, ceil(n/2))!
I guess it would be :
C( C(n , ceil(n/2)) , n) //this is wrong , look at the update
Because for each line in the matrix you can choose n/2 out of n places for FALSE values and you have 'n' lines of matrix.
static ArrayList<Boolean[]> lines = new ArrayList<Boolean[]>();
static void matrix_choice(int n){
Boolean[] line = new Boolean[n];
for (int i = 0 ; i < line.length ; i++)
line[i] = true;
choice_make_line((int)Math.ceil((double)n/2) , line , 0 , 0);
Boolean[][] matrix = new Boolean[n][n];
for (int i = 0 ; i < n ; i++)
for (int j = 0 ; j < n ; j++)
matrix[i][j] = true;
choice_make_matrix(matrix , 0 , 0);
}
static void choice_make_matrix(Boolean[][] matrix , int array_index , int line_index){
if (line_index == matrix.length){
for (int i = 0 ; i < matrix.length;i++)
System.out.println(Arrays.toString(matrix[i]));
System.out.println("------------------------------------------------------------------");
}
if (array_index == lines.size())
return;
matrix[line_index] = lines.get(array_index);
choice_make_matrix(matrix , array_index+1 , line_index+1);
choice_make_matrix(matrix , array_index+1 , line_index);
}
static void choice_make_line(int m , Boolean[] line , int index, int chosen_so_far){
if (chosen_so_far == m){
lines.add(line.clone());
return;
}
if (line.length - index < m - chosen_so_far)
return;
line[index] = false;
choice_make_line(m , line , index + 1, chosen_so_far+1);
line[index] = true;
choice_make_line(m , line , index + 1, chosen_so_far);
return;
}
But for n=2, there are only two combinations.
0 1 and 10
1 0 01.
but C(C(n,ceil(n/2)),n)=C(C(2,1),2)=C(2,2)=0.
The first part is permutation question. First, lets' consider only the row
n item, with p=ceil(n/2) value zero and and (n-p) value one. The permutation formula is k = n! / (n-p)! p!
Where k is number of possible arrangement on the n item. Now, we consider the n x n matrices. Given set of k items (possible rows), we want to choose n items to from the matrices. This is a permutation with k! / (k-n)!
It is easy for the first part, the second part is a back-tracking algorithm with recursive. Tricky to code.
#include <cstdlib>
#include <iostream>
#include<vector>
#include<conio.h>
using namespace std;
int p;
int main(int argc, char *argv[])
{
int n=4;
int a[4][4]={0};
for(int s=0;s<n;)
{
for(int i=0,k=s;i<n;i++)
{ p=0;
for(int j=0;j<n;j++)
{ if(p<2) {
a[i][(k+p)%4]=1;
p++; }
}
k=(k+1)%4;
}s=(s+1);
for(int x=0;x<n;x++)
{ for(int y=0;y<n;y++)
{ cout<<a[x][y];
a[x][y]=0;
}cout<<endl;
}
cout<<endl;
}
getch();
return 0;
}
I think the answer involves realizing that such matrices must be comprised of 'complimentary' rows. For example, for n, we have the possible rows:
- Anonymous July 15, 20131 1 0 0
0 0 1 1
1 0 1 0
0 1 0 1
1 0 0 1
0 1 1 0
Any matrix must be made up of two of these complimentary pairs. The order doesn't matter.
So we have 3 ways of choosing complimentary pairs (1,2 or 1,3 or 2,3) and then we have 4! ways of ordering these pairs, for a total of 3 * 24 = 72 different matrices. To generate them, iterate through the different permutations of complimentary pairs and permutations.
In general, the number of permutations is n! where n is the number of rows/cols, and the number of complimentary pairs is n choose n/2 (so in this case 4 choose 2 = 6).
That's my guestimate anyhow =p