## Google Interview Question Software Engineer / Developers

• 0

Given an N x M matrix having only positive values, we have to nullify the matrix i.e make all entries 0.
We are given two operations
1) multiply each element of any one column at a time by 2.
2) Subtract 1 from all elements of any one row at a time

Find the minimum number of operations required to nullify the matrix.
Note: no range of input was given

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
8
of 10 vote

key to solve this problem:
i) do NOT use operation 2(O2) on any row that has "1" in it till all the member in that row is "1".
ii) use operation 1(O1) on any col that has "1" in it and then O2 to prevent case one from happening.

algorithm to solve it:
s1)search for the minimum value in row i, let it be a. Record all index where a occur;
s2)do O2 for (a-1) times to row i;
s3)check if any column has a value greater than "1"
true:
s4)do O1 for each column indexed in step 1(s1). go to s1
false:
s5)do O2 then move to next row(i++)

for example of a row:
s1: 4 17 11
s2: 1 14 8
s3->4: 2 14 8
s1~2: 1 13 7
s3->4: 2 13 7
s1~2: 1 12 6
s3->4: 2 12 6
.
.
.
s1~2: 1 7 1
s3->4: 2 7 2
s1~2: 1 6 1
s3->4: 2 6 2
.
.
.
s1~2: 1 2 1
s3->4: 2 2 2
s1~2: 1 1 1
s3->5: 0 0 0

there are two improvement method I can think of atm.
1. instead of doing O1 once every loop, we can do it several times if the 2nd min larger than 4. which means: instead of doing (1 17 1) -> (2 17 2) -> (1 16 1)->...->(1 2 1), we do (1 17 1)-> (16 17 16)->(1 2 1).
1st method need 16+16=32operations, while 2nd method need 4+15+1+1=21operations.
2. work multiple row at the same time, prioritize upper row. e.g. O1 operation will only used when upper row needed(sometimes it might be the same column needed by lower row).

basic method operations needed:
1. (min-1)+2*(2nd min-min)+2*(3rd min - 2nd min) + .....
2. update value changed by O1 in all previous row operation, go to 1.
3. till last row, then sum all.

Comment hidden because of low score. Click to expand.
0

I can do it in 37 steps:

1 [[0 0 0] [0 0 0]]
2 [[1 1 1] [0 0 0]]
3 [[2 2 2] [0 0 0]]
4 [[3 3 3] [0 0 0]]
5 [[4 4 4] [0 0 0]]
6 [[5 5 5] [0 0 0]]
7 [[6 6 6] [0 0 0]]
8 [[7 7 7] [0 0 0]]
9 [[8 8 8] [0 0 0]]
10 [[9 9 9] [0 0 0]]
11 [[10 10 10] [0 0 0]]
12 [[11 11 11] [0 0 0]]
13 [[12 12 12] [0 0 0]]
14 [[12 12 12] [1 1 1]]
15 [[12 12 12] [2 2 2]]
16 [[12 12 12] [3 3 3]]
17 [[12 12 12] [4 4 4]]
18 [[12 12 12] [5 5 5]]
19 [[12 12 12] [6 6 6]]
20 [[12 12 12] [7 7 7]]
21 [[12 12 12] [8 8 8]]
22 [[12 12 12] [9 9 9]]
23 [[12 12 12] [10 10 10]]
24 [[12 12 12] [11 11 11]]
25 [[12 12 12] [12 12 12]]
26 [[6 12 12] [6 12 12]]
27 [[6 12 6] [6 12 6]]
28 [[7 13 7] [6 12 6]]
29 [[8 14 8] [6 12 6]]
30 [[8 14 8] [7 13 7]]
31 [[8 14 8] [8 14 8]]
32 [[4 14 8] [4 14 8]]
33 [[2 14 8] [2 14 8]]
34 [[1 14 8] [1 14 8]]
35 [[2 15 9] [1 14 8]]
36 [[3 16 10] [1 14 8]]
37 [[4 17 11] [1 14 8]]

Comment hidden because of low score. Click to expand.
0

what if the test case is
[4, 17, 11]
[1000, 10, 10]

And in your algorithm, you double the element 1000 several time which makes efficience worse

We should handle the raws with largest difference first

Comment hidden because of low score. Click to expand.
0

How does your solution guarantee minimum number of operations?

Comment hidden because of low score. Click to expand.
0

I can do it in only 21 steps
4, 17, 11
2x: 8, 17, 11
2x: 16, 17, 11
-5: 11, 12, 6
2x: 11, 12, 12
-10: 1, 2, 2
2x: 2, 2, 2
-2: 0, 0, 0

When the row has a max of 17, it means we should do at least 17 decrements. in my algorithm, # of decrements are exactly 17, and the 2x operations are minimum:
step1: Find the max column of the row.
step2: Keep doing 2x on all the other columns while they haven't exceeded the max column.
step3: Decrement the row and goto step1

Optimization: When the max of a row is M and min of the row is m, and we know that 2xm will exceed M, then you need to decrement the row as many times as 2m-M so that you can apply 2x on the min column because
after k decrements, M and m become M-k and m-k, now you can make min column 2x. i.e 2(m-k) <= 2(M-k) => k=2m-M

Comment hidden because of low score. Click to expand.
1
of 1 vote

With a little thought it is easy to see that it suffices to write a subroutine that will make all entry in a specific row all zero.
In this subroutine repeatedly do the following
a) apply operation 1) to columns having 1 in the specific row
b) apply operation 2) to the specific row
Entries in the specific row who are 1 will oscillate 1-2-1-2-1-2
Entries in the specific row who are greater than 1 will each decrease by 1 continuously.
Hence at some point all entries will be 1. Now apply 2) a final time and all entries in the specific row are 0.
Rinse, repeat.

Comment hidden because of low score. Click to expand.
0
of 0 vote

How large are the inputs?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Are you sure you are not missing something? How are negative values going to be 'brought up' to zero if only operation allows are:

1) multiply each element of any one column at a time by 2.
2) Subtract 1 from all elements of any one row at a time

which both will decrease their values.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Any -ve number can't be reduced to 0 using given operation. Is the problem statement correct ?

Comment hidden because of low score. Click to expand.
0

Yeah, what is with the silly problem statement?

Comment hidden because of low score. Click to expand.
0

The problem makes sense. Integers have bounded memory and multiplication is left shifting by 1. So the absolute simplest solution is multiple all numbers by 2 till all the ones get left shifted out and you are left with only 0.

Comment hidden because of low score. Click to expand.
0

@axecapone: Don't be silly.

Comment hidden because of low score. Click to expand.
0

Even if we have 0 anywhere with at least 1 non zero value in the matrix then also solution is impossible. Problem must be having all values +ve.

Comment hidden because of low score. Click to expand.
0

it assumes for positive values only.

Comment hidden because of low score. Click to expand.
0

@Anonymous: Why don't you give the code below a try?

``````public class AnonymousThinksIAmSilly {
public static void main(String[] args) {
int a = 767;
while(a != 0) {
a = a*2;
System.out.println(a);
}
}``````

Comment hidden because of low score. Click to expand.
0

@axecapone:

Don't be silly.

Comment hidden because of low score. Click to expand.
0

@Anonymous, REALLY you don't be silly..The discussion above clearly states that do -1 operation until the value of minimum element in a row goes down to "1". Once that happens multiply the column with value "1" by 2 so, value never goes to 0 or negative.. It's a valid problem statement..

Comment hidden because of low score. Click to expand.
0

@Algos: Don't be silly.

Comment hidden because of low score. Click to expand.
0
of 0 vote

You have make that point...

Comment hidden because of low score. Click to expand.
0
of 0 vote

I am sorry for the mistake in problem statement.
I have corrected it now
Thank you

Comment hidden because of low score. Click to expand.
0

for each element in column A[j], A[j]= 2*lcm(elements in A[i])/A[i][j]

How can you do this? Can you elaborate?
for ex [ 1 2 3] , lcm=6, how can you convert 2 to 6 by the operations given above? Maybe in [1 2 4], its possible. If I got your algo correctly...

Sure. Essentially what I am saying is, we want to transform every element in each position to 2 times the lcm. We can't just transform it to lcm, because the question REQUIRE us to *2 to every column, so there are some cases, say if lcm is odd, that aiming at lcm will fail. e.g. [ 3 5 9], lcm = 45, but can you transform every element to 45 by multiply some different constant multiplication of 2 to every column? NO!

I think it might be more clear if I write for each element in column A[j], A[j]= 2*lcm(elements in A[i])/A[i][j] with the third variable k.

..i..
..j..
...
for k=i to M
A[k]= A[k][j]*2*lcm(elements in A[i])/A[i][j]

what it basically doing is, if k=i, then set it to 2lcm (since A[i][j]*2lcm/A[i][j]= 2lcm), so we know row i will be eliminated if we substract 2lcm fron row i.
The other rows below will be multiplied accordingly. But that does not matter, since our loop invariant is every row above i are all 0's.

My algorithm guarantee that every element will be eliminated eventually.

[1 2 3] lcm=6
for A[0]=1, 2*lcm/A[0]=2*6/1=12
for A[1]=2, 2*lcm/A[1]=2*6/2=6
for A[2]=3, 2*lcm/A[2]=2*6/3=4

Now let each element times their corresponding product we calculated above:
1*12=12; 2*6=12; 3*4=12

eliminate!

May be a real matrix?
[1 2 3]
[4 5 6]
[7 8 9]

for A[0]=1, 2*lcm/A[0]=2*6/1=12
for A[1]=2, 2*lcm/A[1]=2*6/2=6
for A[2]=3, 2*lcm/A[2]=2*6/3=4

Now times 12 to every element in column 0, 6 to column 1, 4 to column 2:
[12 12 12]
[48 30 24]
[84 48 36]

row 1 -12:
[0 0 0]
[48 30 24]
[84 48 36]

I think you got the idea. repeated doing this... eliminate row2, then3.

Comment hidden because of low score. Click to expand.
0

Ok simpler query:
How can you transform 1 to 12 (2*6 or 2*lcm) , when the only operation feasible here is multiplying by 2 , so in first step your matrix is
[1,2,3]
and then multiplying by 2 to reach 12:
[2,2,3]
[4,2,3]
[8,2,3]
[16,2,3]
I know if you get [12,12,12] you'll be done.
But:
1- Is that possible to get [12,12,12] here (just by multiplying and no subtraction) , because you're doing that in last step ( after getting [12,12,12] ) anyways.
2- Even if you somehow get [12,12,12] somehow, by intervening subtractions in between multiplications, would that be minimum no. of steps?

I believe [1,2,3] would follow this ->
[1,2,3]
[2,2,3]
[1,1,2]
[2,1,2]
[2,2,2]
[1,1,1]
[0,0,0]

Every transformation takes 1 step, hence min no. of steps = 6

PS: You can't do normal column operations here, like multiplying whole column by 12 or 6 (like you've done above). You can just multiply it by 2.

Comment hidden because of low score. Click to expand.
0

[1,2,3]
[2,2,3]
[1,1,2]
[2,1,2]
[2,2,2]
[1,1,1]
[0,0,0]

I think you may misunderstood the question, we have to multiply 2 to WHOLE column, so if it's a 3*M matrix, to eliminate first row, you take much more than 6 steps in reality. Am I clear?

Also, if there are M*N elements, it takes O(MN) time to read the data, so O(MN) is the best we can get, and mine is with O(MN) time and O(M) space.

Comment hidden because of low score. Click to expand.
0

Rows are vertical? Columns are horizontal? :|

for a 1x3 matrix (NxM matrix)
[1,2,3]
there is one row, and 3 columns. And am multiplying WHOLE column by 2 , when am doing
[2,2,3]

It shouldn't matter actually, when you can take transpose of it as an example :/

Comment hidden because of low score. Click to expand.
0
of 0 vote

this can't be done. for example:

0 ... 1 .. 0
0 ... 0 .. 0
...............
0............0

Comment hidden because of low score. Click to expand.
0

0 is not a positive integer.

Comment hidden because of low score. Click to expand.
0

Very easy then.

//row 1-M will all be 0's after iteration
for i=0 to M
//now row i are all 0's after this iteration
for j=0 to N
for each element in column A[j], A[j]= 2*lcm(elements in A[i])/A[i][j]
for 2*lcm(elements in A[i]) times, we -1 from row i

Comment hidden because of low score. Click to expand.
0

for each element in column A[j], A[j]= 2*lcm(elements in A[i])/A[i][j]

How can you do this? Can you elaborate?
for ex [ 1 2 3] , lcm=6, how can you convert 2 to 6 by the operations given above? Maybe in [1 2 4], its possible. If I got your algo correctly...

Comment hidden because of low score. Click to expand.
0

My algorithm takes O(M*N*N) times, but can be easily reduced to O(M*N) time if we use an extra N sized array to keep track of multiplication should applied to each rows below current i when we are running this program. the next time another j becoming currently eliminating row, we'll multiply the constant we stored in our array before doing eliminating operations.

Comment hidden because of low score. Click to expand.
0

I'd like to see a clearer description of this algorithm.

Comment hidden because of low score. Click to expand.
0

posted above. don't reply here anymore.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Are we allowed to check the elements in the array or does the problem require a generalized answer for any N*M matrix with any input and no access to them but the operations in the statement. Please clarify.

Comment hidden because of low score. Click to expand.
0
of 2 vote

I think:
Answer for [1 2 3] is 6
Answer for [1 7 13] is 18

I can't generalize anything so far. Hope these test cases lead you somewhere.

Comment hidden because of low score. Click to expand.
0

1 [[0 0 0]]
2 [[1 1 1]]
3 [[2 2 2]]
4 [[1 2 2]]
5 [[1 1 2]]
6 [[2 2 3]]
7 [[1 2 3]]

1 [[0 0 0]]
2 [[1 1 1]]
3 [[2 2 2]]
4 [[3 3 3]]
5 [[4 4 4]]
6 [[5 5 5]]
7 [[6 6 6]]
8 [[7 7 7]]
9 [[8 8 8]]
10 [[9 9 9]]
11 [[10 10 10]]
12 [[5 10 10]]
13 [[6 11 11]]
14 [[7 12 12]]
15 [[7 6 12]]
16 [[8 7 13]]
17 [[4 7 13]]
18 [[2 7 13]]
19 [[1 7 13]]

Comment hidden because of low score. Click to expand.
0

i can do [1 7 13] in 17 steps

- 1 7 13
1 2 7 13
2 4 7 13
3 3 6 13
4 6 6 13
5 5 5 12
6 4 4 11
7 3 3 10
8 2 2 5
9 1 1 4
10 2 1 4
11 4 1 4
12 4 2 4
13 4 4 4
14 3 3 3
15 2 2 2
16 1 1 1
17 0 0 0

Comment hidden because of low score. Click to expand.
0
of 0 vote

One ans: sizeof(the positive qty in bits) * No. of cols.
Lets assume that size of the qty here is 32 bits. Multiplying by 2 is left shifting by 1. After 32 left shifts all integers in first column will be 0 ( it is given as +ve integer). Repeat for all cols.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Another improvement in the num of operations will be to write a func. that returns true when all column elems hv turned to 0. So, one does not need to left shift by size of integer always. Only left shift till the func. returns true

Comment hidden because of low score. Click to expand.
0
of 0 vote

i couldnt understand the question .... how can multiply help in nullifying the matrix

Comment hidden because of low score. Click to expand.
0
of 0 vote

Multiply by 2 is shift1 once left. Integer has 32 bits at most.

If A(i,j) is >= 32, it is faster to multiply multiply by 2 till it becomes 0 than repeatedly subtracting 1

If A(i, j ) < 32, faster to use subtraction

{Nullify(A, rowBegin, colBegin, rowEnd, colEnd)
{
if (no elements) return;

if (just one element),
{
if number > 32,
use as many shifts needed
else
use subtraction
return;
}

if there is a column c that has > 32,
{
use shifts to make the entire column 0s;
Now you have 2 smaller 2D arrays atmost and call Nullify recursively.
return;
}

find row r with min value in the entire array
{
subtract 1 from that row until it becomes 0;
This leaves 4 smaller 2D arrays at most. Call Nullify recursively
}

}}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Try this code, for bigger matrices use long int matrix in suitable places. although this code is not the optimized one. This is just a process to nullify the matrix. Please tell anyone if you can find some way to optimize it.

``````#include <stdio.h>

#define SIZE 5
#define width SIZE
#define height SIZE

static int mul_no,dec_no;

int mat[height][width]={	{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}};

col_mul(int col_no)
{
int i=0;mul_no++;
while(i!=height)mat[i++][col_no]*=2;
print();printf("Multiplied Col no %d by 2\n",col_no);		//comment this line to remove unwanted prints
}
row_dec(int row_no,int amt)
{
int i=0;dec_no+=amt;
while(i!=width)mat[row_no][i++]-=amt;
print();printf("Decresed row no %d by %d\n",row_no,amt);	//comment this line to remove unwanted prints
}
print()
{
int i,j;
for(i=0;i<height;i++)
{for(j=0;j<width;j++) printf("%02d ",mat[i][j]);
printf("\n");}
printf("\n\n");
}
int max_row(int row_no)
{
int max=0;int i=0;
for(i=0;i<width;i++)
if(max<mat[row_no][i])max=mat[row_no][i];
return max;
}
int min_row(int row_no)
{
int min=max_row(row_no);int i=0;
for(i=0;i<width;i++)
if(min>mat[row_no][i])min=mat[row_no][i];
return min;
}
dec_below_row(int row_no)	// not calling this might make the arrays cross the limits of integer
{
int i,j;
for(i=row_no+1;i<height;i++)
for(j=0;j<(min_row(i)-1);j++)row_dec(i,1);
}
nullify_row(int row_no)
{
int i=0;
while(max_row(row_no)!=1){
dec_below_row(row_no);
while(min_row(row_no)!=1){row_dec(row_no,min_row(row_no)-1);}
int max=max_row(row_no);
for(i=0;i<width;i++)
while(mat[row_no][i]<=max/2)col_mul(i);
}
row_dec(row_no,1);// All rows now have only 1 s
}
nullify_mat()
{
int i=0;
for(i=0;i<height;i++)nullify_row(i);
}
main()
{
mul_no=dec_no=0;
print();
nullify_mat();
print();
printf("No of Multiplication %d No of Decrements %d\n",mul_no,dec_no);
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.