Tuesday, November 11, 2014

Facebook: Mutate input array

Given an input array and another array that describe a new index for each element, mutate the input array so that each element ends up in their new index. Discuss the runtime of the algorithm and how you can be sure there won't be any infinite loops.


Understand the problem:
Input char[] {a, b, c, d}
         int[]    {3, 1, 0, 2}

Suppose the input is valid, i.e, index array does not contain out of boundary elements, or "collision" elements. 

Output: char[] {c, b, d, a}

Based on the description above, out-of-place transformation is trivial. Just create a new array and put the character into the corresponding position. But the problem asks for a in-place transform, which therefore requires swap if necessary.

Solution:
public class Solution {
    public void mutate(int[] A, int[] pos) {
        if (A == null || A.length == 0 || pos == null || pos.length == 0) {
            return;
        }
        
        int i = 0;
        while (i < A.length) {
            if (pos[i] != i) {
                swap(A, i, pos[i]);
                swap(pos, i, pos[i]);
            } else {
                i++;
            }
        }
    }

    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }

    public static void main(String[] args) {
      Solution sol = new Solution();

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

      sol.mutate(A, pos);

      for (int i = 0; i < A.length; i++) {
        System.out.print(A[i] + " ");
      }

      System.out.println("");
    }
}

No comments:

Post a Comment