My interview question was to find duplicates in two arrays.
array1 = [1,2,4,6,9,50,34];
array2 = [1,5,4,50,24,78,34];
I know the code for this is to use two for loops:
for(int i=0; i<arr1.length; i++){
for(int j=0; j<arr2.length; j++) {
if(arr1[i]==arr2[j]) {
System.out.println(arr1[i]);
}
}
}
The interviewer asked for a better method with much iteration. Can I get any suggestions regarding this?
The code with two loops is O(m*n), where m and n are array sizes. You can do better than that if you put the content of one array into a hash-based container, say, HashSet<T>, and then go through the items of the second array, checking if they are in the hash set or not. This has the complexity of O(m+n), i.e. linear in the total number of elements in both arrays.
As dasblinkenlight said before me:
public static void main(String[] args) {
int[] arr1 = new int[] { 10, 3, 4, 20};
int[] arr2 = new int[] { 10, 20, 30 };
//convert arr1 to java.util.Set
Set<Integer> set1 = new HashSet<Integer>();
for (int i : arr1) {
set1.add(i);
}
// print the duplicates
for (int i : arr2) {
if (set1.contains(i)) {
System.out.println(i); // print 10 20
}
}
}
I did the tests again... set and maps are indeed a lot faster then the loops
private static int size = 100000;
public static void main(String[] args) {
int[] array1 = new int[size];
int[] array2 = new int[size];
for (int i = 0; i < size; i++) {
array1[i] = i;
array2[i] = i + i;
}
System.out.println("starting set");
startTimer();
compareAgainstSet(array1, array2);
long set = stopTimer();
System.out.println("against set: " + set + "ms\n");
System.out.println("starting map");
startTimer();
compareAgainstMap(array1, array2);
long map = stopTimer();
System.out.println("against hashmap: " + map + "ms\n");
System.out.println("starting loops with break");
startTimer();
twoLoopsWithBreak(array1, array2);
long loopsBreak = stopTimer();
System.out.println("2 loops with break: " + loopsBreak + "ms\n");
System.out.println("starting loops without break");
startTimer();
twoLoopsWithoutBreak(array1, array2);
long loops = stopTimer();
System.out.println("2 loops without break: " + loops + "ms\n");
}
private static void twoLoopsWithoutBreak(int[] arr1, int[] arr2) {
ArrayList<Integer> doubles = new ArrayList<>();
for (int i : arr1) {
for (int j : arr2) {
if (i == j) {
doubles.add(i);
}
}
}
}
private static void twoLoopsWithBreak(int[] arr1, int[] arr2) {
ArrayList<Integer> doubles = new ArrayList<>();
for (int i : arr1) {
for (int j : arr2) {
if (i == j) {
doubles.add(i);
break;
}
}
}
}
private static void compareAgainstSet(int[] arr1, int[] arr2) {
ArrayList<Integer> doubles = new ArrayList<>();
Set<Integer> set1 = new HashSet<Integer>();
for (int i : arr1) {
set1.add(i);
}
for (int i : arr2) {
if (set1.contains(i)) {
doubles.add(i);
}
}
}
private static void compareAgainstMap(int[] arr1, int[] arr2) {
ArrayList<Integer> doubles = new ArrayList<>();
HashMap<Integer, Integer> hashmap = new HashMap<Integer, Integer>();
for (int i : arr1) {
hashmap.put(i, 0);
}
for (int i : arr2) {
if (hashmap.containsKey(i)) {
doubles.add(i);
}
}
}
private static long startTime;
private static void startTimer() {
startTime = System.currentTimeMillis();
}
private static long stopTimer() {
return System.currentTimeMillis() - startTime;
}
import java.util.*;
public class Duplicate {
public static void main(String[] args) {
// TODO Auto-generated method stub
int array1[]= {1,2,4,6,9,50,34};
int array2[]= {1,5,4,50,24,78,34};
HashSet<Integer> hashValue=new HashSet<>();
for(int i=0;i<array1.length;i++) {
hashValue.add(array1[i]);
}
for(int j=0;j<array2.length;j++) {
if(hashValue.contains(array2[j])) {
System.out.println("the duplicate value is "+array2[j]);
}
}
}
}
Your solution required O(n^2) time (assuming n is the length of the larger of the two arrays).
A better solution would be to sort the two arrays - O(n log(n))
and then find the duplicates in a single iteration over both sorted arrays - O(n).
The total running time would be O(n log(n)).
Why not just using array_intersect?
$a = array(1, 2, 5, 10, 15, 16);
$b = array(1, 4, 5, 6, 10, 13, 15, 19);
print_r(array_intersect($a, $b));
Whoops, I tought it was PHP, not JS...
Then: How do I get the intersection between two arrays as a new array?
If you don't want two for loops. Then you can use hashtable. Iterate the first array and insert to the hastable. When iterating the 2nd array to the hash table, check for the key, if present then it is duplicated else no.
With this approach, the time complexity will be getting reduced to O(kn) where k is a constant which is the number of arrays you have, but auxiliary space complexity will be increased.
