Facebook Interview Questions/Q 1

From Software Engineers Wiki
Jump to: navigation, search

Given an array of integers. Modify the array by moving all the zeros to the end (right side). The order of the other elements doesn't matter.

Answer

Swap any non-zero element with zero-element. Since the algorithm doesn't need to be stable (keep the order), to minimize number of move, scan from the right, and fill the zero element with rightmost non-zero element.

void move_zero_to_end(int *parray, int size)
{
        int *pzero;
        int *pnonzero;

        /* find last non-zero element */
        for (pnonzero = parray + size - 1; pnonzero >= parray; --pnonzero)
                if (*pnonzero)
                        break;
        /* if no non-zero element, nothing to do */
        if (pnonzero < parray)
                return;
        /* find zero element and swap */
        for (pzero = pnonzero - 1; pzero >= parray; --pzero) {
                if (*pzero == 0) {
                        *pzero = *pnonzero;
                        *pnonzero-- = 0;
                }
        }
}

Test program:

void print_array(int *parray, int size)
{
        while (size-- > 0)
                printf("%d ", *parray++);
        printf("\n");
}

int main(void)
{
        int samples[] = { 3, 7, 9, 0, 11, 0, 15, 21, 0, 99 };
        int size = sizeof(samples) / sizeof(samples[0]);

        print_array(samples, size);
        move_zero_to_end(samples, size);
        print_array(samples, size);

        return 0;
}

Test result:

3 7 9 0 11 0 15 21 0 99 
3 7 9 21 11 99 15 0 0 0 

Reference

Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox