## Amazon Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**In-Person

```
using System;
using System.Collections;
using System.Linq;
using System.Text;
namespace HashTableDemo
{
class Program
{
static void Main(string[] args)
{
Hashtable ht = new Hashtable();
int [] arr = { 1, 2, 3, 4, 5, 5, 4, 3, 2, 8, 6, 3, 5, 7, 3, 2 };
int x;
for (int i = 0; i < arr.Length; i++)
if (ht.Contains(arr[i].ToString()))
{
x = (int)ht[arr[i].ToString()];
ht[arr[i].ToString()] = ++x;
}
else
ht[arr[i].ToString()] = 1;
foreach (DictionaryEntry e in ht)
Console.WriteLine(e.Key);
}
}
}
```

- RAHUL

<pre lang="" line="1" title="CodeMonkey74814" class="run-this">import java.util.*;

import java.util.HashSet;

import java.io.*;

import java.lang.*;

class RemoveDuplicated {

public static void main(String[] args){

RemoveDuplicated RD = new RemoveDuplicated();

String input = "thestringisduplicatedqwertyuio";

String output = RD.InsertToHashSet(input);

System.out.println(output);

}

public String InsertToHashSet(String input){

HashSet<String> CheckDuplicate = new HashSet<String>();

String output="";

int i,j;

j = 0;

for(i=0;i<input.length();i++)

{

String current = "";

current += input.charAt(i);

if(CheckDuplicate.contains(current)) //check if the char is already in the HashSet,if yes,do nothing

continue;

else { //if not,add current char to HashSet and put it in the output

CheckDuplicate.add(current);

output = output + current;

j++;

}

}

return output;

}

}

</pre><pre title="CodeMonkey74814" input="yes">

</pre>

public static void removeDuplicates(char[] str)

{

if (str == null) return ;

int len = str.length;

if(len<2) return ;

int tail = 1;

for ( int i=1; i<len ; ++i)

{

int j;

for ( j = 0 ; j<tail ;++j)

{

if(str[i] == str[j])

break ;

}

if(j ==tail)

{

str[tail] = str[i];

++tail;

}

}

str[tail] =0;

}

```
package arrays;
/**
* remove duplicate integers in array
*
*
*/
public class RemoveDuplicatesInArray {
public static void main(String [] args){
int a[] = {1,1,1,1};
int tail = 1;
for (int i = 1;i<a.length;i++){
int j =0;
for(;j<tail;j++){
if (a[j] == a[i]){
break;
}
}
if(j==tail){
a[tail]= a[i];
tail++;
}
}
for (int i=0;i<tail;i++) {
System.out.print(a[i]);
}
}
}
```

I recently received this question in an early Google interview, so this is a pretty important question.

I did mine in Java with HashSet and this is what I got.

```
//O(2n) two passes, one for first for loop, second for toArray method
public static Integer[] uniqueHashElement(Integer[] startArray)
{
//CAN'T DO Set<integer> set = new Set because it's abstract
Set<Integer> set = new HashSet<Integer>();
int numItemsFound = 0;
for (int i = 0; i < startArray.length; i++)
{
set.add(startArray[i]);
}
Integer[] result = new Integer[set.size()];
return set.toArray(result);
}
```

public class Removeduplicatenumber {

public static void main(String args[])

{

int array[] = { 10, 20, 30, 20, 40, 40, 50, 60, 70, 80 };

int size = array.length;

System.out.println("Size before deletion: " + size);

for (int i = 0; i < size; i++)

{

for (int j = i + 1; j < size; j++)

{

if (array[i] == array[j])

{

while (j < (size) - 1)

{

array[j] = array[j + 1];// shifting the values

j++;

}

size--;

}

}

}

System.out.println("Size After deletion: " + size);

for (int k = 0; k < size; k++)

{

System.out.println(array[k]); // printing the values

}

}}

Add the items to a set as you go and check to see if each item is already in the set. Every time you find a new item that isn't in the set, do array[numItemsFound] = array[currentIndex]; numItemsFound++; Complexity is O(n) and needs O(n) extra space. If you can't use extra space, an in-place sort might be the best bet, giving you O(n log n) or O(kn) if you use radix sort. If you can't use extra space AND you also can't re-order the original array, you're probably stuck checking every element with every element, O(n^2)

- eugene.yarovoi October 17, 2011