Write algorithm to compute the intersection of two arrays. What is the time complexity of this algorithm (using the big O notation)?

Question

Rashid · Accepted Answer

You supposed to use hashmaps. And its time complexity is O(n+m). n = length of 1st array and m = length of 2nd array. Here is algoritm in python

def array_intersect(arr1, arr2):
    cache = dict()
    result = []
    for elm in arr1:
        if elm in cache:
            cache[elm] +=1
        else:
            cache[elm] = 1

    for elm in arr2:
        if elm in cache:
            result.append(elm)
            cache[elm] -=1

    return result

Nikolai · Answer

def intersect(a1,a2)
    h = a1.inject(Hash.new(0)){|h,el| h[el] += 1; h}
    a2.select{|el| h[el]-=1; h[el] >= 0}
end

intersection to inordered array · Answer

for(int i=0;i

intersection to ordered array · Answer

int printIntersection(int arr1[], int arr2[], int m, int n)
{
  int i = 0, j = 0;
  while (i < m && j < n)
  {
    if (arr1[i] < arr2[j])
      i++;
    else if (arr2[j] < arr1[i])
      j++;
    else /* if arr1[i] == arr2[j] */
    {
      printf(" %d ", arr2[j++]);
      i++;
    }
  }
}

Booking.com

Pergunta de entrevista da empresa Booking.com

Respostas da entrevista

Empresas seguidas

Buscas de vagas