## Amazon Interview Question for Software Engineer / Developers

Team: Amazon Instant Video
Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
1
of 1 vote

Most of the answers above are based on Hashtables. I tried the solution with sorting and merge operations.

``````static List<Integer> intersect(int[] a, int[] b) {
Arrays.sort(a);
Arrays.sort(b);

int N = a.length;
int M = b.length;

int aPos = 0;
int bPos = 0;

List<Integer> result = new ArrayList<Integer>();
while(aPos < N && bPos < M) {

if(a[aPos] == b[bPos]) {

// if Duplicates...
if(result.size() == 0 || result.get(result.size() - 1) != a[aPos])

++aPos;
++bPos;
}

else if(a[aPos] < b[bPos]) ++aPos;
else if(a[aPos] > b[bPos]) ++bPos;

}

return result;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package careerCup;

import java.util.HashSet;
import java.util.Set;

/* problem Statement: find out common element in two arrays*/

public class CommonElement {
public static void main(String[] args){
int[] myfirstArray={4,1,2,3,4,5};
int[] mySecondArray={4,5,7,1,8,9};
Set<Integer> s=new HashSet<Integer>();
//System.out.println("common elements are: ");
for(int i=0;i<myfirstArray.length;i++){
for(int j=0;j<mySecondArray.length;j++)
if(myfirstArray[i]==mySecondArray[j]){
//System.out.print( myfirstArray[i]+" ");

}

}
System.out.println(s);

}

}``````

Comment hidden because of low score. Click to expand.
0

I believe you can optimize it :) currently it's complexity is O(n^2)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````<?php

\$arr1 = array(9,2,10,4,11,6,7,8,1);
\$arr2 = array(12,14,6,8,11);

print_r(intersect(\$arr1, \$arr2));

function intersect(\$arr1, \$arr2){

sort(\$arr1);
sort(\$arr2);

foreach (\$arr1 as \$value1) {
foreach (\$arr2 as \$value2) {
if (\$value1 == \$value2) {
\$result[] = \$value1;
break;
}else if (\$value1 < \$value2) {
break;
}
}
}
return \$result;
}

?>``````

Comment hidden because of low score. Click to expand.
0

sorry dude...but this is O(mn) or generically speaking O(n^2). :( . You can do O(m) assuming n is very very small compared to m ( where n and m are the input array sizes ). Do correct me in case I have misunderstood what you are trying to do in your code.

Or you could use some extra memory to put them into data structures like hashsets.

Am curious: wasnt there any condition to this? like you got to be within some decent efficiency limits? or cannot use extra memory??

Comment hidden because of low score. Click to expand.
0
of 0 vote

string GetCommonElements(char* array1,char* array2,unsigned length1,unsigned length2)
{
if(!array1 || !array2 || length1<=0 || length2<=0){
return "";
}

char v_char[256];

for(int i=0;i<256;++i){
v_char[i]=0;
}

for(int i=0;i<length1;++i){
v_char[array1[i]]++;
}

string str_ret;
for(int i=0;i<length2;++i){
if(v_char[array2[i]]!=0){
str_ret.push_back(array2[i]);
}
}
return str_ret;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.*;
public class Common
{
public static void func(int [] array1,int[] array2)
{
HashSet<Integer> al=new HashSet<Integer>();
HashSet<Integer> all=new HashSet<Integer>();
for (int i:array1)
{
}
for (int j:array2)
{
}

al.retainAll(all);
System.out.println(al);
}
public static void main(String args[])
{
int[] array1={1,2,3,4,3,2,1,2,3,4,5,6,4,3,2};
int[] array2={4,7,6,5,4,5,6,7,5,5,8,9,0};
func(array1,array2);

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````We can do it with O(m) where m>n, m and n being
the number of elements in two arrays.

/** SUFFICIENT_SIZE is just an assumption, we need
to re-size the array based on some condition and
re-Hash the table after re-sizing. For now please
ignore this and assume that the SUFFICIENT_SIZE is
just sufficient to accommodate the  elements.*/

{
int maxCount = (m>n) ? m : n;
Integer[] hashTable = new Integer[SUFFICIENT_SIZE];
for(int i =0; i<maxCount; i++)
{
//Find hashCode for the elements of both the
array.
int firstHashCode = hash( firstArray[i] );
int secondHashCode = hash( secondArray[i] );

//Find hash table index for elements of both the array.
int firstHashTableIndex = findIndex( firstHashCode );
int secondHashTableIndex = findIndex( secondHashCode );

//Add the elements in the hashTable, if there
is a collision and the equals method finds the same
element at that index, we have found the common
element.

......Code for adding elements to the hashTable follows......

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

//ArrayList<Integer> array = new ArrayList<Integer>();
Integer arr[] = { 1,3,2,4,5,4,2 };
Integer arr1[] = { 8,6,7,3,4,1,2 };

HashSet<Integer> hs=new HashSet<Integer>();
hs=(HashSet) compareArray(arr,arr1);
System.out.println(hs);
}
public static Set compareArray(Integer arr1[],Integer arr2[]){
HashSet hs= new HashSet();
for(int ar1:arr1){
System.out.println("Arr1->"+ar1);
for (int ar2: arr2){
System.out.println("Arr2->"+ar2);
if(ar1==ar2){
}
}
}
return hs;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

list1=[1,2,3,4,5,6,7,8,9]
list2=[2,4,6,8,10]
dict1={}
list3=[]
for i in list1:
dict1[i]=1
for i in list2:
try:
if dict1[i]==1:
list3+=[i]
except:
continue
print list3

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.