Thomson Reuters Interview Question
Software Engineer / DevelopersTeam: 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.