trickier question, code a method given the following method signature that will print out any numbers that intersect both arrays of numbers

//Example arrays
// 4, 18, 25, 40, 411
// 20, 25, 40, 320, 1009, 1100

void intersect(int[] arr1, int len1, int[] arr2, int len2) {

Question

trickier question, code a method given the following method signature that will print out any numbers that intersect both arrays of numbers

//Example arrays
// 4, 18, 25, 40, 411 
// 20, 25, 40, 320, 1009, 1100 

void intersect(int[] arr1, int len1, int[] arr2, int len2) {

Shards · Accepted Answer

If you want a very simple answer, use hashtable to store the contents of the first list (O(n)). Then, for each member of the second list, check whether the value is in the hashtable (each check is O(1)). We have O(n + m) algorithm that is extremely simple to code.

Sigiloso · Answer

void intersect(int[] arr1, int len1, int[] arr2, int len2) { 
   
 int startIndex = 0;
    //have an outer loop of one of the arrays
    for( int i = 0; i < len1; i ++){
    //have an inner loop of the other array
        for( int j = startIndex; j < len2; j++){
            if(array1[i] == array2[j]){
                System.out.println(array1[i] + "	");
                startIndex = j + 1;
                break;
            }
            else if(array1[i] < array2[j]){
            //skip because less than the number in the second array
                break;
            }
            else{
                startIndex = j++;
            }
        }
    }
}

Osman · Answer

Are both input arrays sorted in ascending order?

Sigiloso · Answer

if sorted then you can avoid the nsquare with binary search

Google

Pergunta de entrevista da empresa Google

Respostas da entrevista

Empresas seguidas

Buscas de vagas