Amazon Interview Question
Software Engineer in TestsCountry: India
Interview Type: In-Person
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..
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
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.
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.
3. Clear your HashMap
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)){
arr4.add(i);
}
else{
filter.put(i, i);
}
}
for(int i: arr2){
if(filter.containsKey(i) && !arr4.contains(i)){
arr4.add(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()){
arr4.add(i);
}
if(arr4.size() == 0){
System.out.println("-1");
}
else{
for(int i: arr4){
System.out.println(i);
}
}
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.
#!/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
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.
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)
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());
}
}
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)
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)
You can do this in linear time.
- jx33wang September 18, 2013A. 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.