Amazon Interview Question
Software Engineer / DevelopersThe question not that easy as it seems.
@Hiren - your solution may seem obvious one but it is not.
Let say I have this matrix
0 2 3
0 2 3
0 2 2
Now for sure you will make the first column and row 0 and next time you wont consider those rows and cols again, but the problem is row 2 and 3 both initially had 0s so even those rows should be zero.
1. Keep a bitmap of size (m + n).
2. Scan the matrix.
3. If you find 0, set the respective 2 bits in the bitmap (one for row and one for column).
4. Now use the information in the bitmap to write zeros in the expected rows and columns in the matrix.
int array[m][n];
int x=0; int row[m];
int y=0; int row[n];
for(int i=0;i<m;i++){
for(int j=0;j<m;j++){
if(array[i,j]==0){
row[x++] = i; col[y++]=j;
}
}
}
for(int a=0;a<x;a++){
for(int z=0;z<n;z++){
array[row[a],z] = 0;
}
}
for(int b=0;a<y;b++){
for(int w=0;w<m;w++){
array[w,col[b]] = 0;
}
}
Not sure if this is the most efficient way thou.. Feel free to comment
public static void changeMatrix(int[][] input, int row, int col)
{
//scan through the matrix to get 0
for(int i=0;i<=row;i++)
{
for(int j=0;j<=col;j++)
{
if(input[i][j]==0)
{
convertRowandCol(input,i,j,row,col);
}
}
}
}
private static void convertRowandCol(int[][] input, int i, int j, int row,
int col) {
for(int x=0;x<col;x++)
{
input[i][x]=0;
}
for(int y=0;y<row;y++)
{
input[y][j]=0;
}
}
comlexity : o(m*n) for scanning the matrix
o(m +n) for again changing matrix.
Not efficient but simple.
// find the positions of 0s
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (matrix[i][j] == 0) {
row[rowCount] = i;
rowCount++;
col[colCount] = j;
colCount++;
}
}
}
int i = 0;
int rowNo = 0, colNo = 0;
while (row[i] != -1 && col[i] != -1) {
rowNo = row[i];
colNo = col[i];
// make upper column 0
for (int r = 1; r <= rowNo; r++) {
matrix[rowNo - r][colNo] = 0;
}
// make lower column 0
for (int r = 1; r < (height - rowNo); r++) {
matrix[rowNo + r][colNo] = 0;
}
//make the row 0
for (int c = 0; c < width; c++) {
matrix[rowNo][c] = 0;
}
i++;
}
row string and col string with AND of all variables per row or column.
2nd round make it 0.
if its row in row and col in col for 1, make it 1
otherwise keep 0
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
namespace ConsoleApplication3
{
class test
{
static int row = 0;
static int col = 0;
public static void Main(string[] args)
{
int[,] a = { { 11, 2, 3, 1 }, { 4, 1, 6, 5 }, { 3, 6, 2, 4 } };
row = a.GetLength(0);
col = a.GetLength(1);
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
if (a[i, j] == 1)
{
markarraywithzero(a, i, j);
break;
}
}
}
}
public static void markarraywithzero(int[,] a, int rowitem, int colitem)
{
for (int i = 0; i < col; i++)
{
a[rowitem, i] = 0;
}
for (int i = 0; i < row; i++)
{
a[i, colitem] = 0;
}
}
}
}
//C#
static void setZeros(int[,] _arr, int _iMax, int _jMax)
{
int[] rows = new int[_arr.GetLength(0)];
int[] colums = new int[_arr.GetLength(1)];
for (int i = 0; i < _iMax; i++)
{
for (int j = 0; j < _jMax; j++)
{
if (_arr[i, j] == 0)
{
rows[i] = 1;
colums[j] = 1;
}
}
}
for (int i = 0; i < _iMax; i++)
{
for (int j = 0; j < _jMax; j++)
{
if ((rows[i] == 1 || colums[j] == 1))
{
_arr[i, j] = 0;
}
}
}
}
import java.util.ArrayList;
public class MultiplyExceptSelf {
public static void main(String[] args) {
int arr[][] = { {1,0,1,0},
{1,0,1,0},
{1,0,0,0},
{0,0,0,0}
};
ArrayList<Integer> xcor = new ArrayList<Integer>();
ArrayList<Integer> ycor = new ArrayList<Integer>();
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(arr[i][j] == 1){
if(xcor.contains(i)){
}
else{
xcor.add(i);
}
if(ycor.contains(j)){
}
else{
ycor.add(j);
}
}
}
}
System.out.println(xcor);
System.out.println(ycor);
for(int i=0;i<xcor.size();i++)
{
for(int j=0;j<4;j++){
arr[xcor.get(i)][j] = 1;
}
}
for(int i=0;i<ycor.size();i++)
{
for(int j=0;j<4;j++){
arr[j][ycor.get(i)] = 1;
}
}
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
System.out.print(arr[i][j]);
}
System.out.println("\n");
}
}
}
- Hiren January 12, 2010