Combining two lists into one and sorting items

Question

Is there a way to combine (merge without cheating) two given lists into one and save the sorted items using ONE for the loop?

Also, I am looking for a solution that does not use API methods (e.g. 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 was asked this question in an interview, but have not yet found an answer.

Answer 1

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

Add this prerequisite and the problem is very simple.

Keep two iterators, one for each list. In each cycle, compare an item from each list and select the smaller one. Enlarge this list with an iterator. If the item you are about to insert in the last list is already the last item in this list, skip the insert.

In pseudo code:

 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 2

Why can't you use api methods? The reinvention of the wheel is dull. Also, this is a .ToList() call that kills you. Never call .ToList() or .ToArray() until you are absolutely obligated because they violate your lazy assessment.

Do it like this and you will list the minimum amount needed:

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

This will be combining in a single loop using hashset, and lazy execution means the base sort pass will be the piggyback on the join. But I don’t think it’s possible to finish sorting in one iteration, because sorting is not an O (n) operation.

Answer 3

  private static void MergeTwoSortedArray(int[] first, int[] second) { //throw new NotImplementedException(); int[] result = new int[first.Length + second.Length]; int i=0 , j=0 , k=0; while(i < first.Length && j <second.Length) { if(first[i] < second[j]) { result[k++] = first[i++]; } else { result[k++] = second[j++]; } } if (i < first.Length) { for (int a = i; a < first.Length; a++) result[k] = first[a]; } if (j < second.Length) { for (int a = j; a < second.Length; a++) result[k++] = second[a]; } foreach (int a in result) Console.Write(a + " "); Console.WriteLine(); } 

Answer 4

Using iterators and a stream interface is not so difficult:

class MergeTwoSortedLists {static void Main (string [] args) {

  var list1 = new List<int?>() { 1,3,5,9,11 }; var list2 = new List<int?>() { 2,5,6,11,15,17,19,29 }; foreach (var c in SortedAndMerged(list1.GetEnumerator(), list2.GetEnumerator())) { Console.Write(c+" "); } Console.ReadKey(); } private static IEnumerable<int> SortedAndMerged(IEnumerator<int?> e1, IEnumerator<int?> e2) { e2.MoveNext(); e1.MoveNext(); do { while (e1.Current < e2.Current) { if (e1.Current != null) yield return e1.Current.Value; e1.MoveNext(); } if (e2.Current != null) yield return e2.Current.Value; e2.MoveNext(); } while (!(e1.Current == null && e2.Current == null)); } } 

Answer 5

You can write a loop that combines and deactivates lists and uses the binary search method to insert new values ​​into the mailing list.

Answer 6

 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 7

The nearest solution that I see will be to allocate an array, knowing that integers are limited 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 say that you have a sorted array in a “special” form :-) To get a clean sorted array, you need to go through the values array, skip all positions with 0 count and build the final list.

Answer 8

This will only work for lists of integers, but fortunately, this is what you have!

 List<int> sortedList = new List<int>(); foreach (int x in listOne) { sortedList<x> = x; } foreach (int x in listTwo) { sortedList<x> = x; } 

This uses the values ​​in each list as the index position in which the value will be stored. Any duplicate values ​​will overwrite the previous record at this index position. It satisfies the requirement of only one iteration over values.

Of course, this means that the list will have “empty” positions.

I suspect that the vacancy is already filled, although .... :-)

Answer 9

Try this:

  public static IEnumerable<T> MergeWith<T>(IEnumerable<T> collection1, IEnumerable<T> collection2, IComparer<T> comparer) { using (var enumerator1 = collection1.GetEnumerator()) using (var enumerator2 = collection2.GetEnumerator()) { var isMoveNext1 = enumerator1.MoveNext(); var isMoveNext2 = enumerator2.MoveNext(); do { while (comparer.Compare(enumerator1.Current, enumerator2.Current) < 0 || !isMoveNext2) { if (isMoveNext1) yield return enumerator1.Current; else break; isMoveNext1 = enumerator1.MoveNext(); } if (isMoveNext2) yield return enumerator2.Current; isMoveNext2 = enumerator2.MoveNext(); } while (isMoveNext1 || isMoveNext2); } }