# Finding the intersection of elements in two sets

Is there another better way to implement those two methods in 1 and 2?

1. Implement the method contains. contains returns true if the given element is a member of the set, and false otherwise.

2. Implement the method intersection. intersection returns a set which contains the elements in the set that are also members of the given set

output:

{9, 1, 4, 3, 7, 5}

{4, 2, 8, 5, 7}

{4, 7, 5}


public class IntSet {

private int[] elements = null;

public IntSet(int[] elements) {
this.elements = new int[elements.length];
for (int pos = 0; pos < elements.length; pos++) {
this.elements[pos] = elements[pos];
}
}

// toString returns a string representation of the set
public String toString() {
String s = "{";
if (elements.length == 0)
s = s + "}";
else {
for (int pos = 0; pos < elements.length - 1; pos++)
s = s + elements[pos] + ", ";
s = s + elements[elements.length - 1] + "}";
}

return s;
}

// contains returns true if the given element
// is a member of the set, and false otherwise.
public boolean contains(int element) {

for (int i = 0; i < this.elements.length; i++) {
if (this.elements[i] == element)
return true;
}
return false;
}

// intersection returns a set which contains the elements
// in the set that are also members of the given set
public IntSet intersection(IntSet set) {
// use the method contains
int members = 0;
for (int i = 0; i < elements.length; i++) {
if (set.contains(elements[i]))
members++;
}

int[] newMembers = new int[members];
int position = 0;
for (int i = 0; i < elements.length; i++) {
if (set.contains(elements[i]))
newMembers[position++] = this.elements[i];

}
return new IntSet(newMembers);
}

//Some instances of the class IntSet are created and used like this:
public static void main(String[] args) {
int[] numbers1 = {9, 1, 4, 3, 7, 5};
IntSet set1 = new IntSet(numbers1);
int[] numbers2 = {4, 2, 8, 5, 7};
IntSet set2 = new IntSet(numbers2);
System.out.println(set1);
System.out.println(set2);

IntSet set = set1.intersection(set2);
System.out.println(set);
//When this code fragment is executed, the following printout is produced:
//{9, 1, 4, 3, 7, 5}
//{4, 2, 8, 5, 7}
//{4, 7, 5}
}
}

• Why not using Set in 1st place? – πάντα ῥεῖ Mar 28 '17 at 21:54
• In the task only two methods was asked to implement the other part of the code was giving within the task. So I'm open to learn if HashSet<Integer> Please share your knowledge I like to learn it. – Adam Mar 28 '17 at 23:00

public static void main(String[] args) {
int[] numbers1 = {9, 1, 4, 3, 7, 5};
IntSet set1 = new IntSet(numbers1);
int[] numbers2 = {4, 2, 8, 5, 7};
IntSet set2 = new IntSet(numbers2);
System.out.println(set1);
System.out.println(set2);

IntSet set = set1.intersection(set2);
System.out.println(set);
//When this code fragment is executed, the following printout is produced:
//{9, 1, 4, 3, 7, 5}
//{4, 2, 8, 5, 7}
//{4, 7, 5}
}


public static void main(String[] args) {
Integer[] numbers1 = {9, 1, 4, 3, 7, 5};
Set<Integer> set1 = new HashSet<Integer>(Arrays.asList(numbers1));
Integer[] numbers2 = {4, 2, 8, 5, 7};
Set<Integer> set2 = new HashSet<Integer>(Arrays.asList(numbers2));
System.out.println(Arrays.toString(numbers1));
System.out.println(Arrays.toString(numbers2));

Set<Integer> set = intersection(set1, set2);
System.out.println(Arrays.toString(set.toArray()));
//When this code fragment is executed, the following printout is produced:
//{9, 1, 4, 3, 7, 5}
//{4, 2, 8, 5, 7}
//{4, 7, 5}
}


This handles contains for you, as Set has a contains method.

Because this is a built-in data type, you don't have to reinvent it. And HashSet has constant time contains, add, and remove.

Then you just need to implement intersection.

public static Set<Integer> intersection(Set<Integer> a, Set<Integer> b) {
// unnecessary; just an optimization to iterate over the smaller set
if (a.size() > b.size()) {
return intersection(b, a);
}

Set<Integer> results = new HashSet<>();

for (Integer element : a) {
if (b.contains(element)) {
}
}

return results;
}


This will operate in linear time based on the size of the smaller set.

Is there another better way to implement those two methods in 1 and 2?

Of course there is.

My advice is to think about the problem as though you were solving the problem without a computer.

Here, I'm going to give you a list of a thousand unsorted integers between 0 and 999999.

Now I'm going to ask you one thousand times whether a particular number I've chosen at random is on the list.

Would you really try to answer every question by reading down the list from top to bottom every time?

Give some thought as to how you might solve that problem before you read on.

.

.

.

.

.

.

.

.

You probably thought something like

• the first time I go down the list, I could make ten smaller lists: numbers I've seen from 0-99999, numbers I've seen from 100000-199999, from 200000-299999, and so on. That will take a thousand steps to make ten buckets of roughly 100 items each.
• Then the second time I'm asked the question, I can first figure out what bucket the number might be in. Then I can search that bucket, and I know I will only have around 100 things to check instead of 1000.
• And hey, while I'm doing that, I might as well divide that bucket up into ten buckets of roughly ten items each!

Every time you do a search that makes ten more buckets, you make subsequent searches that hit that bucket ten times faster.

All right, that should get you started; can you implement something like this bucketing algorithm in code?

Now, think the same way about intersection. Can you use the same bucketing trick to make intersection vastly faster? Or something similar? Again, think about how you would solve the problem if I asked you to do it by hand.