CareerCup

HashTable?

yeah

class FindDups
{
static void Main(string[] args)
{
int[] inputArr = null;
GenerateInts(ref inputArr, 99999);
Console.WriteLine("Input Array:");
for (int i = 0; i < 99999; i++)
{
Console.Write(inputArr[i] + "; ");
}

DateTime startTime = DateTime.Now;
FindDups.FindDupInts(inputArr);
DateTime endTime = DateTime.Now;
Console.WriteLine("\n Time taken: {0}", endTime - startTime);
}

static void GenerateInts(ref int[] arrayInts, int count)
{
Random randInt = new Random(DateTime.Now.Second);
arrayInts = new int[count];

for (int i = 0; i < count; i++)
{
arrayInts[i] = randInt.Next(0, count);
}
}

static void FindDupInts(int[] inpArr)
{
Hashtable dupHash = new Hashtable();

try
{
int i = 0;
while (i >= 0)
{
if (!dupHash.Contains(inpArr[i]))
dupHash.Add(inpArr[i], inpArr[i++]);
else
i++;
}

}
catch (IndexOutOfRangeException)
{
Console.WriteLine("\n\n Dups: Num of Dups={0}",dupHash.Count);
foreach (DictionaryEntry dupObj in dupHash)
{
Console.Write((int)dupObj.Value + "; ");
}
}
}

}

We can use bst to find duplications.

Each node contains boolean which says it is duplicated or not.

Algo:

step 1: for each element in array.
step 2 : insert in to bst.
step 3 : if number is already there in bst, then mark boolean as true (duplicate)
else mark as false (we are inserting first time).
step 4: traverse bst and print only numbers which as boolean set.

space complexity = o(n) (Of course:just n bits).
time complexity = o(nlogn).

one other way we can do it as follows:
step 1: Sort the array
step 2: compare each element with its adjacent element , if any two are equal then it is a duplicate...The whole process can be done in O(nlogn)+O(n) time..

void find_duplicates(int a[])
{
int i,b[256];
for(i=0;i<255;i++)
{
b[i]=0;
}
for(i=0;i<a.length;i++)
{
if(!b[a[i]])
{
b[a[i]]++;
}
else
{
printf("\n Duplicate element found at index %d is %d",i,a[i]);
}
}
}

For each element in the array, search the BST. If not found, insert it into the BST. If found, we've found the duplicate. This takes O(logn) for searching and O(logn) for insertion. So, total is O(logn + logn) = O(logn).

This is better than sorting (O(logn) + O(n)) and Hashtable (O(n)). But, this approach takes O(n) extra space for the BST. But, the Hashtable takes O(n) extra space (or more !!). Sorting might also take O(n) time unless you do in-place. So, BST approach is the best and the cheapest.

My soultion involves sorting of array: O(nlogn), and then finding dups ...

import java.util.Arrays;


public class Duplicates {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

int[] input = {1,2,3,3,3,3,3,4,1,2};
findDup(input);

}

public static void findDup(int[] ip)
{
Arrays.sort(ip);
int[] dupArr = new int[ip.length];

int j=0;
int currNum = ip[0];
int currCnt = 0;
for(int i=0;i<ip.length;i++)
{
if(ip[i]==currNum)
{
currCnt++;
continue;
}
else if(ip[i]!=currNum)
{
if(currCnt>1)
dupArr[j++] = ip[i-1];

currNum = ip[i];
currCnt=1;
}
}

for(int i=0;i<j;i++)
System.out.println(dupArr[i]);
}

}

we can solve the problem with help of hashmap or hashtable
1 loop through the array and put the element in the hashmap
2 if the entries is not already available . put the entry in hashmap and initialize
the count value to 1
3 if the entries is already available . just increment the count value.
print it if the count==1

Java Pseudocode

int[] arrContent={2,1,3,4,1,6,1,3,2};
HashMap<int,int> duplicateMap=new HashMap<int,in>();
for(int i=0;i<arrContent.length;i++) {
if(!duplicateMap.containtsKey(arrContent[i]) {
duplicateMap.put(arrContent[i],1);
}
else {
int count=duplicateMap.get(arrContent[i]);
if(count==1) {
System.out.println(" duplicate value is"+arrContent[i]);
}
duplicateMap.put(arrContent[i],++count);
}

}

so time complexity is o(n)
space complexity o(n)

public class Duplicates
{
      public void removeDuplicate(int a[])
      {
            int tail=1;
            for(int i=0;i<a.length;i++)
            {
               int j = 0;
               while(j<tail)
               { 
                    if(a[i]==a[j] break;
                    else j++; 
               } 
               if(j==tail)
                  a[tail++]=a[i]; 
            }  
      }
}

public class Duplicates
{
      public void removeDuplicate(int a[])
      {
            int tail=1;
            for(int i=1;i<a.length;i++) //Correction in above code
            {
               int j = 0;
               while(j<tail)
               { 
                    if(a[i]==a[j] break;
                    else j++; 
               } 
               if(j==tail)
                  a[tail++]=a[i]; 
            }  
      }
}