Merging two lists into one and sorting the items.

Question

Is there a way to merge(union without dupes) two given lists into one and store the items in sorted way by using ONE for loop?

Also, i am looking for a solution which does not makes use of API methods ( like, union, sort etc).

Sample Code.

private static void MergeAndOrder() 
{
var listOne = new List<int> {3, 4, 1, 2, 7, 6, 9, 11}; 
var listTwo = new List<int> {1, 7, 8, 3, 5, 10, 15, 12}; 

//Without Using C# helper methods...
//ToDo.............................

//Using C# APi.
var expectedResult = listOne.Union(listTwo).ToList(); 
expectedResult.Sort();//Output: 1,2,3,4,5,6,7,8,9,10,11,12,15
//I need the same result without using API methods, and that too by iterating over items only once.


}

PS: I have been asked this question in an interview, but couldn't find answer as yet.

Answer 1

You could write a loop that merges and de-dups the lists and uses a binary-search approach to insert new values into the destination list.

Answer 2

Why can't you use the api methods? Re-inventing the wheel is dumb. Also, it's the .ToList() call that's killing you. Never call .ToList() or .ToArray() until you absolutely have to, because they break your lazy evaluation.

Do it like this and you'll enumerate the lists the minimum amount necessary:

var expectedResult = listOne.Union(listTwo).OrderBy(i => i);

This will do the union in one loop using a hashset, and lazy execution means the base-pass for the sort will piggyback on the union. But I don't think it's possible finish the sort in a single iteration, because sorting is not a O(n) operation.

Answer 3

var listOne = new List<int> { 3, 4, 1, 2, 7, 6, 9, 11 };
var listTwo = new List<int> { 1, 7, 8, 3, 5, 10, 15, 12 };
var result = listOne.ToList();

foreach (var n in listTwo)
{
  if (result.IndexOf(n) == -1)
    result.Add(n);
}

Answer 4

Without the precondition that both lists are sorted before the merge + sort operation, you can't do this in O(n) time (or "using one loop").

Add that precondition and the problem is very easy.

Keep two iterators, one for each list. On each loop, compare the element from each list and choose the smaller. Increment that list's iterator. If the element you are about to insert in the final list is already the last element in that list, skip the insert.

In pseudocode:

List a = { 1, 3, 5, 7, 9 }
List b = { 2, 4, 6, 8, 10 }
List result = { }
int i=0, j=0, lastIndex=0
while(i < a.length || j < b.length)
    // If we're done with a, just gobble up b (but don't add duplicates)
    if(i >= a.length)
        if(result[lastIndex] != b[j])
            result[++lastIndex] = b[j]
        j++
        continue

    // If we're done with b, just gobble up a (but don't add duplicates)
    if(j >= b.length)
        if(result[lastIndex] != a[i])
            result[++lastIndex] = a[i]
        i++
        continue

    int smallestVal

    // Choose the smaller of a or b
    if(a[i] < b[j])
        smallestVal = a[i++]
    else
        smallestVal = b[j++]

    // Don't insert duplicates
    if(result[lastIndex] != smallestVal)
        result[++lastIndex] = smallestVal
end while

Answer 5

The closest solution I see would be to allocate an array knowing that integers are bounded to some value.

int[] values = new int[ Integer.MAX ]; // initialize with 0
int size1 = list1.size();
int size2 = list2.size();

for( int pos = 0; pos < size1 + size2 ; pos++ )
{
     int val =  pos > size1 ? list2[ pos-size1 ] : list1[ pos ] ;
     values[ val ]++;
}

Then you can argue that you have the sorted array in a "special" form :-) To get a clean sorted array, you need to traverse the values array, skip all position with 0 count, and build the final list.