Hey guys,

So I have been practicing some common interview questions and have been stumped on one. I got asked this a few weeks ago at a job interview and I failed pretty miserably on it. It is removing duplicates in an array. The problem is as follows:

"Given an array of integers remove the duplicates in the array without using an extra buffer to hold the contents".

I was told I could not use any collections such as a Hashtable or an ArrayList but I COULD use a boolean array. Now first of all I know for a fact arrays in C# are a fixed size so basically you need to shift the contents up and write over the duplicates. I have been trying to solve this problem but cannot come up with a solution!

static int[] removeDupes(int[] array)
        {
            //Assumes ASCII characters
            bool[] boolArray = new bool[256];
           
            int i = 0, len = array.Length - 1;

            while (i < len)
            {
                //Dupe found
                if (boolArray[(char)array[i]])
                {
                    //write next element in array to current element
                    array[i] = array[i + 1];
                    i--;
                }
                else
                {
                    //If letter is encountered for first time assign set it to true
                    boolArray[(char)array[i]] = true;
                }
                i++;
            }
            return array;
        }

So this effectively 'works' in the sense that it removes the duplicate but it ALWAYS prints out the last value in the array twice. So for example if I have an array with 1,2,2,3,4,5. It will return 1,2,3,4,5,5.

Any ideas on how to solve this??

Recommended Answers

All 4 Replies

Check out this code to remove duplicates:

int[] s = { 1, 2, 3, 3, 4};
int[] q = s.Distinct().ToArray();

Right..

You are not allowed to use the C# API calls..

This one?

string[] sArray = {"a", "b", "b", "c", "c", "d", "e", "f", "f"};
var sList = new ArrayList();

for (int i = 0; i < sArray.Length; i++) {
    if (sList.Contains(sArray[i]) == false) {
        sList.Add(sArray[i]);
    }
}

var sNew = sList.ToArray();

for (int i = 0; i < sNew.Length; i++) {
    Console.Write(sNew[i]);
}

Another solution is perhaps to use Hashset Collection (Framework3.5) which only add new values in your collection instead of simple array...

HashSet<int> hs = new HashSet<int>();
hs.add(1); //--> hs = { 1 }
hs.add(2); //--> hs = { 1 ; 2 }
hs.add(1); //--> hs = { 1 ; 2 }

and you can convert it to Array if necessary

int[] array = hs.ToArray<int>();

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.