Given two sorted integer arrays, write an algorithm to get back the intersection.

Question

chandra shekhar · Accepted Answer

for(int i=0,j=0; i  ar2[j])
                                j++;
                        else {
                                i++; j++;
                        }
                }

NoOne · Answer

vector SortedIntersection(int *a, int an, int *b, int bn)
{
	vector 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;
}

Anonymous · Answer

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

dmn · Answer

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.

Google

Google interview question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches