[megglz]

I'm prepping for a technical phone interview at the end of next week. I've been coding how to remove duplicates from arrays and lists.

When I print the return of my array, it doesn't shorten the array size so I end up with three 0's after returning 1,2,3,4,5,6,7 minus duplicates. What would be the easiest way to shorten the array before returning?

class Program
    {
        static void Main(string[] args)
        {
            int[] numbers = new int[] { 1, 2, 3, 4, 4, 4, 5, 6, 7, 7 };

            List<int> input = new List<int>();
            input.Add(1);
            input.Add(2);
            input.Add(3);
            input.Add(4);
            input.Add(4);
            input.Add(5);
            input.Add(5);
            input.Add(6);

            List<int> result = removeDuplicates(input);
            
            foreach (int i in result)
                Console.WriteLine("List:" + i);

            int[] intResult = removeDuplicateArray(numbers);
            foreach (int i in intResult)
                Console.WriteLine("Array:" + i);

        }


        static int[] removeDuplicateArray(int[] inputList)
        {
            int[] finalArray = new int[inputList.Length];
            int i = 0;

            foreach (int currValue in inputList)
            {
                if (!Contains(finalArray, currValue))
                {
                    finalArray[i] = currValue;
                    i++;
                }
            }
            return finalArray;
        }

        static bool Contains(Array list, int comparedValue)
        {
            foreach (int listValue in list)
            {
                if (listValue == comparedValue)
                {
                    return true;
                }
            }
            return false;
        }

        static List<int> removeDuplicates(List<int> inputList)
        {
            List<int> finalList = new List<int>();
            foreach (int currValue in inputList)
            {
                if (!Contains(finalList, currValue))
                {
                    finalList.Add(currValue);
                }
            }
            return finalList;
        }

        static bool Contains(List<int> list, int comparedValue)
        {
            foreach (int listValue in list)
            {
                if (listValue == comparedValue)
                {
                    return true;
                }
            }
            return false;
        }
    }

[Imdsm]

Why are you using an int array for the final list variable? They are fixed lengths, hence why we have generic lists. Simply use a List<int> and if it doesn't already contain the current value, add it. Then if you have to return an int array, just do list.ToArray();

Easy peasy lemon squeasy!

[Imdsm]

Look at how more concise this is

using System;
using System.Collections.Generic;

namespace ListDuplicates
{
    class Program
    {
        static void Main(string[] args)
        {
            // first we declare our arrays
            // but we don't need to use more than two lines for this
            int[] intarr = new int[] { 1, 2, 3, 4, 4, 5, 6, 7, 7, 8, 9 };
            List<int> list = new List<int>(intarr);

            // now we remove dups
            int[] newintarr = RemoveDuplicates(intarr);
            List<int> newlist = RemoveDuplicates(list);

            // and output
            for (int i = 0; i < newintarr.Length; i++)
            {
                string output = "newintarr[{0}] = {1}";
                Console.WriteLine(string.Format(output, i, newintarr[i]));
            }

            for (int i = 0; i < newlist.Count; i++)
            {
                string output = "newlist[{0}] = {1}";
                Console.WriteLine(string.Format(output, i, newlist[i]));
            }

            Console.ReadKey();
        }

        static List<int> RemoveDuplicates(List<int> list)
        {
            List<int> newlist = new List<int>();
            foreach (int i in list)
            {
                if (!newlist.Contains(i)) 
                    newlist.Add(i);
            }
            return newlist;
        }

        static int[] RemoveDuplicates(int[] intarr)
        {
            return RemoveDuplicates(new List<int>(intarr)).ToArray();
        }
    }
}

This post has been edited by Imdsm: 04 September 2010 - 05:14 AM

[fixo]

megglz, on 04 September 2010 - 02:59 AM, said:

I'm prepping for a technical phone interview at the end of next week. I've been coding how to remove duplicates from arrays and lists.

When I print the return of my array, it doesn't shorten the array size so I end up with three 0's after returning 1,2,3,4,5,6,7 minus duplicates. What would be the easiest way to shorten the array before returning?

class Program
    {
        static void Main(string[] args)
        {
            int[] numbers = new int[] { 1, 2, 3, 4, 4, 4, 5, 6, 7, 7 };

            List<int> input = new List<int>();
            input.Add(1);
            input.Add(2);
            input.Add(3);
            input.Add(4);
            input.Add(4);
            input.Add(5);
            input.Add(5);
            input.Add(6);

            List<int> result = removeDuplicates(input);
            
            foreach (int i in result)
                Console.WriteLine("List:" + i);

            int[] intResult = removeDuplicateArray(numbers);
            foreach (int i in intResult)
                Console.WriteLine("Array:" + i);

        }


        static int[] removeDuplicateArray(int[] inputList)
        {
            int[] finalArray = new int[inputList.Length];
            int i = 0;

            foreach (int currValue in inputList)
            {
                if (!Contains(finalArray, currValue))
                {
                    finalArray[i] = currValue;
                    i++;
                }
            }
            return finalArray;
        }

        static bool Contains(Array list, int comparedValue)
        {
            foreach (int listValue in list)
            {
                if (listValue == comparedValue)
                {
                    return true;
                }
            }
            return false;
        }

        static List<int> removeDuplicates(List<int> inputList)
        {
            List<int> finalList = new List<int>();
            foreach (int currValue in inputList)
            {
                if (!Contains(finalList, currValue))
                {
                    finalList.Add(currValue);
                }
            }
            return finalList;
        }

        static bool Contains(List<int> list, int comparedValue)
        {
            foreach (int listValue in list)
            {
                if (listValue == comparedValue)
                {
                    return true;
                }
            }
            return false;
        }
    }

Try this instead

          int[] numbers = new int[] { 7, 7, 5, 5, 5, 1, 2, 3, 4, 4, 4, 5, 6, 7, 7 };
            List<int> input = new List<int>();
            foreach (int x in numbers)
                if (!input.Contains(x)) input.Add(x);
            input.Sort();

~'J'~

[JackOfAllTrades]

Except that this is some sort of interview question, and it appears based on the code (there is code in the OP for List<> duplicate removal also) that perhaps it needs to be demonstrated both on an Array and a List.

[Nakor]

Just requires a little bit more code if you want to return an array with the size equal the number of non-duplicate items.

static int[] removeDuplicateArray(int[] inputList)
{
    int[] tempArray = new int[inputList.Length];
    int i = 0;

    foreach (int currValue in inputList)
    {
        if (!Contains(tempArray, currValue))
        {
            tempArray[i++] = currValue;
        }
    }
    int[] finalArray = new int[i-1];
    
    for (int j=0; j< (i-1); j++)
    {
        finalArray[i] = tempArray[i];
    }

    return finalArray;
}

[Nakor]

another way would be to count the number of duplicates and create the array using the original array's size minus the number of duplicates.

static int[] removeDuplicateArray(int[] inputList)
        {
            int duplicate = 0;

            for (int j=0; j<inputList.Length; j++)
            {
                for (int k=j; k< inputList.Length; k++)
                {
                    if (inputList[j] == inputList[k])
                    {
                        duplicate++;
                    }
                }
            }

            int[] finalArray = new int[(inputList.Length - duplicate)];
            int i = 0;

            foreach (int currValue in inputList)
            {
                if (!Contains(finalArray, currValue))
                {
                    finalArray[i] = currValue;
                    i++;
                }
            }
            return finalArray;
        }

Disclaimer: This is theory only as I did not test this code

[megglz]

thanks

[Imdsm]

@Nakor, Surely it's better to teach people concise code, with the least possible performance hit?

static int[] removeDuplicateArray(int[] inputList)
{
    int duplicate = 0;

    for (int j=0; j<inputList.Length; j++)
    {
	for (int k=j; k< inputList.Length; k++)
	{
	    if (inputList[j] == inputList[k])
	    {
		duplicate++;
	    }
	}
    }

    int[] finalArray = new int[(inputList.Length - duplicate)];
    int i = 0;

    foreach (int currValue in inputList)
    {
	if (!Contains(finalArray, currValue))
	{
	    finalArray[i] = currValue;
	    i++;
	}
    }
    return finalArray;
}

static List<int> RemoveDuplicates(List<int> list)
{
    List<int> newlist = new List<int>();
    foreach (int i in list)
    {
	if (!newlist.Contains(i)) newlist.Add(i);
    }
    return newlist;
}

static int[] RemoveDuplicates(int[] intarr)
{
    return RemoveDuplicates(new List<int>(intarr)).ToArray();
}

This post has been edited by Imdsm: 04 September 2010 - 03:24 PM

[Nakor]

That all depends on the requirements imposed on you. If you convert the array to a List to remove the duplicates you're not really demonstrating how to remove duplicates from an Array, you're just removing it from a List again. If I was just doing this for myself I would probably implement it your way or with something like

public static List<int> RemoveDuplicates(List<int> aList)
{
    return (from aL in aList
            select aL).Distinct().ToList();
}
		
public static int[] RemoveDuplicates(int[] intarr)
{
    return (from arr in intarr
	        select arr).Distinct().ToArray();
}

just because I like using LINQ and it's simple to read.

[fixo]

Nakor, on 04 September 2010 - 02:50 PM, said:

That all depends on the requirements imposed on you. If you convert the array to a List to remove the duplicates you're not really demonstrating how to remove duplicates from an Array, you're just removing it from a List again. If I was just doing this for myself I would probably implement it your way or with something like

public static List<int> RemoveDuplicates(List<int> aList)
{
    return (from aL in aList
            select aL).Distinct().ToList();
}
		
public static int[] RemoveDuplicates(int[] intarr)
{
    return (from arr in intarr
	        select arr).Distinct().ToArray();
}

just because I like using LINQ and it's simple to read.

Oh, I'm too late anyway I have post my solution as well

        /// <summary>
        ///   remove duplicates using SortedList
        /// </summary>
        /// <param name="numbers"></param>
        /// <returns></returns>
        static public int[] RemoveDupes1(int[] numbers)
        {
           SortedList sorted = new SortedList();
         
               for (int i = 0; i < numbers.Length; i++)
               {
                   if (!sorted.ContainsValue(numbers[i]))
                   {
                       sorted.Add(numbers[i], numbers[i]);
                      
                   }
               }

               int[] result = new int[sorted.Count];

               sorted.Values.CopyTo(result, 0);

            return result;
        }
        /// <summary>
        ///      remove duplicates using HashTable
        /// </summary>
        /// <param name="numbers"></param>
        /// <returns></returns>
        static public int[] RemoveDupes2(int[] numbers)
        {
            Hashtable sorted = new Hashtable();

            for (int i = 0; i < numbers.Length; i++)
            {
                if (!sorted.ContainsValue(numbers[i]))
                {
                    sorted.Add(numbers[i], numbers[i]);

                }
            }

            int[] result = new int[sorted.Count];

            sorted.Values.CopyTo(result, 0);

            return result;
        }
        /// <summary>
        ///  remove duplicates using LINQ (.NET FrameWork 3.5 and higher)
        /// </summary>
        /// <param name="numbers"></param>
        /// <returns></returns>
        static public int[] RemoveDupes3(int[]numbers)
        {
            /*Array.Sort(numbers); optional*/
            return numbers.Distinct().ToArray();
        }

~'J'~

This post has been edited by fixo: 05 September 2010 - 03:00 AM

[Nakor]

Let's add one more to the growing list then

	public static class RemoveDupes
	{
		public static int[] RemoveDuplicates(this int[] arr)
		{
			return arr.Distinct().ToArray();
		}
	}

would then be used in main like so

int[] numbers = new int[] { 1, 2, 3, 4, 4, 4, 5, 6, 5, 7, 1 };

foreach (int i in numbers.RemoveDuplicates())
        Console.WriteLine("Array:" + i);

As I stated before there's many ways to do it, a lot of it comes down to your personal preference.

[Imdsm]

This is true

Question comes down to what is important, the means or the end?

I haven't really started learning LINQ properly yet, I've been a 2.0 coder most of my C# life, only recently moved to 4.0, but I love how concise that line was!

+1

[megglz]

Thanks !