Write a function that computes the intersection of two arrays. The arrays are sorted. Then, what if one array is really larger than the other array?

Question

baskin · Accepted Answer

public static void printIntersectionOfSortedArrays(int []a, int []b) 
	{
		int i = 0, j = 0;
		while (i < a.length && j < b.length) {
			if (a[i] == b[j]) {
				System.out.println(a[i] + " ");
				i++; j++; // INC BOTH
			}
			else if (a[i] < b[j]) {
				i++;
			}
			else {
				j++;
			}
		}
	}

if one array is really larger than the other array:
iterate over smaller ans binary search in larger.

Vagrant · Answer

Don't forget about the case of duplicate values.

A= 1 3 3
B= 2 3 3

You don't want to output 3 twice.

Sigiloso · Answer

It's very interesting that people who are offered a job get very simple questions like this one. It's like they decide in advance whom they hire.

Pavel · Answer

Should be just as simple as O(n)

	public static void printIntersection(int[] a1, int[] a2) {
		int i = 0; int j = 0;
		int n1 = a1.length;
		int n2 = a2.length;
		
		while (i < n1 && j < n2) {
			if (a1[i] == a2[j]) {
				System.out.println(a1[i]);
				i++;
				j++;
			} else if (a1[i] < a2[j]) {
				i++;
			} else {
				j++;
			}
		}
	}

H-can · Answer

O(n log N)
where n size of smaller array
N size of bigger array

public static void printIntersection(int[] arr1, int[] arr2) {

		int[] big = arr1.length > arr2.length ? arr1 : arr2;
		int[] small = arr1.length > arr2.length ? arr2 : arr1;

		for (int i = 0; i  0) {
				while ( n value) end = mid-1;
		}
		return -1;
	}

Sigiloso · Answer

Create a hash table.
hash[50] = 0;

Set hash[array1[i]]  =1 for all elements in array 1.
loop through array2.
if hash[array2[i]] == 1, then true; // the element intersects...

this will work even if array 2 is longer than array 1.

Google

Pergunta de entrevista da empresa Google

Respostas da entrevista

Empresas seguidas

Buscas de vagas