Facebook Interview Questions/Q 2

From Software Engineers Wiki
Jump to: navigation, search

We have an array of objects A and an array of indexes B. Reorder objects in array A with given indexes in array B. Do not change array A's length. For example,

A = [ C, D, E, F, G ];
B = [ 3, 0, 4, 1, 2 ];

After sort

A = [D, F, G, C, E ];

Answer #1

If there is additional array that it can use, the sort will be simple. But here let's try to sort in-place.

This is algorithm is fairly simple. It begins with first entry, and the order. Since first element needs to move to the new order, swap current and the element in the new order. Do this until it finds a item with new order 0. Repeat this with each elements.

void swap(int *arr, int left, int right)
{
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
}

void reorder(int *pdata, int *porder, int size)
{
        int i;

        for (i = 0; i < size; ++i) {
                while (porder[i] != i) {
                        swap(pdata, i, porder[i]);
                        swap(porder, i, porder[i]);
                }
        }
}

Test program:

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

int data_array[] = { 9, 3, 1, 2, 8, 0, 7, 6, 4, 5 };
int order_array[] = { 9, 3, 1, 2, 8, 0, 7, 6, 4, 5 };

int main(void)
{
        int size = sizeof(data_array) / sizeof(data_array[0]);
        reorder(data_array, order_array, size);
        print_array(data_array, size);

        return 0;
}

Test result:

0 1 2 3 4 5 6 7 8 9 

With above example, there were 40 reads, and 24 writes.

A python code that does same thing.

def swap(arr, left, right):
        arr[left], arr[right] = arr[right], arr[left]

def reorder(data_array, order_array):
        for i in range(len(order_array)):
                while order_array[i] != i:
                        swap(data_array, order_array[i], i)
                        swap(order_array, order_array[i], i)

def main():
        data_array = [ 9,3,1,2,8,0,7,6,4,5 ]
        order_array = [ 9,3,1,2,8,0,7,6,4,5 ]
        reorder(data_array, order_array)
        print data_array

main()

Answer #2

This algorithm is more about chain reaction. In above example,

int order_array[] = { 9, 3, 1, 2, 8, 0, 7, 6, 4, 5 };

the item at index 0 is moved to index 9. If finds that index 9 should move to index 5, and index 5 to index 0. Now index 0 has right element, and move to the next element. This may have less memory access.

void reorder(int *pdata, int *porder, int size)
{
        int i;
        int data_old, order_old;
        int data_new, order_new;
        int old_idx, new_idx;

        for (i = 0; i < size; ++i) {
                if ((new_idx = porder[i]) != i) {
                        old_idx = i;
                        data_old = pdata[i];
                        order_old = porder[i];

                        for (;;) {
                                data_new = pdata[new_idx];
                                order_new = porder[new_idx];
                                pdata[new_idx] = data_old;
                                porder[new_idx] = order_old;

                                if (new_idx == i)
                                        break;

                                data_old = data_new;
                                order_old = order_new;

                                old_idx = new_idx;
                                new_idx = order_new;
                        }
                }
        }
}

For the same example, there were 34 reads, and 20 writes. This algorithm requires less memory access.

Reference

Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox