Merge Sorted Arrays

Merging sorted arrays is the quintessential interview question that tests if you can write code further than "Hello World!"

Thing with this problem is that it differs only very slightly between different languages. For example for Java, C++ and C# the code would pretty much look the same. So I am just going to put 1 language here for each method and might add others later.

C++

Straight answer (O(n1 + n2))

void mergeSortedArrays(int arr1[], int arr2[], int arr3[])
    {
        int n1 = sizeof(arr1) / sizeof(arr1[0]);
        int n2 = sizeof(arr2) / sizeof(arr2[0]);

        int i = 0, j = 0, k = 0;
        while(i < n1 && j < n2)
        {
            //Track indexes of each array individually and increment them in an ordered manner
            if(arr1[i] < arr2[j])
            {
                arr3[k++] = arr1[i++];
            }
            else
            {
                arr3[k++] = arr1[j++];
            }
        }

        //Handle the remaining elements in each of the arrays
        while(i < n1)
            arr3[k++] = arr1[i++];
        while(j < n1)
            arr3[k++] = arr1[j++];
    }

Java

Smarter variation with maps. (O(nlog(n) + mlog(m)))

This version abuses how map-like datastructures handle data.

int[] mergeSortedArrays(int[] arr1, int[] arr2)
    {
        int n1 = arr1.length;
        int n2 = arr2.length;

        //Can also use TreeMap here but Hashmap is faster at inserting than TreeMap
        Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();
        for(int i = 0; i < n; i++)
            map.put(a[i], true);
        for(int i = 0;i < m;i++)
            map.put(b[i], true);

        return (int[]) map.keys().toArray();
    }

I might add other languages later but its all going to be pretty much the same, for example; in javascript you'd use 'Map()' to implement the second solution and for C# Dictionary or SortedDictionary could be used but apart from that its all the same.

Notes and stuff:

When I was trying to figure out whats best to use on the Java solution I discovered this comparasion between HashMap and TreeMap. It is pretty cool