CareerCup

If extra space is available, use hash map to store elements from B. Complexity - O(n)
If extra space is not available and arrays can be changed, sort arrays and then print elements from A not in B. Complexity - O(n logn)
If extra space is not available and arrays cannot be changed, use two loops to check if element of A is present in B. Complexity - O(n2).

If we are allowed to use extra space:
1. Load items from array B into a collection (ex: ArrayList).
2. Loop through items in array A and in the loop check each item if it exists in the array list of B. If not found, print the item.

Efficiency = O(n), where n is number of items in array A.

Suggestions?

I am not sure what the interviewer wanted with this question but if python was an applicable language then after converting A and B into a set A-B would give you your result. Here is a sample code in python
>>> print set([1,3,4,6,9])-set([8,2,3,4])

Use hashmap

Let size of A is m and B is n
1) Put all values of B in std::set() . O(nlogn)
2) Check all values of A in the set(). one by one O(mlogn).
overall : O(max(nlogn,mlogn)).

Sort the smaller array - B
and then perform binary search for each element of array A
print not found numbers.

why would we consider arraylist when complexity matters? Coz anyway arraylist uses array internally which increases number of instructions.?

Let size of A is m and B is n
1) Put all values of B in std::set() . O(nlogn)
2) Check all values of A in the set() if its there dot contains() method O(1)
if its there call remove() i.e. O(1)
we have to check for all m elements so O(m).
now print all the elements of this set.

overall : O(nlogn)+O(n).= O(nlogn) it can be done

Solution using sorting. Sort array b mlogm then for each element in a do a binary search nlogm, so total mlogm + nlogm

import java.util.ArrayList;
import java.util.Arrays;


public class ArrIntersection {

public static ArrayList<Integer> ANotB(int[] a,int[] b){
ArrayList<Integer> c = new ArrayList<Integer>();
Arrays.sort(b);
for (int i=0; i<a.length; ++i){
int idx = Arrays.binarySearch(b, a[i]);
if (idx < 0){
c.add(a[i]);
}
}
return c;
}

public static void main(String[] args){
int[] a = {1,4,3,6,9};
int[] b = {2,8,4,3};
ArrayList<Integer> c = ANotB(a,b);
for (Integer num : c){
System.out.println(num);
}
}
}

Solution with Hash, map b to hash O(m), search every item in a in the hash O(n), so total o(n)+o(m).

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;


public class ArrIntersection {
	
	
	public static ArrayList<Integer> ANotBWithHash(int[] a,int[] b){
		Map<Integer, Boolean> bMap = new HashMap<Integer, Boolean>();
		for (int i=0; i<b.length; ++i){
			bMap.put(b[i], true);
		}
		ArrayList<Integer> c = new ArrayList<Integer>();
		for (int i=0; i<a.length; ++i){
			if (!bMap.containsKey(a[i])){
				c.add(a[i]);
			}
		}
		return c;
		
	}
	
	public static void main(String[] args){
		int[] a = {1,4,3,6,9};
		int[] b = {2,8,4,3};
		ArrayList<Integer> c = ANotBWithHash(a, b);
		for (Integer num : c){
			System.out.println(num);
		}
	}
}

public static void main(String args[]){

int[] A={1,4,3,6,9};
int[] B={2,8,4,3};

for(int i=0;i<A.length;i++){
int count = 0;
for(int j=0;j<B.length;j++){

if(A[i]!=B[j]){
count = count+1;
}
if(count==4){
System.out.print(A[i] + " ");
}
}
}

}