CareerCup

1) Sort the first array and search for every element of second array in first using binary search
2) Create a tree of first array and search in the tree with elements from second array

Time Complexity in both the cases : O(nlogn)

Simply insert one array in a hashtable (O(n)), then go through all elements of the second array and lookup in the hashtable (O(m)). Time complexity would be O(n) + O(m) which is O(n) if n>=m.

No need to use sorting/ hashing. It can be done in O(n) with mere array traversals.

Let us say 2 arrays A[1..Na] B[1...Nb] where Na, Nb are size of arrays and Na > Nb.

- Now start traversing both the arrays with startingIndex of A = 1+Na and that of B = 1.
- Traverse each array by 1 element and find save the first index, startI from A where the elements in A and B are equal.
- Continue traversing till all elements from A & B are equal.
- if however any mismatch occurs, reset the startI

$arr1=array("ankush","sameer","manish","rajeev","somesh","mukul");
$arr2=array("rohit","sameer","a","b","c","mukul");
$unique_array=array();
for($i=0;$i<count($arr2);$i++)
{
for($j=0;$j<count($arr1);$j++)
{
//echo "i is ",$arr2[$i],"--","j is ",$arr1[$j],"<br/>";
if ($arr2[$i]==$arr1[$j])
{
$unique_array[]=$arr1[$j];
}
}
}

/// Using Sort + Uniq Method