Amazon Interview Question Software Engineer / Developers
I tried your approach and did not get the expected result. I have seen this algo elsewhere but this is the result I get
(according to your solution)
1111
1020
1000
Can you please explain clearly?
>>> 1. Traverse the matrix once. If you find '1' at a[i][j], mark a[0][i] and a[j][0] as '2'
I think, it should be, If you find '1' at a[i][j], mark a[i][0] and a[0][j] as '2'
Wouldnt the above algorithm be time of O(3*n*m)?
Traversing the matrix: O(n*m)
Conditionally filling each row (worst case): O(n*m)
Conditionally filling each column (worst case): O(n*m)
A possible solution is you can have 2 1-d arrays, row[n] and col[m],all entries in the two arrays initialized to 0 .Now traverse the 2-d array and find all the positions where you have a 1,if a[1][2] has a 1 then in row[1] change the value from '0' to '1' and do the same in col[2].This way the 2 1-d arrays will have the indexes of the row and col where the entry happened to be a 1 in the original array.
Now
for (i = 0; i < n; i++) {
for ( j = 0; j < m; j++) {
if ((row[i] == 1 || column[j] == 1)) {
a[i][j] = 1;
}
}
This has O(n*m) complexity.
}
Don't have to specify a special row or column to keep the 1's.
Scan the matrix row by row, if there is no 1 in some row, use the space
in that row i.
Scan the matrix column by column, if there is a 1 in a column j, mark row i, column j
by 1.
fill the matrix row by row except row i, if there is a 1, fill the whole row by 1.
go through row i, if there is 1 in some column, fill the whole column by 1.
Lets allocate a bitmap of size n*m. Each bit in the bitmap will represent "visited" row or column. For eg for a 4 * 4 matrix, allocate a 8 bit, bitmap. The first 4 bits represent rows, and last for 4 bits represent columns.
So before I mark any row, I check if that row has been visited before. That way I control the time complexity.
#define Visted 1
bitmap[N*M] = 0 ;
for (n=0;n<N;n++)
for (m=0;m<M;m++)
{
if a[n,m]=1
if !bitmap[n]
{
bitmap[n]=Visited
for (k=0; k<M; k++,a[n,k]=1) // Mark entire Row
}
if !bitmap[m]
{
bitmap[m]=Visited
for (k=0; k<N; k++,a[k,m]=1) // Mark entire Column
}
}
use the first row to record columns needed to be set as all 1's
use the first column to record rows needed to be set as all 1's
1. scan through the matrix, if (a[x][y]==1) {a[0][y]=1; a[x][0]=1}; time O(m*n)
2. scan through the matrix again, for a[x][y], if (a[0][y]==1 || a[x][0]==1) a[x][y] = 1; time O(m*n)
overall time O(m*n)
auxiliary space O(1)
not if we scan matrix backwards in second pass
code:
public class RowColumnSetter
{
public static void setRowColumns(int[][] orig, int n, int m)
{
int i, j;
System.out.println("Original Matrix");
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
System.out.print(orig[i][j] +" ");
System.out.println("");
}
for(i=1;i<n;i++)
for(j=1;j<m;j++)
if(orig[i][j]==1)
{
orig[0][j]=1;
orig[i][0]=1;
}
System.out.println("Intermediate Matrix");
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
System.out.print(orig[i][j] +" ");
System.out.println("");
}
for(i=n-1;i>=0;i--)
for(j=m-1;j>=0;j--)
{
if(orig[i][0]==1 || orig[0][j]==1)
orig[i][j]=1;
}
System.out.println("New Matrix");
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
System.out.print(orig[i][j] +" ");
System.out.println("");
}
}
public static void main(String[] args)
{
int n=4,m=4;
int[][] initial = new int[n][m];
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
initial[i][j]=0;
initial[0][0]=1;
initial[0][3]=1;
initial[1][2]=1;
RowColumnSetter.setRowColumns(initial, n, m);
}
}
I think, we need some special cases too........Like this solution will fail if there is 0 at (1,1) and either 0th row or column has 1 at some other position.........I think this solution will work in other cases..........
Very nice solution........
jialin's solution will fail with the case below.
0 0 0 0
0 0 1 1
0 0 0 1
After 1st scan it becomes
0 0 1 1
1 0 1 1
1 0 0 1
After 2nd scan it becomes
1 1 1 1
1 1 1 1
1 1 1 1
But, what we really expect is
0 0 1 1
1 1 1 1
1 1 1 1
@kunalgaind, I agree with you, to handle this case, we can use two more values. If there is a 1 at the 0th row but not at 0th column, we assign the value 2. Similarly, if there is a 1 at the 0th column but not at the 0th row, we assign the value 3. In the second pass we can make the row or the column all 1 accordingly.
I took a different approach to this problem.
This is what I do
Block 1: Number of iterations = m * 2n
--
For all rows
If a column in a particular row has a 1 set a flag
If the flag is set
Mark all 0's in the row as 2
--
Block 2: Number of Iterations = n * 2m
--
For all columns
If a row in a particular column has a 1 set a flag
If the flag is set
mark all the 0 in the column as 2
--
Block 3 Number of iterations = n * m
--
For all the Rows and columns
If a row and column = 2 then mark it as 1
--
The overall complexity is O(m*n).
public class MarkUpArray{
public static void main(String[] args){
int [][]array = {{1,0,0,1},{0,0,1,0}, {0, 0, 0, 0},{0,0,0,0}};
// Scan all rows -- Block 1
for (int i = 0; i < array.length; i++){
boolean flag = false;
for(int j = 0; j < array[i].length && flag == false; j++){
if (array[i][j] == 1)
flag = true;
}
if (flag)
for (int j = 0; j < array[i].length; j++){
if (array[i][j] != 1)
array[i][j] = 2;
}
}
// Scan all columns -- Block 2
for (int i = 0; i < array[0].length; i++){
boolean flag = false;
for (int j = 0; j < array.length && flag == false; j++){
if (array[j][i] == 1)
flag = true;
}
if (flag)
for (int j = 0; j < array.length; j++){
if (array[j][i] != 1)
array[j][i] = 2;
}
}
// Block - 3
for (int i = 0; i < array.length; i++){
for(int j = 0; j < array[i].length; j++){
if (array[i][j] == 2)
array[i][j] = 1;
}
}
// Print Array
for (int i = 0; i < array.length; i++){
for(int j = 0; j < array[i].length; j++){
System.out.print(array[i][j] + " ");
}
System.out.println();
}
}
}
jialin solution will work with the few additional steps / modifications:
0.(pre-step) save information about if row0 has '1' and column0 has '1'
1. save in row0/column0 info about having at least one '1' in all rows/columns except row0 and column0 as described above
2. go through the array again except in row0 and column0 and set 1/0 in all elements
3.(post step) set corner element array[0][0] to 1 if row0 had '1' || column0 had '1'
Use bit array to store the matrix. Say a 32x32 matrix uses 32 unsigned int.
Take the OR of all int, give that to those zero rows (= 0 as int), all rows dealt with; make the nonzero rows FFFF, all columns dealt with. O(n).
Each row of 32 bits is an int, so a nonzero int means there are 1 bits, and must be made FFFF; and the a column has 1, it is passed to other rows by OR.
So it should be
Take the OR of all rows, give that to those zero rows, all columns dealt with; make the nonzero rows FFFF, all rows dealt with. O(n).
You can't set the value as 2 according to Amazon. Here is some working code. O(1) space, O(m*n) time.
#define MAX 100
void printMatrix(int val[MAX][MAX], int rows, int cols){
int r, c;
for(r=0;r<rows;++r) {
for(c=0;c<cols;++c) {
if(val[r][c]) printf("1 ");
else printf("0 ");
}
printf("\n");
}
}
void makeMatrixValues(int val[MAX][MAX], int rows, int cols){
int vr00, vc00, r, c;
if(!(rows*cols)) return;
vr00 = vc00 = val[0][0];
for(r=0;r<rows;++r) if(val[r][0]) vr00=1;
for(c=0;c<cols;++c) if(val[0][c]) vc00=1;
for(r=0;r<rows;++r) {
for(c=0;c<cols;++c) {
if(val[r][c]) { val[0][c]=1; val[r][0]=1; }
}
}
for(r=1;r<rows;++r) {
for(c=1;c<cols;++c) {
if(val[r][0]) val[r][c]=1;
if(val[0][c]) val[r][c]=1;
}
}
if(vr00) {
for(r=0;r<rows;++r) val[r][0]=vr00;
}
if(vc00) {
for(c=0;c<cols;++c) val[0][c]=vc00;
}
}
#define r 3
#define c 4
int main() {
int val[MAX][MAX] = {
{ 0, 0, 1, 0 },
{ 0, 0, 0, 0 },
{ 1, 0, 0, 0 },
};
printf("Original: \n");
printMatrix(val,r,c);
makeMatrixValues(val,r,c);
printf("Final: \n");
printMatrix(val,r,c);
}
You can't set the value as 2 according to Amazon. Here is some working code. O(1) space, O(m*n) time.
#define MAX 100
void printMatrix(int val[MAX][MAX], int rows, int cols){
int r, c;
for(r=0;r<rows;++r) {
for(c=0;c<cols;++c) {
if(val[r][c]) printf("1 ");
else printf("0 ");
}
printf("\n");
}
}
void makeMatrixValues(int val[MAX][MAX], int rows, int cols){
int vr00, vc00, r, c;
if(!(rows*cols)) return;
vr00 = vc00 = val[0][0];
for(r=0;r<rows;++r) if(val[r][0]) vr00=1;
for(c=0;c<cols;++c) if(val[0][c]) vc00=1;
for(r=0;r<rows;++r) {
for(c=0;c<cols;++c) {
if(val[r][c]) { val[0][c]=1; val[r][0]=1; }
}
}
for(r=1;r<rows;++r) {
for(c=1;c<cols;++c) {
if(val[r][0]) val[r][c]=1;
if(val[0][c]) val[r][c]=1;
}
}
if(vr00) {
for(r=0;r<rows;++r) val[r][0]=vr00;
}
if(vc00) {
for(c=0;c<cols;++c) val[0][c]=vc00;
}
}
#define r 3
#define c 4
int main() {
int val[MAX][MAX] = {
{ 0, 0, 1, 0 },
{ 0, 0, 0, 0 },
{ 1, 0, 0, 0 },
};
printf("Original: \n");
printMatrix(val,r,c);
makeMatrixValues(val,r,c);
printf("Final: \n");
printMatrix(val,r,c);
}
It does not help when you spit out that much code without any explanation. I did not go through your code because jialin already gave the best solution which I am sure you cannot beat.
Well, we can try this:
- Solution November 30, 20091. Traverse the matrix once. If you find '1' at a[i][j], mark a[0][i] and a[j][0] as '2'
2. Traverse the first row. If a[0][i] = 2, set the ith row (fill with 1)
3. Traverse the first col. If a[j][0] = 2, set the jth col.