JAVA

Use the empty stub method to implement a faster alternative for the intersection algorithm.

public List intersectionFast(int[] a, int[] b)

Assume that each array has no duplicate values.

Steps for Completion

1. Assume that we have a way to sort the inputs in O(n log n). This is provided in the following method:

public void mergeSort(int[] input) {

Arrays.sort(input);

}

We can use this method to sort one input array, or both, and make the intersection easier.

2. To sort one input array, we can use a binary search on it. The runtime complexity is O(n log n) for the merge sort plus O(n log n) for the binary search per item in the first list. This is nlog+ nlog n which results in a final O(n log n).
3. Sort both arrays, and have two pointers, one for each array.
4. Go through the input arrays in a linear fashion.
5. Advance a pointer if the other pointer is pointing to a larger value.
6. If the values at both pointers are equal, both pointers are incremented. The runtime complexity for this algorithm is 2 (n log n) for the two merge sorts plus the n for the linear pass after the sorting. This results in 2 (n log n) + n with a final O(n log n)

TASKS

1. intersectionFast() returns the correct values for two different arrays.

2. intersectionFast() returns the intersection of two identical arrays.

3. intersectionFast() returns the correct intersection for two arrays which contain the same element multiple times.

4. intersectionFast() returns the properly value for two arrays that do not intersect.

Here is the code:

import java.util.Arrays;

import java.util.LinkedList;

import java.util.List;

public class SimpleIntersection {

private BinarySearch search = new BinarySearch();

public List intersection(int[] a, int[] b) {

List result = new LinkedList<>();

for (int x : a) {

for (int y : b) {

if (x == y) result.add(x);

}

}

return result;

}

public List intersectionFast(int[] a, int[] b) {

// Write your code here

return null;

}

public void mergeSort(int[] input) {

Arrays.sort(input);

}

public static void main(String[] args) {

Intersection inter = new Intersection();

System.out.println(inter.intersection(new int[]{4, 7, 5, 2, 3}, new int[]{4, 2, 3, 9, 1}));

System.out.println(inter.intersection(new int[]{4, 6, 11, 2, 3}, new int[]{5, 11, 3, 9, 1}));

// Write your code here

}

}