Cracking The Coding Interview/Q 1.7

From Software Engineers Wiki
Jump to: navigation, search

Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0.

Answer

#define MATRIX_M        10
#define MATRIX_N        8

void propagate_zero_matrix(uint32_t matrix[MATRIX_N][MATRIX_N])
{
        int rows_with_zero[MATRIX_N] = { 0 };
        int cols_with_zero[MATRIX_M] = { 0 };

        int row, col;
        uint32_t *p;

        p = (uint32_t *) matrix;

        for (row = 0; row < MATRIX_N; ++row) {
                for (col = 0; col < MATRIX_M; ++col) {
                        if (*p == 0) {
                                rows_with_zero[row] = 1;
                                cols_with_zero[col] = 1;
                        }
                        ++p;
                }
        }

        p = (uint32_t *) matrix;

        for (row = 0; row < MATRIX_N; ++row) {
                for (col = 0; col < MATRIX_M; ++col) {
                        if (rows_with_zero[row] || cols_with_zero[col])
                                *p = 0;
                        ++p;
                }
        }
}

And a test program.

void init_matrix(uint32_t matrix[MATRIX_M][MATRIX_N])
{
        uint32_t *p;
        uint32_t value;
        int i;

        for (i = 0, p = (uint32_t *) matrix, value = 1; i < MATRIX_M * MATRIX_N; ++i, ++p) {
                if ((random() & 0x1f) == 0) /* 1/32 chance */
                        *p = 0;
                else
                        *p = value++;
        }
}

void print_matrix(uint32_t matrix[MATRIX_N][MATRIX_N])
{
        uint32_t *p;
        int i;

        for (i = 0, p = (uint32_t *) matrix; i < MATRIX_M * MATRIX_N; ++i, ++p) {
                printf("%2d ", *p);
                if ((i % MATRIX_M) == MATRIX_M - 1)
                        printf("\n");
        }
}

int main(void)
{
        uint32_t matrix[MATRIX_M][MATRIX_N];

        srandom(time(NULL));
        init_matrix(matrix);

        printf("Initial matrix:\n");
        print_matrix(matrix);

        propagate_zero_matrix(matrix);

        printf("Zero propagated matrix:\n");
        print_matrix(matrix);

        return 0;
}

And the test result with 10 column, 8 row matrix.

Initial matrix:
 1  2  3  4  5  6  7  8  9 10 
11  0 12 13 14 15 16 17 18 19 
20 21 22 23 24 25 26 27 28 29 
30 31 32 33 34 35 36 37 38 39 
40 41 42 43 44 45 46 47 48 49 
50 51 52 53 54 55 56 57 58 59 
60 61 62 63  0 64 65 66 67 68 
69 70 71 72 73 74 75 76 77 78 
Zero propagated matrix:
 1  0  3  4  0  6  7  8  9 10 
 0  0  0  0  0  0  0  0  0  0 
20  0 22 23  0 25 26 27 28 29 
30  0 32 33  0 35 36 37 38 39 
40  0 42 43  0 45 46 47 48 49 
50  0 52 53  0 55 56 57 58 59 
 0  0  0  0  0  0  0  0  0  0 
69  0 71 72  0 74 75 76 77 78 
Initial matrix:
 1  2  3  4  5  6  7  8  9 10 
11  0 12 13 14 15 16 17 18 19 
20 21 22 23 24 25 26 27 28 29 
30 31 32 33 34 35 36 37 38 39 
40 41 42 43 44 45 46 47 48 49 
50 51 52 53 54 55 56 57 58 59 
60 61 62 63  0 64 65 66 67 68 
69 70 71 72 73 74 75 76 77 78 
Zero propagated matrix:
 1  0  3  4  0  6  7  8  9 10 
 0  0  0  0  0  0  0  0  0  0 
20  0 22 23  0 25 26 27 28 29 
30  0 32 33  0 35 36 37 38 39 
40  0 42 43  0 45 46 47 48 49 
50  0 52 53  0 55 56 57 58 59 
 0  0  0  0  0  0  0  0  0  0 
69  0 71 72  0 74 75 76 77 78 
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox