CareerCup

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.

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)

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

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

HashMap and HashSet will save the day here.

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)

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