Google Interview Question Software Engineer / Developers
0of 0 votesGiven 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
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]]
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
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
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.
Any -ve number can't be reduced to 0 using given operation. Is the problem statement correct ?
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.
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.
@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);
}
}
@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..
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.
for your example:
[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.
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.
[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.
this can't be done. for example:
0 ... 1 .. 0
0 ... 0 .. 0
...............
0............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
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...
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.
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.
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]]
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
}
}}
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);
}
key to solve this problem:
- Ares.Luo.T on September 21, 2012 Edit | Flag Replyi) 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.