Cracking The Coding Interview/Q 1.6

From Software Engineers Wiki
Jump to: navigation, search

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

Answer

#define MATRIX_N        7

void rotate_matrix(uint32_t matrix[MATRIX_N][MATRIX_N])
{
        int start_rotate_index = 0;
        int end_rotate_index = MATRIX_N - 1;
        int max_rotate_index = MATRIX_N / 2;
        uint32_t tmp;
        int i, s, e, c;

        while (start_rotate_index < max_rotate_index) {
                s = start_rotate_index;
                e = end_rotate_index;
                c = e - s;
                for (i = 0; i < c; ++i) {
                        tmp = matrix[s][s + i];
                        /* (left, top) <= (left, bottom) */
                        matrix[s][s + i] = matrix[e - i][s];
                        /* (left, bottom) <= (right, bottom) */
                        matrix[e - i][s] = matrix[e][e - i];
                        /* (right, bottom) <= (right, top) */
                        matrix[e][e - i] = matrix[s + i][e];
                        /* (right, top) <= saved (left, top) */
                        matrix[s + i][e] = tmp;
                }
                ++start_rotate_index;
                --end_rotate_index;
        }
}

And a test program.

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

        for (i = 0, p = (uint32_t *) matrix, value = 0; i < MATRIX_N * MATRIX_N; ++i, ++p)
                *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_N * MATRIX_N; ++i, ++p) {
                printf("%2d ", *p);
                if ((i % MATRIX_N) == MATRIX_N - 1)
                        printf("\n");
        }
}

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

        init_matrix(matrix);

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

        rotate_matrix(matrix);

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

        return 0;
}

Test result with matrix 7x7

Initial matrix:
 0  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 26 27 
28 29 30 31 32 33 34 
35 36 37 38 39 40 41 
42 43 44 45 46 47 48 
Rotated matrix:
42 35 28 21 14  7  0 
43 36 29 22 15  8  1 
44 37 30 23 16  9  2 
45 38 31 24 17 10  3 
46 39 32 25 18 11  4 
47 40 33 26 19 12  5 
48 41 34 27 20 13  6 

Test result with matrix 10x10

Initial matrix:
 0  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 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 64 65 66 67 68 69 
70 71 72 73 74 75 76 77 78 79 
80 81 82 83 84 85 86 87 88 89 
90 91 92 93 94 95 96 97 98 99 
Rotated matrix:
90 80 70 60 50 40 30 20 10  0 
91 81 71 61 51 41 31 21 11  1 
92 82 72 62 52 42 32 22 12  2 
93 83 73 63 53 43 33 23 13  3 
94 84 74 64 54 44 34 24 14  4 
95 85 75 65 55 45 35 25 15  5 
96 86 76 66 56 46 36 26 16  6 
97 87 77 67 57 47 37 27 17  7 
98 88 78 68 58 48 38 28 18  8 
99 89 79 69 59 49 39 29 19  9 
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox