Amazon Interview Question Software Engineer in Tests
Country: United States
Interview Type: Phone Interview
public Integer[] unique(Integer[] input) {
Integer[] output = new Integer[0];
HashSet<Integer> a = new HashSet<Integer>();
HashSet<Integer> b = new HashSet<Integer>();
for (Integer i : input) {
if (!a.add(i)) {
b.add(i);
}
}
return b.toArray(output);
}
Use Sorting using any nlogn method like heap sort
and then compare if u find more then 1 element , put it in another array...
void findunique(int arr[],int size)
{
int j=0,arr2[size];
heapsort(arr,size);
for(int i =0;i<size;i++)
{
if(i<size-1 && arr[i]==arr[i+1])
{
while(i<size-1 && arr[i]==arr[i+1])
i++;
arr2[j++]=arr[i];
}
}
}
Assuming they don't want the answer array in the same order as the original array, sorting first works fine.
public class ReturnDuplicate {
public static void main(String[] args) {
int array[] = new int[]{2,1,2,4,3,1,5,1};
int[] duplicates = getDuplicates(array);
for(int i=0; i<duplicates.length;i++)
System.out.println(duplicates[i]);
}
private static int[] getDuplicates(int[] array) {
HashSet<Integer> uniqueSet = new HashSet<Integer>();
ArrayList<Integer> duplicates = new ArrayList<Integer>();
for(int i=0 ; i< array.length; i++){
Integer item = array[i];
if(uniqueSet.remove(item))
duplicates.add(item);
else
uniqueSet.add(item);
}
int[] dupArray = new int[duplicates.size()];
for(int i=0; i< duplicates.size(); i++)
dupArray[i] = duplicates.get(i);
return dupArray;
}
}
import java.util.HashSet;
import java.util.Set;
class NumUtils {
public Integer[] nonSingular(Integer[] numbers) {
Set<Integer> allNums = new HashSet<>();
Set<Integer> nonSingularNums = new HashSet<>();
for (Integer number : numbers) {
if (!allNums.add(number)) {
nonSingularNums.add(number);
}
}
return (Integer[])nonSingularNums.toArray();
}
}
Create a BST with node of following type. store the frequency of number in the count.
struct Node {
int data;
int count;
struct Node *left;
struct Node *left;
};
Create a new array by traversing the BST, containing only those values whose count is > 1
you could even make a bst of unique keys and if a duplicate is found append to the array
that way you could save looping through bst after creation
so you would get running time of order O(nlgn)
or making use of hashing will make it even better O(n)
since we need to go through all the elems in the array we cant do better than O(n) hence using hash tables would be best
public static void main(String args[]){
int[] sat = {2,1,2,4,3,1,5,1};
// int[] sat = {1,1,1,1,1,1,1,1,1,1};
HashSet sat1 = new HashSet();
for(int i=0;i<sat.length;i++){
sat1.add(sat[i]);
}
Object[] sat2 = sat1.toArray();
int len1 = sat.length - sat2.length;
for(int j=0;j<sat.length-len1;j++){
System.out.print(sat2[j] + " ");
}
System.out.println();
for(int i=0;i<sat2.length;i++){
int count = 0;
for(int j=0;j<sat.length;j++){
if(sat2[i].equals(sat[j])){
count++;
}
}
if(count>=2){
System.out.print(sat2[i] + " ");
}
}
}
def get_arr(arr)
arr1_1 = []
for i in 0..arr.length-1
for j in i+1..arr.length
if arr[i] == arr[j]
unless arr1_1.include? arr[i]
arr1_1 << arr[i]
end
end
end
end
return arr1_1
end
arr3 = get_arr(arr1)
arr4 = get_arr(arr2)
arr = []
arr = arr.concat(arr3).concat(arr4)
p arr
This code is in ruby
Working C Code, messy though
/* Program to print instances of elements which have duplicates in a given
array */
#include <stdio.h>
#include <stdlib.h>
int* findDupEle(int arr[], int size);
int main(void)
{
int arr[]={2,1,2,4,3,1,5,1};
int size=sizeof(arr)/sizeof(arr[0]);
int *dup=findDupEle(arr, size);//Pointer to the array containing
//duplicates is returned
int i=1;
int k=*dup;
//Printing the elements which have repeats
printf("\nThe Array of Duplicates contains : ");
while(i<=k)
{
printf("%d\t",*(dup+i));
i++;
}
printf("\n");
return 0;
}
//Function that returns the array containing instances of
//elements with duplicates
int* findDupEle(int arr[], int size)
{
if(size==0 || size==1)
{
printf("\nErroneous Input!\n");
abort();
}
int hasha[101]={0};//Sort of hash which accepts values from 1 to 100
int count=0;
int* dup=(int*)malloc(sizeof(int)*size+1);//Dynamically declare and allocate
//memory to the array which is
//going to store duplicates
int i=0,k=0;
while(i<size)
{
if(hasha[arr[i]]==0)//If the value is being seen for
hasha[arr[i]]=1;//the first time this is executed
else if(hasha[arr[i]]==1)
{
dup=dup+1;//dup pointer is incremented
*dup=arr[i];
k++;
hasha[arr[i]]++;//hash is also incremented and hence
//elements which are seen for the 2nd
//time only are put into the dup array
}
i++;
}
dup=dup-k;
*dup=k;
return dup;
}
Algorithm:
foreach element in the array
look if element exist in hashmap
if it doesn't exisit
add to hasmap with count as 1
else
if value of that element from hasmap returns 1
update hashmap value to -1 // -1 values will be skipped from adding it to the
//array
increment counter
output array[counter] = array element // ad to the output array
int[] findUniqueDup(int[ ] input] {
// check for null
//check if array.length = 1;
// In the above cases return -1;
Hashmap hm = new Hashmap();
int value,j -1;
int[] output;
foreach ( int i in input){
Object o = hm.get(i);
if( o == null) // i is not in hashmap so add it in hashmap
hm.put(i,1);
else{
val = hm.get(i);
if(value ! = -1)
hm.put(i,-1);
j++;
output[j] = i;
}
}
return output;
}
import java.util.HashSet;
public class Sample3 {
public static void main(String[] args) {
Integer[] numbers = { 1, 2, 1, 1, 2, 4, 5, 6, 6};
Integer[] result = new Integer[numbers.length];
HashSet<Integer> hs = new HashSet<Integer>();
HashSet<Integer> dups = new HashSet<Integer>();
for (int i = 0; i < numbers.length; i++) {
if (!hs.add(numbers[i])) {
dups.add(numbers[i]);
}
}
System.out.println(dups);
}
}
List<int> st = new List<int>() { 2, 1, 2, 4, 3, 1, 5, 1 };
var r = st.GroupBy(c => c).Where(x => x.Count() > 1);
public class DuplicateInArray {
public static void main(String args[]) {
int[] arr = {2,1,2,4,3,1,5,1};
int[] res = findDuplicate(arr);
System.out.print("[");
for (int i = 0; i < res.length; i++) {
if (i != res.length - 1) {
System.out.print(res[i] + ",");
} else {
System.out.print(res[i]);
}
}
System.out.println("]");
}
public static int[] findDuplicate(int[] arr) {
int[] result;
int size = 0;
HashMap<Integer, Integer> valueToCount = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
if (valueToCount.containsKey(arr[i])) {
valueToCount.put(arr[i], valueToCount.get(arr[i]) + 1);
} else {
valueToCount.put(arr[i], 1);
}
}
size = valueToCount.entrySet().stream().filter((pair) ->
((int)pair.getValue()!=1)).map((_item) -> 1).reduce(size, Integer::sum);
result = new int[size];
int index = 0;
for (Map.Entry pair : valueToCount.entrySet()) {
if ((int)pair.getValue()!=1) {
result[index] = (int) pair.getKey();
index++;
}
}
return result;
}
}
public class DuplicateInArray {
public static void main(String args[]) {
int[] arr = {2,1,2,4,3,1,5,1};
int[] res = findDuplicate(arr);
System.out.print("[");
for (int i = 0; i < res.length; i++) {
if (i != res.length - 1) {
System.out.print(res[i] + ",");
} else {
System.out.print(res[i]);
}
}
System.out.println("]");
}
public static int[] findDuplicate(int[] arr) {
int[] result;
int size = 0;
HashMap<Integer, Integer> valueToCount = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
if (valueToCount.containsKey(arr[i])) {
valueToCount.put(arr[i], valueToCount.get(arr[i]) + 1);
} else {
valueToCount.put(arr[i], 1);
}
}
size = valueToCount.entrySet().stream().filter((pair) ->
((int)pair.getValue()!=1)).map((_item) -> 1).reduce(size, Integer::sum);
result = new int[size];
int index = 0;
for (Map.Entry pair : valueToCount.entrySet()) {
if ((int)pair.getValue()!=1) {
result[index] = (int) pair.getKey();
index++;
}
}
return result;
}
}
Test case:
- Gabriel April 16, 20131) by value, to test the correction of the function
1. normal cases: like some integers in some fixed range
2. very large cases: give some integers which are out of integer range
3. blank cases: give {}
2) by element quantity, to test the speed of the function
1. small set
2. large set
3) give some special test cases, want have the results expected or speed demand