Algorithm: efficient way to remove duplicate integ

Question

I got this problem from an interview with Microsoft.

Given an array of random integers, write an algorithm in C that removes duplicated numbers and return the unique numbers in the original array.

E.g Input: {4, 8, 4, 1, 1, 2, 9} Output: {4, 8, 1, 2, 9, ?, ?}

One caveat is that the expected algorithm should not required the array to be sorted first. And when an element has been removed, the following elements must be shifted forward as well. Anyway, value of elements at the tail of the array where elements were shifted forward are negligible.

Update: The result must be returned in the original array and helper data structure (e.g. hashtable) should not be used. However, I guess order preservation is not necessary.

Update2: For those who wonder why these impractical constraints, this was an interview question and all these constraints are discussed during the thinking process to see how I can come up with different ideas.

Answer 1

This can be done in a single pass, in O(N) time in the number of integers in the input list, and O(N) storage in the number of unique integers.

Walk through the list from front to back, with two pointers "dst" and "src" initialized to the first item. Start with an empty hash table of "integers seen". If the integer at src is not present in the hash, write it to the slot at dst and increment dst. Add the integer at src to the hash, then increment src. Repeat until src passes the end of the input list.

Answer 2

One more efficient implementation

int i, j;

/* new length of modified array */
int NewLength = 1;

for(i=1; i< Length; i++){

   for(j=0; j< NewLength ; j++)
   {

      if(array[i] == array[j])
      break;
   }

   /* if none of the values in index[0..j] of array is not same as array[i],
      then copy the current value to corresponding new position in array */

  if (j==NewLength )
      array[NewLength++] = array[i];
}

In this implementation there is no need for sorting the array. Also if a duplicate element is found, there is no need for shifting all elements after this by one position.

The output of this code is array[] with size NewLength

Here we are starting from the 2nd elemt in array and comparing it with all the elements in array up to this array. We are holding an extra index variable 'NewLength' for modifying the input array. NewLength variabel is initialized to 0.

Element in array[1] will be compared with array[0]. If they are different, then value in array[NewLength] will be modified with array[1] and increment NewLength. If they are same, NewLength will not be modified.

So if we have an array [1 2 1 3 1], then

In First pass of 'j' loop, array[1] (2) will be compared with array0, then 2 will be written to array[NewLength] = array[1] so array will be [1 2] since NewLength = 2

In second pass of 'j' loop, array[2] (1) will be compared with array0 and array1. Here since array[2] (1) and array0 are same loop will break here. so array will be [1 2] since NewLength = 2

and so on

Answer 3

The following example should solve your problem:

def check_dump(x):
   if not x in t:
      t.append(x)
      return True

t=[]

output = filter(check_dump, input)

print(output)
True

Answer 4

Create a BinarySearchTree which has O(n) complexity.

Answer 5

How about the following?

int* temp = malloc(sizeof(int)*len);
int count = 0;
int x =0;
int y =0;
for(x=0;x<len;x++)
{
    for(y=0;y<count;y++)
    {
        if(*(temp+y)==*(array+x))
        {
            break;
        }
    }
    if(y==count)
    {
        *(temp+count) = *(array+x);
        count++;
    }
}
memcpy(array, temp, sizeof(int)*len);

I try to declare a temp array and put the elements into that before copying everything back to the original array.

Answer 6

import java.util.ArrayList;


public class C {

    public static void main(String[] args) {

        int arr[] = {2,5,5,5,9,11,11,23,34,34,34,45,45};

        ArrayList<Integer> arr1 = new ArrayList<Integer>();

        for(int i=0;i<arr.length-1;i++){

            if(arr[i] == arr[i+1]){
                arr[i] = 99999;
            }
        }

        for(int i=0;i<arr.length;i++){
            if(arr[i] != 99999){

                arr1.add(arr[i]);
            }
        }

        System.out.println(arr1);
}
    }