Question: I had an interview question which i could not solve. 

Write method (not a program) in Java Programming Language that will move all even numbers on the first half and odd numbers to the second half in an integer array. 

E.g. Input = {3,8,12,5,9,21,6,10}; Output = {12,8,6,10,3,5,9,21}.

The method should take integer array as parameter and move items in the same array (do not create another array). The numbers may be in different order than original array. This is algorithm test, so try to give as efficient algorithm as you can (possibly linear O(n) algorithm). Avoid using built in functions/API. \*

Also some basic intro to what is data structure efficiency

Answer: 
Keep two indices: one to the first odd number and one to the last even number. Swap such numbers and update indices.
public class ArraysSortEvensFirst {

```
public static void main(String[] args) {
    int[] arr = generateTestData();
    System.out.println(Arrays.toString(arr));

    ArraysSortEvensFirst test = new ArraysSortEvensFirst();
    test.sortEvensFirst(arr);

}

private static int[] generateTestData() {
    int[] arr = {1,3,5,6,9,2,4,5,7};
    return arr;
}

public int[] sortEvensFirst(int[] arr) {
    int end = arr.length;

    int last = arr.length-1;
    for(int i=0; i < arr.length; i++) {
        // find odd elements, then move to even slots
        if(arr[i]%2 > 0) {
            int k = findEven(last, arr);
            if(k > i) swap(arr, i, k);
            last = k;
        }
    }

    System.out.println(Arrays.toString(arr));
    return arr;
}

public int findEven(int last, int[] arr) {
    for(int k = last; k > 0; k--) {
        if(arr[k]%2 == 0) {
            return k;
        }
    }
    return -1; // not found;
}

public void swap(int[] arr, int x, int y) {
    int temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

```

}

Output:
[1, 3, 5, 6, 9, 2, 4, 5, 7]
[4, 2, 6, 5, 9, 3, 1, 5, 7]