## Amazon Interview Question for Software Engineer in Tests

Country: India
Interview Type: In-Person

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

You can do this in linear time.

A. Find Duplicates in Arr1 and Arr2:
1. Add each element in arr1 into a hashmap.
2. Iterate through each element in arr2; if exists in hashmap then add element to arr4
B. Find Uniques in Arr3 and Arr4:
1. Add each element in arr3 into a (new) hashmap.
2. Iterate through each element in arr4; if exists in hashmap then remove from hashmap. If does not exist in hashmap, then add to outputs.
3. add remaining elements from hashmap into outputs.

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

hashmap supposes (key,value) pairs. here we just need hash tables.

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

Oh god..Little more specific in ur answer.i told a simillar algorithm to Tech. HR but he wanted to write codes step by step fr bugs..Actually doesnt matter what type of code,but it shouldnt contain BUGS..SO WRITE CODEEEEEE..

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

Without using extra space, you can just sort all three arrays. Use 'merge' like step to compare elements and find out duplicates in arrays 1 and 2 and place them in array 4. Use 'merge' like step again to scan arrays 3 and 4 to find out the unique elements

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

Also, there can be multiple dups of a single element (For e.g. 1 can exist twice in arr1 and arr 2). If we use hash, we also need to keep the count of each element.

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

Is it an integer array? If it is.. one solution is:
1. Sort array 1, 2 & 3 O(nlogn)
2. Iterate arr1 and arr2 using 2 pointers and find the dups and store it in arr4.O(n)
3. Iterate arr3 and arr4 using 2 pointers and find&return the unique elements.O(n)

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

Method 1: Use a hashset:
Insert all the elements of Arr1[] in a hashset. Check which elements of Arr2[] are present in the hashset. This gives duplicates of Arr1[] and Arr2[]. Apply similar procedure for Arr3[].

Method 2: Use sorting:
Sort Arr1[], Arr2[], and Arr3[] and apply simple procedure like the merge-step of merge sort. Insert an element in Arr4[] only if it is present in all of the arrays.

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

So the pseudo provided above is all good, but actually coding it finds some interesting little tweaks that you must make to complete this successfully.

1. Put all elements of arr1 into a HashMap, unless they are duplicates themselves. If they are duplicates, add to arr4 immediately, unless that value already exists in arr4 (arr4 is expandable ArrayList or equivalent).
2. Compare all elements of arr2 to keys in HashMap. If the values are present AND that value is not already in arr4, then add it to arr4.
4. Load arr3 into the HashMap.
5. Compare all elements of arr4 to the HashMap, and if the value is contained in the HashMap delete it from both the HashMap and arr4. (By eliminating duplicates in previous steps, we don't have to worry about duplicates being present within the HashMap or the Array itself. Therefore we can delete from both safely at this point).
6. Since the arr4 element was deleted, back the iterator up by 1 to make sure we don't skip any elements.
7. Iterate through the HashMap and load any remaining values into arr4.
8. If arr4.size() is 0, output -1, else output arr4's contents

Key points that need addressed: remove duplicates early in the process so they don't cascade to final comparison. Make sure that you use an expandable/retractable array or equivalent to store elements for arr4 as the size is variable. This also allows you to reuse it for final output. Make sure when you delete element from variable length array to back your iterator up by 1 so you don't skip an element.

Time complexity of this algorithm is O(n), and space complexity is also O(n) since the HashMap and arr4 could potentially hold every element of the largest array in the worst case.

The final output for the above test case is: 2, 4, 6, 8

Sample Code:

``````int[] arr1={1,3,5,7,9};
int[] arr2={1,2,3,5,4,1,8,9,7};
int[] arr3={1,3,5,7,9,2,1,4,6,5,8};
ArrayList<Integer> arr4 = new ArrayList();

HashMap<Integer, Integer> filter = new HashMap();

for(int i: arr1){
if(filter.containsKey(i) && !arr4.contains(i)){
}
else{
filter.put(i, i);
}
}

for(int i: arr2){
if(filter.containsKey(i) && !arr4.contains(i)){
}
}

filter.clear();

for(int i: arr3){
filter.put(i, i);
}

for(int i = 0; i < arr4.size(); i++){
if(filter.containsKey(arr4.get(i))){
filter.remove(arr4.get(i));
arr4.remove(i);
i--;
}
}

for(int i: filter.keySet()){
}

if(arr4.size() == 0){
System.out.println("-1");
}
else{
for(int i: arr4){
System.out.println(i);
}
}``````

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

Original Poster, are they only single digit numbers?
If so, you can use bit vector of size=(range of input integers). Set the 0-th bit if you see number 0, 1-th bit if you see number 1, ... etc.
When you see that bit set already when you find a another number corresponding to that position => duplicate found.

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

``````#!/usr/local/bin/python2.7

def solve(first, second, third):
print "Solving the problem"
dict = {}
i = 0
j = 0
while i < len(first):
dict[str(first[i])]=''
i += 1
pass

mid = {}
k = 0
while j < len(second):
if str(second[j]) in dict:
mid[str(second[j])]=''
pass
j += 1
pass

print "Mid : ", mid
res = []
while k < len(third):
if str(third[k]) in mid:
del mid[str(third[k])]
pass
else:
res.append(third[k])
pass
k += 1
pass

for key in mid.keys():
res.append(int(key))
pass
return res

if __name__ == '__main__':
print "Executing script"
first = [1, 2, 3, 4]
second = [3, 4, 5, 6]
third = [4, 6, 7, 8, 9, 10]
print "First : ", first
print "Second : ", second
print "Third : ", third
print "result : ", solve(first, second, third)
pass``````

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

Ruby way:

``````arr1=[1,3,5,7,9]
arr2=[1,2,3,5,4,1,8,9,7]
arr3=[1,3,5,7,9,2,1,4,6,5,8]

arr4=arr2 && arr1
arr3.uniq.each do |e|
arr4.uniq.include?(e) ? puts(e) : puts(-1)
end``````

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

HashMap and HashSet will save the day here.

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

1) Sort A = { 1 3 5 7 9} Sort B = { 1 2 3 5 4 1 8 9 7} - n(log n) using quick sort making sure that duplicates are not there in the array.
2) Use merge sort on A and B with condition
while ( i < len A && j < len B) {
if ( A[i] == B[j]) {
dup[k] = A[i];
i++ ; k++;
} else {
j++;
}
}

3) quick sort C array making sure that duplicates are not in the array
4) Merge C and duplicate with the condition
while ( i < len C && j < len Dup) {
if ( C[i] < Dup[j]) {
Non_dup[k] = dup[i];
i++ ; k++;
} elseif ( C[i] > dup[j])
Non_dup[k] = dup[i];
j++; k++;
} else {
j++; i++;
}
}

the whole operation can be done in n(log(n)) time.

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

Here's a simple way to do it in Python.
1. Make both the arrays(arr1 and arr2) into dictionaries. Compare the keys of both the dicts, if they are the same, then put the elements into a third array (arr4).
2. Convert the arrays (arr4) and arr3) into dictionaries.Compare the keys of both the dicts, if they are the same, then put the elements into another array (arr5).
3.Return arr5

``````def findduplicates(arr1,arr2,arr3):
arr4=[]
arr5=[]
d1={}
d2={}
dicti(arr1,d1)
dicti(arr2,d2)
for k in d1:
if k in d2:
arr4.append(k)
print arr4
d3={}
d4={}
dicti(arr3,d3)
dicti(arr4,d4)
for k in d3:
if k not in d:
arr5.append(k)
if len(arr5)==0:
return -1
else:
return arr5

def dicti(arr,d):
for c in arr:
if c not in d:
d[c]=1
else:
d[c]+=1
return d

arr1=[1,3,5,7,9]
arr2=[1,2,3,5,4,1,8,9,7]
arr3=[1,3,5,7,9,2,1,4,6,5,8]

print findduplicates(arr1,arr2,arr3)``````

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

``````import java.util.HashMap;

public class RemoveArrayDuplicates {

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

int[] arr1={1,3,5,7,9};
int[] arr2={1,2,3,5,4,1,8,9,7};
int[] arr3={1,3,5,7,9,2,1,4,6,5,8};
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
HashMap<Integer,Integer> map1 = new HashMap<Integer,Integer>();
HashMap<Integer,Integer> map2 = new HashMap<Integer,Integer>();
for(int i = 0 ; i < arr1.length; i ++)
{
map.put(arr1[i], i);
}

for(int i = 0 ; i < arr2.length; i ++)
{
if(map.containsKey(arr2[i]))
{
map1.put(arr2[i], i);
}
}
System.out.println(map1.keySet());
for(int i = 0 ; i < arr3.length; i ++)
{
if(!map1.containsKey(arr3[i]))
{
map2.put(arr3[i], i);
}
}
System.out.println(map2.keySet());
}

}``````

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

arr1=[1,3,5,7,9]; arr2=[1,2,3,5,4,1,8,9,7];arr3=[1,3,5,7,9,2,1,4,6,5,8];

Python 3:

a = [1,3,5,7,9]
b = [1,2,3,5,4,1,8,9,7]
c = [1,3,5,7,9,2,1,4,6,5,8]

if len(a) > len(b):
dup = [x for x in a if x in b]
print(dup)
else:
dup = [x for x in b if x in a]
print(dup)

if len(dup) > len(c):
unq = [x for x in dup if x not in c]
print(unq)
else:
unq = [x for x in c if x not in dup]
print(unq)

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

a = [1,3,5,7,9]
b = [1,2,3,5,4,1,8,9,7]
c = [1,3,5,7,9,2,1,4,6,5,8]

if len(a) > len(b):
dup = [x for x in a if x in b]
print(dup)
else:
dup = [x for x in b if x in a]
print(dup)

if len(dup) > len(c):
unq = [x for x in dup if x not in c]
print(unq)
else:
unq = [x for x in c if x not in dup]
print(unq)

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

list1 = [1,3,5,7,9]
list2 = [1,2,3,5,4,1,8,9,7]
list3 = [1,3,5,7,9,2,1,4,6,5,8]

list4 = []
for element in list1:
if element in list2:
list4.append(element)

list5 = list(set(list4).union(set(list3)))
print list5

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.