CareerCup

Google Longest common subsequence..You can easily tweak it to output only non duplicates.

Use hash table (hash_set in STL). Put first sequence into this hash table (O(n))
Search each element in second sequence in the hash table (O(n) * O(1))
In case of duplicate preserving case use multiset

Scan both arrays left to right:
- if there is an smaller element, skip that number
- if numbers are same, include that in result and advance both indices:
- if non duplicate mode is selected, then advance both counters so numbers are distinct again.

I have done this one in 1 scan of both arra.........
while(a[i]&&a[j])
{ if(a[i]==a[j])
{ //store result in other array
i++;j++;
}
elseif(a[i]<a[j])
i++;
else
j++;
}


for non duplicate mode we can check whether current match no is equal to last match element.

<pre lang="" line="1" title="CodeMonkey1122" class="run-this">import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;

/**
*
* * @param <T>
* A common problem is to generate the intersection of two sequences.
* A sequence is a sorted list of objects that are ordered according to some comparison operation.
* I need two functions (or one function with some type of switch parameter)
* that provide an intersection of two sequences.
* In one case, I want to only output an intersection of the sequence,
* but if there are duplicate values in the sequence, only output one object.
* In the other, preserve duplicates. For example, take two sequences:
* A: 1, 3, 3, 7, 7, 7, 8
* B: 2, 3, 7, 7, 9
*/
public class A14SequenceIntersection<T extends Comparable<? super T>> {


/**
* @param first
* @param second
* @param includeDuplicates
* @returns an Array of common elements (intersection)
*/
@SuppressWarnings({ "unchecked", "hiding" })
public<T> T[] intersectSequences(T[] first, T[] second, boolean includeDuplicates){
if(first == null || second == null) throw new IllegalArgumentException(" One of the arrays is empty");
HashSet<T> noDuplicates = new HashSet<T>();
LinkedList<T> duplicates = new LinkedList<T>();
for(int i = 0; i < first.length; i++) {
int index = Arrays.binarySearch(second, first[i], null);
T c = null;
if(index >= 0){
c = second[index];
}
if(c != null){
if(includeDuplicates){
duplicates.add(first[i]);
} else {
noDuplicates.add(first[i]);
}
second = removeElementAtIndex(second, index);
}
}
if(includeDuplicates){
return (T[]) duplicates.toArray(new Object[0]);
} else {
return (T[]) noDuplicates.toArray(new Object[0]);
}

}
/**
* @param <T>
* @param second
* @param index
* @returns the Array -1 element at index...
*/
@SuppressWarnings({ "unchecked", "hiding" })
private<T> T[] removeElementAtIndex(T[] second, int index) {
if(second == null || second.length < 2) return second;
T[] result = (T[]) new Object[second.length-1];
for(int i=0, j=0; i < second.length; i++){
if(i!=index){
result[j++]=second[i];
}
}
return result;
}

/**
* @param args
*/
public static void main(String[] args) {
A14SequenceIntersection<Integer> sequenceIntersection = new A14SequenceIntersection<Integer>();
Integer[] first = new Integer[]{1, 3, 3, 7, 7, 7, 8};
Integer[] second = new Integer[]{1, 3, 3, 7, 7, 7, 8};
Object[] duplicates = sequenceIntersection.intersectSequences(first, second, true);
for (Object r : duplicates) {
System.out.printf("%s ", r);
}
System.out.println();
Object[] nonDuplicates = sequenceIntersection.intersectSequences(first, second, false);
for (Object r : nonDuplicates) {
System.out.printf("%d ", r);
}
}

}

</pre><pre title="CodeMonkey1122" input="yes">
</pre>

void findwithdups(int a[],int n,int b[],int m)
{
printf("In With Duplicates\n");
int i=0,j=0;
while(i<n && j<m)
{
if(a[i]==b[j])
{
printf("Element matched %d\n",a[i]);
i++;
j++;


}
else{

if(a[i]>b[j])
{
j++;

}
else{
if(a[i]<b[j])
i++;
}
}
}

}

void findwithoutdups(int a[],int n,int b[],int m)
{
printf("In Without Duplicates\n");
int i=0,j=0,prev=0;
while(i<n && j<m)
{
if(a[i]==b[j])
{
if(prev == a[i])
{
printf("Duplicate found %d\n",a[i]);



}
else{
printf("Element matched %d\n",a[i]);
prev=a[i];

}
i++;
j++;


}
else{

if(a[i]>b[j])
{
j++;

}
else{
if(a[i]<b[j])
i++;
}
}
}




}

/**
Pre-condition:
-arr1 and arr2 are sorted
-arr3 contain enough space for the solution
Output variable:
-arr3 return the solution array of size arr3Len
-arr3Len size of arr3
**/
bool fIntersection(int arr1[],int arr1Len,int arr2[],int arr2Len,int arr3[],int *arr3Len, bool AllowDuplicate=false)
{
int i=0;
int j=0;
*arr3Len=-1; //initialize answer

//if we reach the end of any list, it the end
while(arr1Len>i && arr2Len>j) {
if((AllowDuplicate && arr1[i]==arr2[j]) || (arr1[i]==arr2[j]&&(*arr3Len==-1 || arr1[i]!=arr3[*arr3Len]))) {
arr3[++(*arr3Len)]=arr1[i];
i++;
j++;
} else if (arr1[i]>arr2[j]) {
j++;
} else {
i++;
}
}
*arr3Len+=1; //value was initialized at -1 due to loop condition, fix final size
return true;
}

Could of allocated memory but not knowing the size of the output, i preferred not to jump into those solution... wouldn't want to over allocate memory from the function...
All memory allocated dynamically need to be removed, I will have to search a bit more about it for cpp to not create any issue...
That the main reason I gave the solution this way...