2
\$\begingroup\$

This is the original question https://www.geeksforgeeks.org/union-and-intersection-of-two-sorted-arrays-2/

Given two sorted arrays, find their union and intersection.

Example:

Input : arr1[] = {1, 3, 4, 5, 7}
        arr2[] = {2, 3, 5, 6}  
Output : Union : {1, 2, 3, 4, 5, 6, 7} 
         Intersection : {3, 5}

Input : arr1[] = {2, 5, 6}
        arr2[] = {4, 6, 8, 10}  
Output : Union : {2, 4, 5, 6, 8, 10} 
         Intersection : {6}

I also added one more case of finding items which are only in one of the two arrays and called it Diff.

Please review for performance.
Please do not comment about code in the same class as the test and the functions not being static. It is just faster for me like this to get to the point of the exercise.

using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace ArrayQuestions
{
    /// <summary>
    /// https://www.geeksforgeeks.org/union-and-intersection-of-two-sorted-arrays-2/
    /// </summary>

    [TestClass]
    public class UnionAndIntersectionOfTwoSortedArrays2
    {
        [TestMethod]
        public void UnionTest()
        {
            int[] arr1 = { 1, 3, 4, 5, 7 };
            int[] arr2 = { 2, 3, 5, 6 };
            int[] union = { 1, 2, 3, 4, 5, 6, 7 };
            CollectionAssert.AreEqual(union, Union(arr1, arr2));
        }

        [TestMethod]
        public void IntersectionTest()
        {
            int[] arr1 = { 1, 3, 4, 5, 7 };
            int[] arr2 = { 2, 3, 5, 6 };

            int[] intersection = { 3, 5 };
            CollectionAssert.AreEqual(intersection, Intersection(arr1, arr2));
        }

        [TestMethod]
        public void DiffTest()
        {
            int[] arr1 = { 1, 3, 4, 5, 7 };
            int[] arr2 = { 2, 3, 5, 6 };

            int[] diff = { 1, 2, 4, 6, 7 };
            CollectionAssert.AreEqual(diff, Diff(arr1, arr2));
        }

        private int[] Diff(int[] arr1, int[] arr2)
        {
            int i = 0;
            int j = 0;
            int n = arr1.Length;
            int m = arr2.Length;
            List<int> list = new List<int>();
            while (i < n && j < m)
            {
                if (arr1[i] == arr2[j])
                {
                    i++;
                    j++;
                }

                else if (arr1[i] < arr2[j])
                {
                    list.Add(arr1[i]);
                    i++;
                }
                else
                {
                    list.Add(arr2[j]);
                    j++;

                }
            }

            while (i < n)
            {
                list.Add(arr1[i]);
                i++;
            }
            while (j < m)
            {
                list.Add(arr2[j]);
                j++;
            }
            return list.ToArray();
        }


        private int[] Intersection(int[] arr1, int[] arr2)
        {
            int i = 0;
            int j = 0;
            int n = arr1.Length;
            int m = arr2.Length;
            List<int> list = new List<int>();
            while (i < n && j < m)
            {
                if (arr1[i] == arr2[j])
                {
                    list.Add(arr1[i]);
                    i++;
                    j++;
                }
                else if (arr1[i] < arr2[j])
                {
                    i++;
                }
                else
                {
                    j++;
                }
            }

            return list.ToArray();
        }

        public int[] Union(int[] arr1, int[] arr2)
        {
            int i = 0;
            int j = 0;
            int n = arr1.Length;
            int m = arr2.Length;
            List<int> list = new List<int>();
            while (i < n && j < m)
            {
                if (arr1[i] < arr2[j])
                {
                    list.Add(arr1[i]);
                    i++;
                }
                else if (arr2[j] < arr1[i])
                {
                    list.Add(arr2[j]);
                    j++;
                }
                else // equals
                {
                    list.Add(arr1[i]);
                    i++;
                    j++;

                }
            }
            //handle the rest
            for (; i < n; i++)
            {
                list.Add(arr1[i]);
            }
            for (; j < m; j++)
            {
                list.Add(arr2[j]);
            }

            return list.ToArray();
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ It is just faster for me like this to get to the point of the exercise. If you code really fast, would you also expect a fast review? \$\endgroup\$ – dfhwze Jul 4 at 4:33
  • \$\begingroup\$ @dfhwze I mean to say that please disregard why it is not separate class for test and for the rest of the code. \$\endgroup\$ – Gilad Jul 4 at 6:26
  • \$\begingroup\$ I get what you mean, but still it would be a very small effort to extract the algorithm to a separate class and call that class in the unit tests. \$\endgroup\$ – dfhwze Jul 4 at 6:34
  • 1
    \$\begingroup\$ It looks like both Union() and Intersection() are the basic implementation of the algorithms which do not handle duplicates (Union of { 1, 2, 2, 2, 3 } and { 2, 3, 4, 5 }) gives {1, 2, 2, 2, 3, 4, 5} not {1, 2, 3, 4, 5} and Intersection of { 2,5,5,6,6} and {4,6,6,8,10} gives {6,6} not {6}) is this intended? \$\endgroup\$ – AlanT Jul 4 at 8:44
  • 2
    \$\begingroup\$ I see you are practicing various algorithms but writing working code is a no-brainer. Doing it in a way that can be maintained, tested and easily understood, with intuitive API is much much harder and on higher levels this is what counts most. Currently you just write something to solve the task avoiding to implement additional types to encapsulate the logic in proper modules. If you want to improve your skills you should try to write more professional code with proper types, names etc. I would still classify this code as beginner. \$\endgroup\$ – t3chb0t Jul 4 at 19:11
5
\$\begingroup\$
  • You can optimize all 3 methods if you initialize list's capacity to the longest of the two arrays. Resizing a list involves allocating a new internal array and copying old items into the new array, which is something to keep in mind if you care about performance.
  • Your tests often contain small pieces of manually crafted data. That's not a very scalable approach. It's easy to generate large amounts of test data with a bit of Linq: Enumerable.Range(0, 1000).Select(i => random.Next(0, 1000)).OrderBy(n => n).ToArray() gives you an input array. Verification can be done with a few loops (is every number in arr1 and arr2 present in union, and is every number in union present in either arr1 or arr2?). For the duplicate-handling implementation verification is even easier with a combination of Linq's Union, Intersect and OrderBy methods.
  • Names like i, j, n and m are not very descriptive - specifically which array they're associated with is not clear from their names. Changing them to something like index1, index2, length1 and length2 will make that relationship clear.
  • If you're storing array lengths in local variables, then why not also store the results of arr1[i] and arr2[j] in local variables before comparing them? Both of these are micro-optimizations that affect the readability of the code, so I would only do this for performance-sensitive code, and only when profiling shows that it's actually an improvement.
\$\endgroup\$
  • 1
    \$\begingroup\$ Regarding the first and last points, the attempts at optimising could well go wrong if it messes with the CLR. It used to be the case, for example, and cycling forward through an array was faster than backward because the optimiser would remove redundant bound checks: any additional indirection (e.g. stuffing lengths in variables) might break this. As you say: only do it if you know it is a problem and it shows an improvement upon (realistic) measurement. \$\endgroup\$ – VisualMelon Jul 5 at 19:26
  • \$\begingroup\$ Would you allow names as i1, i2, n1, n2 or prefer the longer names as mentioned in your answer? \$\endgroup\$ – dfhwze Jul 5 at 19:59
  • 1
    \$\begingroup\$ @dfhwze: personally I find the longer variant a bit easier to read so that's how I would write it, but in both cases the relationship with arr1 is clear, so I'd be fine with either. \$\endgroup\$ – Pieter Witvoet Jul 5 at 20:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.