CareerCup

Yes. That seemed to be the right approach to me also. If we know the numbers are all less than M, we can use counting sort which is O(n), comparison takes O(n) time.
Here is a sample implementation using quicksort.

#include <stdio.h>

#define M    8
#define N    8
#define SIZE 10

void swap(int s[], int i, int j) {
    int temp;
    temp = s[i];
    s[i] = s[j];
    s[j] = temp;
}

void quicksort(int s[], int l, int h) {
    int i, last;
    
    if(l>=h)
        return;
        
    for(last=l, i=l+1; i<=h; i++)
        if(s[i]<s[l])
            swap(s, i, ++last);
    swap(s, l, last);
    
    quicksort(s, last+1, h);
    quicksort(s, l, last-1);
}

int main() {
    int s[N] = {2,5,6,8,10,2,3,5};  // array1 of size N
    int t[M] = {4,7,3,5,2,10,2,4};  // array2 of size M
    int r[SIZE];                    // result array
    int i, j, k;
    
    // sort the arrays
    quicksort(s, 0, 7);
    quicksort(t, 0, 7);
    
    i = j = k = 0;
    while(i<N && j<M) {
        if(s[i]==t[j]) {
            r[k++] = s[i];
            i++;
            j++;
        } else if(s[i] > t[j])
            j++;
        else
            i++;
    }
    
    for(i=0; i<k; i++)
        printf("%2d  ", r[i]);
    printf("\n");
    
    return 0;
}

Thanks for correction

Is it possible to show more specific flow in c/c++/java language?

Thanks,

We can also construct BST for larger array..instead of smaller...To reduce the Time complexity..

Now Timecomplexity will be
O(n*log(m))
m--larger array for which BST was constructed
n--smaller arrat

We can also construct BST for larger array..instead of smaller...To reduce the Time complexity..

Now Timecomplexity will be
O(n*log(m))
m--larger array for which BST was constructed
n--smaller arrat

Well I guess the interview said that there is no space for hashmap. If that's true then hashmap would have reqd O(n) space which is the same as binary tree. So I guess maybe he wouldn't be much happier with Binary tree soln as well

Well another alternative is to use count sort if the range is small.Its not directly dependent on N but its rather dependent in the range of the numbers contained in the array. So if the range is small space can be saved.

Or yet another alternative is that if the repetitions r small then probably use a bit vector and assign lets say 4 bits per number. This would allow us a maximum repetitions upto 16. Assigning 4 bits per number vl still save a lot of space then assigning rather conventional 32 bits for a number.

I've asked the interviewer the range of numbers, he said that the range is just as large as the integer. Since I would say, if the range is smaller, we can use bucket sort or radix sort. However, it's not possible to do that.

the problem with the BST or any other searching method like binary search is flawed with the presence of duplicate integers in the array
{2,2} and {2,2,2} and if you create the BST for the first array the o/p has to be {2,2,2} which is wrong and should be {2,2} unless you add additional data to maintain if a particular node in the BST was selected earlier which nullifies the constraint of additional space

i guess the approach of sorting both arrays and maintaining two separate pointers for both the arrays is a better approach
here we increment both the pointers on a hit and increment the pointer with a smaller value on miss till we reach the end of the list.
on hit we print the value

so the overall complexity would be if one array is of size m and other is of size n then
complexity is mlogm+nlogn+n+m
and if n>>m then it is nlogn