Monday, September 29, 2014

Sets

Problem:

TopCoder Problem Statement - Sets

Overview:

Perform some basic Set operations and return the results.

Java Source:
01: import java.util.Arrays;
02: import java.util.HashSet;
03: import java.util.Set;
04: 
05: public class Sets {
06:  
07:  public int[] operate(int[] A, int[] B, String operation) {
08: 
09:         Set setA = new HashSet<>();
10:         Set setB = new HashSet<>();
11:         Set setC = new HashSet<>();
12: 
13:         for (int x : A)  {
14:             setA.add(x);
15:         }
16: 
17:         for (int x : B)  {
18:             setB.add(x);
19:         }
20: 
21:         if ("INTERSECTION".equals(operation)) {
22:             setC.addAll(setA);
23:             setC.retainAll(setB);
24: 
25:         } else if ("UNION".equals(operation))  {
26:             setC.addAll(setA);
27:             setC.addAll(setB);
28: 
29:         } else if ("SYMMETRIC DIFFERENCE".equals(operation))  {
30: 
31:             // setC contains the Union
32:             setC.addAll(setA);
33:             setC.addAll(setB);
34: 
35:             // SetD contains the Intersection
36:             Set setD = new HashSet<>();
37:             setD.addAll(setA);
38:             setD.retainAll(setB);
39: 
40:             // Remove the intersection from the union to get the symmetric diff.
41:             setC.removeAll(setD);
42:         }
43: 
44:         // Create the return array, sort it, and return it.
45:         int[] r = new int[setC.size()];
46: 
47:         int i = 0;
48:         for (Integer x : setC)  {
49:             r[i++] = x;
50:         }
51: 
52:         Arrays.sort(r);
53: 
54:         return r;
55:  }
56: }
Notes:

Another fairly easy Division 2 - Level 2 problem - if you use the language features to do all the work.

We'll use Java's HashSet to perform all of the operations. Lines 9 through 19 create the HashSets and load values into them. setC will hold our results. Then we'll use a combination of addAll(), retainAll(), and removeAll() depending on the type of operations. If you're not familiar with these operations, I encourage you to read up on them.

If the operation is INTERSECTION, then all all the elements from setA into our result setC. Then use retainAll() to keep only those elements that are also in setB.

UNION is the easiest. We just use addAll() to add the contents of setA and setB to setC. It doesn't matter if there are duplicates, Sets guarantee that no duplicates are stored.

For SYMMETRIC DIFFERENCE, we first populate setC as the union of setA and setB. The we create a new setD to hold the intersection of setA and setB. Finally, that intersection is removed from the union.

Lines 45 through 54 create the return array, populate it with the contents from setC, sort it, and return.

No comments:

Post a Comment