Pergunta de entrevista da empresa LinkedIn

Intersection of 2 number arrays.

Respostas da entrevista

Sigiloso

23 de fev. de 2012

if two array just consist of distinct values, we can use a hashset to do the intersection. In case these two array contains duplicate numbers, we can utilize a hashmap in which the key is the number, and the value is its count. 1. Iterate through the first array and record the numbers and their counts in the hashmap. 2.iterate through the second array. If meet the number that also occurs in the hashmap, decrease its count. 3. iterate through the first array again, and remove the numbers that still in the hashmap by their count.(if count still > 0)

Sigiloso

4 de out. de 2012

1. Sort the two arrays using quicksort (O(nlog(n)) + O(nlog(n)) = O(nlog(n)) 2. Iterate through the first array, checking if the number is present in the second array using binary search (O(n * log(n)) = O(n * log(n)).