CareerCup

#include<stdio.h>
#include<stdlib.h>
int compar(const void *x1, const void *x2)
{
        return *((int *)x1) - *((int *)x2);
}
int main()
{
        int arr1[] = {1,2,3,2,3,2};
        int arr2[] = {2,2,3,3,4,5};
        int *resultSet;
        int len1, len2, len;
        int i, j, k;
        len1 = sizeof(arr1)/sizeof(int);
        len2 = sizeof(arr2)/sizeof(int);
        len = len1 < len2 ? len1 : len2;

        resultSet = malloc(sizeof(int) * len);
        qsort(arr1, len1, sizeof(int), compar);
        qsort(arr2, len2, sizeof(int), compar);
        i = j = k = 0;

        while( i < len1 && j < len2)
        {
                if(arr1[i] == arr2[j])
                {
                        resultSet[k] = arr1[i];
                        i++;
                        k++;
                        j++;
                }
                else if(arr1[i] > arr2[j])
                        j++;
                else
                        i++;
        }
        for(i = 0; i < k; i++)
                printf("%d ", resultSet[i]);
        printf("\n");
        return 0;
}

How does that become the largest common subarray ??? why {2,2,3,3} and not 2,3

Why destroying the structure ?

Better time complexity -

public static int[] findLargestCommonSub(int[] arr1, int[] arr2){
		if(arr1 == null || arr1.length <= 0 ||
				arr2 == null || arr2.length <= 0) return null;
		
		Map<Integer, Integer> map = new LinkedHashMap<Integer, Integer>();
		int result[] =  new int[ arr1.length > arr2.length ? arr2.length : arr1.length ];
		int k = 0;
		for(int i = 0; i < arr1.length; i++){
			map.put(arr1[i], (map.get(arr1[i]) == null ? 1 : map.get(arr1[i])+1));			
		}
		for(int j = 0; j < arr2.length; j++){
			if(map.containsKey(arr2[j])){
				result[k++] = arr2[j];
				if(map.get(arr2[j]) > 1){
					map.put(arr2[j], map.get(arr2[j])-1);
				}else{
					map.remove(arr2[j]);
				}
			}				
		}
		return result;
	}

DP solution O(n^2) time and space:
Let:

OPT[x][y] be the length of the longest common sub-array between two prefixes A[1..x] and B[1..y].

Then, the recursive formula is:

OPT[x][y] 	= max(OPT[x][y-1], OPT[x-1][y], OPT[x-1][y-1] + 1), if A[x] = B[y];
			= max(OPT[x][y-1], OPT[x-1][y]), if A[x] != B[y];

Initial values:

OPT[i][j] = 0 for all i, j;
Note: we consider indices start from 1;

The length of the longest common sub array is:

OptLen = OPT[n][m];// n = size of A, m = size of B

To find such a longest common sub array itself, we can trace back by using OPT table and the recursive formula.

This can be implemented in O(n^2) time and space.

Modified Merge Sort problem.

Using a map like what Sathish does is probably best O(n + m) and O(n) memory (cleaned up a bit so it's easier to read):

public static int[] getCommonArray(int[] arr1, int[] arr2){
	HashMap<Integer, Integer> instanceCountMap = new HashMap<Integer, Integer>();
	for(int i : arr1){
		Integer count = instanceCountMap.get(i);
		if(count == null){
			instanceCountMap.put(i, 1);
		}
		else{
			instanceCountMap.put(i, count + 1);
		}
	}
	ArrayList<Integer>results = new ArrayList<Integer>();
	for(int i : arr2){
		Integer count = instanceCountMap.get(i);
		if(count != null){
			results.add(i);
			if(count > 1){
				instanceCountMap.put(i, count -1);
			}
			else{
				instanceCountMap.remove(i);
			}
		}
	}
	int[] resultArr = new int[results.size()];
	for(int i = 0; i < resultArr.length; i++){
		resultArr[i] = results.get(i);
	}
	return resultArr;
}

Step 1) Sort both arrays : O(nlogn)
Step 2) Traverse through the list : O(n)
a. If array1[i] = array2[j]; add it to result and i++, j++
b. if array1[i] > array[j]; then j++;
c. else if array1[i] < array[j]; then i++;

# Total complexity will be O(nlogn).

kind of merge sort.

void solve()
{
	using namespace std;

	vector<int> set1 = { 1, 2, 3, 2, 3, 2 };
	vector<int> set2 = { 2, 2, 3, 3, 4, 5 };
	vector<int> resultSet;

	sort(set1.begin(), set1.end());
	sort(set2.begin(), set2.end());

	auto it = set2.begin();
	
	for (auto value : set1)
	{
		if (value == *it) {
			resultSet.push_back(value);
			++it;
			continue;
		}
		
		while ((value > *it) && (it != set2.end()))
			++it;

		if (it == set2.end())
			break;
	}
}

{
public static void main(String[] args)
{
int [] arr1 = {1,2,3,2,3,2};
int [] arr2 = {2,2,3,3,4,5};
int [] same= new int[arr1.length];
int size=0;
int [] skip= new int[arr2.length];

for(int i=0; i<skip.length; i++)
{
skip[i]=0;
}

for(int i=0; i<arr1.length; i++)
{
for(int x=0; x<arr2.length; x++)
{
if(skip[x]==0)
{
if(arr1[i]==arr2[x])
{
same[size]=arr1[i];
size++;
skip[x]=1;
}
}
}
}

for(int i=0; i<size; i++)
{
System.out.print(same[i]);
}
}
}