## Thomson Reuters Interview Question for Software Engineer / Developers

Team: Eikon
Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
4
of 4 vote

1. Load the items of the array A into a HashSet S. Each insert will take amortized O(1) time.
2. 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.

Comment hidden because of low score. Click to expand.
0

could u plz give the code in c language

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

``````public void displayCommonElements(int []a1,int []a2)
{
Hashtable<Integer,Integer> temp = new Hashtable<Integer,Integer>();
for(int i : a1)
temp.put(i,0);
for(int i : a2)
if(temp.containsKey(i))
System.out.print(i + " ");
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

why do you need to sort them both if you're iterating one and searching in the other?

Comment hidden because of low score. Click to expand.
1
of 1 vote

If we are doing binary search over second array, why sorting first array is needed?

Comment hidden because of low score. Click to expand.
0

damn..dis as asked in yahoo to m friend..he got thro..

Comment hidden because of low score. Click to expand.
0

You are assuming that both the arrays are of the same length 'n'

Comment hidden because of low score. Click to expand.
0
of 0 vote

CommonElement(int A[], int i, int B[], int j){
if ( i < 0 II j < 0) return;
else{
if (A[i] == B[j] ) {
common[++k] = A[i] ; // Global K =-1
CommonElement(A,i-1,B,j-1);
}
else{
CommonElement(A,i,B,j-1);
CommonElement(A,i-1,B,j-1);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)) {
i++;
j++;
}
}
return c;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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++;
}

}
iCount = 0;
for (int j = 0; j < Array2.Length; j++)
{
if (iDict.ContainsKey(Array2[j]))
{
if (!retDict.ContainsKey(Array2[j]))
{
Console.WriteLine("Matching Element: " + Array2[j]);
}
}
}

return retDict;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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++) {
}
for(int i = 0; i < b.length ; i++) {
if(hashSet.contains(b[i])) {
System.out.println("COMMON : "+b[i]);
return b[i];
}
}
return 0;``````

}

Comment hidden because of low score. Click to expand.
1
of 1 vote

implemenation of hash table is not desirable because the array may contain a very large element which is greater than the size of array ..so it may so happen that your space complexity cab be very large..so better to sort the array

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def commonElements(a1,a2):
for element in a2:
if element not in a1:
a2.remove(element)
return a2``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.