Amazon Interview Question
Software Engineer / DevelopersCountry: 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