Bloomberg LP Interview Question
Financial Software Developersmaintain a hash table for the first array(O(n) space) and then scan through this table to find the elements in array2(O(n)) time.
Sort both arrays which takes O(nlogn)
and search both arrays for a common element which takes O(n)...
How about dynamic programming? For example, for 2 strings, find the longest common substring.
int main(){
char arr1[] = "asdfghqqewty";
char arr2[] = "asdfghqqioiu";
int len1 = strlen(arr1), len2 = strlen(arr2);
sort(arr1, arr1 + len1);
sort(arr2, arr2 + len2);
int index1 = 0, index2 = 0;
while(index1 != len1 && index2 != len2){
if (arr1[index1] == arr2[index2]){
cout<<arr1[index1];
++index1; ++index2;
}else
if(arr1[index1] > arr2[index2])
++index2;
else
++index1;
}
cout<<endl;
return 0;
}
Time O(nlogn)
sort the larger array....for every element in the smaller array...do a binary search in the larger...efficiency o(nlogn)...n is the size of larger array
- Anonymous December 12, 2009