|
148. Given a binary matrix of N X N of integers.......
Microsoft Interview Questions and Answers
(Continued from previous question...)
148. Given a binary matrix of N X N of integers.......
Question:
Given a binary matrix of N X N of integers , you need to return only unique rows of binary arrays
eg:
0 1 0 0 1
1 0 1 1 0
0 1 0 0 1
1 1 1 0 0
ans:
0 1 0 0 1
1 0 1 1 0
1 1 1 0 0
maybe an answer:
problem contaions only 0 and 1 so convert each row to corresponding decimal number
like
convert 0 1 0 0 1 = 9;
1 0 1 1 0 = 22;
use an array of 0 to pow(2,N) intialy set whole array -1
and go to each row and set the row num at that pos ex arr[9]= 1(row num) arr[22] =2 (row num)
now traverse the array and if value at pos!= -1 then print that row
time complexty O(N^2) space complexity 2^N
maybe an answer2:
The above algorithms have O(N*N) time complexity in all cases. I'll try to describe my approach with O(N*N) in the worst case.
Well, the idea is to analyse each column and group current identical rows.
First, we analyse the first column. All 0-s will be moved to group G0 and the 1-s to G1. The algorithm continues until there are no groups with more than one row in it or we reach the N-th column. On the k-th step we analyse the k-th column and only groups with more than one row in it. For such a group we will replace it with a two new ones. At any time empty groups must be removed. Getting one row from each group we will get the resultant unique rows. Here is an example:
N=5.
columns: 1 2 3 4 5
---------
row 1: | 0 1 0 0 1
row 2: | 1 0 1 1 0
row 3: | 0 1 0 0 1
row 4: | 1 1 1 0 0
row 5: | 1 1 0 1 1
step 1: G0={1,3}; G1={2,4,5}.
step 2: G0 => (G00={empty}, G01={1,3}); G1 => (G10={2}, G11={4,5}).
step 3: G01 => (G010={1,3}, G011={empty}); G10={2}; G11 => (G110={5}, G111={4}).
step 4: G010 => (G0100={1,3}, G0101={empty}); G10={2}; G110={5}; G111={4}.
step 5: G0100 => (G01000={empty}, G01001={1,3}); G10={2}; G110={5}; G111={4}.
Result groups: G01001={1,3}; G10={2}; G110={5}; G111={4}.
Unique rows: 1 (or 3), 2, 5, 4.
(Continued on next question...)
Other Interview Questions
| 