Interview Question for Software Engineer at Google:

Should clarify what intersection means, after that it's pretty straightforward

vector<int> SortedIntersection(int *a, int an, int *b, int bn)
{
    vector<int> result;
    // assuming asscending order.
    int *aend = a + an;
    int *bend = b + bn;

    while (a != aend && b != bend)
    {
        int candidate = *a;
        ++a;

        while (*b < candidate && b != bend)
        {
            ++b;
        }

        if (b != bend && candidate == *b)
        {
            result.push_back(candidate);
            ++b;
        }
    }

    return result;
}

It can be solved in O(nlogn) . For each number in the 1st array, do a binary search in the second one, if found - try comparing the two subsets.

This post has been removed. Please see our Community Guidelines or Terms of Service for more information.