Lab126 Interview Question
Software Engineer / DevelopersCountry: United States
/**
*
*/
package pkg_Arrays;
import java.util.Random;
import java.util.Scanner;
/**
* @author Aswin
*
*/
public class Intersection {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("Enter the max input range for both arrays: ");
Scanner sc = new Scanner(System.in);
int maxNum = sc.nextInt();
System.out.println("Enter number of elements in both arrays: ");
int elemCount = sc.nextInt();
int[] arr1 = new int[elemCount];
int[] arr2 = new int[elemCount];
int[] res = new int[elemCount];
Random rnd = new Random();
System.out.print("arr1: ");
for(int i = 0; i<elemCount; i++){
arr1[i] = rnd.nextInt(maxNum);
System.out.print(arr1[i]+" ");
}
System.out.println();
System.out.print("arr2: ");
for(int i = 0; i<elemCount; i++){
arr2[i] = rnd.nextInt(maxNum);
System.out.print(arr2[i]+" ");
}
System.out.println();
boolean[] bucket = new boolean[maxNum];
for(int k =0; k<maxNum; k++)
bucket[k] = false;
for(int i=0; i<elemCount; i++){
bucket[arr1[i]] = true;
}
int m=0;
for(int j=0; j<elemCount; j++){
if(bucket[arr2[j]]==true){
res[m] = arr2[j];
m++;
}
}
for(int k=0; k<elemCount; k++){
if(res[k]!=0)
System.out.print(res[k]+" ");
}
}
}
Time Complexity: O(m+n)
m = maxNum
n = no. of elem
There are many approach to solve this problem:
- O(N^2) - brute force match between two array.
- O(nlogn) - sort both array in O(NlogN), then compare both the list, that will take O(N)
- O(N) - if array is not too big, then store contain of first array in hashmap, then iterate through the second array and check whether number is there in the hashmap or not.
Objective C solution to this ,
NSArray *interArr1 = @[@1,@3,@6,@10];
NSArray *interArr2 = @[@2,@3,@5,@6];
__block NSMutableArray *interFinalArray = [NSMutableArray new];
[interArr1 enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
if ([interArr2 containsObject:obj]) {
[interFinalArray addObject:obj];
}
}];
C++ solution
int* commonIntegersInArray(int *arr1, int size1, int* arr2, int size2) {
vector<int> result;
if (size1 == 0 || size2 == 0) {
return &result[0];
}
unordered_map<int, int> array1Map;
for (int i=0; i<size1; i++) {
array1Map.insert(make_pair(arr1[i], arr1[i]));
}
for (int i = 0; i < size2; i++) {
if (array1Map.find(arr2[i]) != array1Map.end()) {
result.push_back(arr2[i]);
}
}
return &result[0];
}
Clarification question #1: The arrays you were given are sorted. Ask the interviewer if the function will always be operating on already-sorted arrays or not, since that is a very obvious opportunity for optimization.
Clarification #2: Can the arrays have duplicates of the same value? If they do, should the intersection contain unique values? For example, if each array has 3 copies of the number 7, should the intersection array also have 3 copies of 7, or just one 7? I've assumed the latter in my examples, but either case is a valid real-world problem.
I wrote two functions in C# to find the intersections.
The function with Presorted in the name only works if it's given arrays of ints that are already sorted in ascending order. It doesn't validate that they are sorted, because I didn't want to confuse the intersection code with validation code, so this version simply returns incorrect results if given unsorted arrays. This version runs quicker than the other, because it takes advantage of knowing the arrays are sorted, looping only as many times as the length of the longer array. Loop does min(n,m) iterations, for Time complexity: O(n)
In the function with Unsorted in the same, the arrays need not be sorted. The smaller of the two arrays is copied into a HashSet, and the larger array is looped over. Any element in the larger array that is already in the HashSet is pushed into a new HashSet that is the scratch space for the results. I used the HashSet here because the arrays we have are unsorted, so this gives an O(1) way to be sure we're not putting duplicates into the output. if you clarified that duplicate values are not expected in the input arrays, or preservation of duplicates is desired in the output, you could save some memory and use a temp array here just as is done in the Presorted function. At the end of the function, the result HashSet is copied into the return value array. The intersection is not sorted, the values are in the order they are encountered in the larger of the 2 arrays.
- Adam Smith November 01, 2014