## Thomson Reuters Interview Question

Software Engineer / Developers**Team:**Eikon

**Country:**United States

**Interview Type:**In-Person

Can u please elaborate o your answer.. Y Inserting an array data into a hashset will take O(1) time. ??? and how the overall process took O(n) time.

Sort array A --> nlogn time

Sort array B -->nlogn time

Now binary search each element of one array to other. takes nlogn+nlogn time

Total nlogn time

It is possible to optimize 2nd step to O(n).

Steps:

1. Assuming we have two array sorted in ascending order. say arr1 and arr2.

2. Traverse through both array,starting from index 0.

3. if arr1[i]==arr2[j] then found matching element.

else if arr1[i]<arr2[j] then i++

else j++;

In steps, I am putting only logic not boundary conditions.

@predequp your solution does improve the performance. But over all it is still O(n * ln n) due to the sorting where the n is the longest length of those two arrays.

solution 1

use HashSet as suggested

solution 2

sort one array and binary search every element in another array

solution 3

sort both arrays, traverse them at the same time and add the same element

```
public ArrayList<Integer> intersect(ArrayList<Integer> a, ArrayList<Integer> b)
{
ArrayList<Integer> c = new ArrayList<Integer>();
int i = 0;
int j = 0;
while(i < a.size() && j < b.size()) {
for(; i < a.size() && j < b.size() && a.get(i) < b.get(j); i++);
for(; j < b.size() && i < a.size() && b.get(j) < a.get(i); j++);
if(i < a.size() && j < b.size() && a.get(i) == b.get(j)) {
c.add(a.get(i));
i++;
j++;
}
}
return c;
}
```

```
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class Program
{
static void Main(string[] args)
{
IntegerFunctions iFunc = new IntegerFunctions();
int[] Array1 = new int[] { 0, 1, 5, 7, 3, 4, 5, 6, 3, 11 };
int[] Array2 = new int[] { 7, 23, 1, 1, 1, 7, 8, 11, 11 };
iFunc.GetCommonItems(Array1, Array2);
}
}
public class IntegerFunctions
{
internal Dictionary<int, int> GetCommonItems(int[] Array1, int[] Array2)
{
Dictionary<int, int> retDict = new Dictionary<int, int>();
if (Array1.Length == 0 || Array2.Length == 0) return retDict;
int iCount = 0;
Dictionary<int, int> iDict = new Dictionary<int, int>();
for (int i = 0; i < Array1.Length; i++)
{
if (!iDict.ContainsKey(Array1[i]))
{
iCount++;
iDict.Add(Array1[i], iCount);
}
}
iCount = 0;
for (int j = 0; j < Array2.Length; j++)
{
if (iDict.ContainsKey(Array2[j]))
{
if (!retDict.ContainsKey(Array2[j]))
{
retDict.Add(Array2[j], iCount);
Console.WriteLine("Matching Element: " + Array2[j]);
}
}
}
return retDict;
}
}
```

Implementation in java by using hashset.

```
public int common(Integer[] a, Integer[] b) {
HashSet hashSet =new HashSet();
for(int i = 0; i < a.length ; i++) {
hashSet.add(a[i]);
}
for(int i = 0; i < b.length ; i++) {
if(hashSet.contains(b[i])) {
System.out.println("COMMON : "+b[i]);
return b[i];
}
}
return 0;
```

}

1. Load the items of the array A into a HashSet S. Each insert will take amortized O(1) time.

- CameronWills November 13, 20122. Iterate through the integers of array B and check if the HashSet contains the integer. Each lookup also takes O(1) time.

So the overall algorithm is O(n) time.