CapitalIQ Interview Question
ConsultantsCountry: India
Interview Type: Phone Interview
we can do this with O(nlogn) complexity...by using binary search tree..
1.sort any one array.
2.From the second array take one one element and do binary search tree in the sorted array ..if element is present insert that element in binary search tree..
3. if the element is already present just increment the count at that node..
4.after all the elements in the second array traverse the binary search tree and display the elements only whose count value is 1..
it takes O(nlogn).
if the arrays the same in size
sorting=O(nlogn)
searching=O(nlogn)
for BST O(nlogn)..
else
small change but ~==O(nlogn)..
You can do this in linear time, O(n), using hashset.
- Anonymous June 19, 20131. Add all the elements of one array into hashset.
2. loop over the elements of second array and check if it is present in hashset. If it is then add it to the result array.