Today I want to take a look on one of the classical Amazon interview questions about merging two sorted arrays.

Problem: "Suppose we have two sorted arrays A[] of m elements and B[] of n elements. Write a function merge which would merge this two arrays into new sorted array C[] in O(n) time as shown on the picture".

 

 

 

 

 

 

 

 

The solution if you think about it is quite simple, one of possible approaches would be:

1. Check if you exhausted one array. If so, take numbers from the other one and continue

2. If both arrays are in play, take the smaller element and increment indexer of the array which been used

3. Repeat

Here how it would look in C#

public static int[] Merge(int[] A, int[] B) 
       { 
           if ((A == null) || (A.Length == 0)) return B; 
           if ((B == null) || (B.Length == 0)) return A; 

           int index = 0; 
           int i = 0; 
           int j = 0; 
           int CountB = B.Length - 1; 
           int CountA = A.Length - 1; 
           int finalSize = A.Length + B.Length; 
           int[] C = new int[finalSize]; 

           while (index <= (finalSize - 1)) 
           { 
               if (i > CountA) 
               { 
                   C[index] = B[j]; 
                   j++; 
               } 
               else 
                   if (j > CountB) 
                   { 
                       C[index] = A[i]; 
                       i++; 
                   } 
                   else 
                   { 
                       if (A[i] < B[j]) 
                       { 
                           C[index] = A[i]; 
                           i++; 
                       } 
                       else 
                       { 
                           C[index] = B[j]; 
                           j++; 
                     }                   
                   } 
                   index++; 
           } 
           return C; 
       }

 

Main things to pay attention are:

1. Check for edge cases (i.e. null or empty input parameters)

2. Be careful with indexes as you need to maintain two of them

3. Be sure to write couple test cases

 

As an example here are set of test cases to unit test this function:

using System;
using System;
using System.Text;
using NUnit.Framework;

namespace Tests
{
    [TestFixture()]
    public class TestCases
    {
         [Test]
        public void emptyMerge()
        {
        int[] A = new int[] { 1, 2, 3, 4, 5 };
        int[] B = new int[] { };
        int[] Result = mergeArrays.Merge(A, B);
        Assert.AreEqual(A, Result); 
        }

        [Test]
        public void lenghtVerification()
        {
            int[] A = new int[] { 1, 2, 3, 4, 5 };
            int[] B = new int[] { 1,2,3};
            int[] Result = mergeArrays.Merge(A, B);
            Assert.AreEqual(A.Count()+B.Count(), Result.Count());
        }

       [Test]
        public void sequentialMergeAB()
        {
          int []A=new int[]{1,2,3,4,5};
          int []B=new int[]{100,200};
          int[] Result = mergeArrays.Merge(A, B);
          Assert.AreEqual(new int[]{1,2,3,4,5,100,200},Result);        
          
        }

        [Test]
        public void sequentialMergeBA()
        {
            int []A=new int[]{100,200};
            int []B=new int[]{1,2,3,4,5};
            int[] Result = mergeArrays.Merge(A, B);
           Assert.AreEqual(new int[]{1,2,3,4,5,100,200},Result);   
        }

        [Test]
        public void SameNumbersMerge()
        {
            int[] A = new int[] {1};
            int[] B = new int[] {1};
            int[] Result = mergeArrays.Merge(A, B);
            Assert.AreEqual(new int[] { 1, 1}, Result);
        }
        [Test]
        public void MixedMerge()
        {
            int[] A = new int[] { 1, 2, 3, 4, 5,100,200,300,310 };
            int[] B = new int[] { 1,1,1,100, 200 };
            int[] Result = mergeArrays.Merge(A, B);
            Assert.AreEqual(new int[] { 1, 1,1,1, 2, 3, 4, 5, 100, 100, 200, 200, 300, 310 }, Result);
        }
     
    }
}

As a bonus question think, how would you solve same problem if I would ask to use multiple threads?