8
\$\begingroup\$

Challenge:

Print set intersections.

Specifications:

Your program should accept as its first argument a path to a filename.
Each line in the file is a test case.
Each test case contain two semicolon delimited sorted lists of numbers in ascending order, whose numbers are separated by a comma.

Print out the ascending order sorted intersection of the lists, one per line.
Print empty new line in case the lists have no intersection

Solution:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.LinkedHashSet;
import java.util.Scanner;
import java.util.Set;

public class SetIntersection {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner input = new Scanner(new File(args[0]));
        String[] parts;

        while (input.hasNextLine()) {
            parts = input.nextLine().split(";");

            System.out.println(
                findIntersection(
                    toIntArray(parts[0].split(",")),
                    toIntArray(parts[1].split(","))
                )
            );
        }
    }

    private static String findIntersection(int[] foo, int[] bar) {
        Set<Integer> intersection = new LinkedHashSet<>();

        for (int i = 0, j = 0; i < foo.length; i++) {
            while (foo[i] > bar[j] && j < bar.length) {
                j++;
            }
            if (foo[i] < bar[j]) {
                continue;
            } else {
                intersection.add(bar[j++]);
            }
        }

        if (intersection.isEmpty()) {
            return ""; // none found
        }

        String result = intersection.toString();
        return result.substring(1, result.length() - 1);
    }

    private static int[] toIntArray(String[] array) {
        int[] nums = new int[array.length];

        for (int i = 0; i < array.length; i++) {
            nums[i] = Integer.parseInt(array[i]);
        }

        return nums;
    }
}

Sample Input:

9,10,11;33,34,35
3,7,8,22;11,22
11,12,13,14;14,15,16
20,21,22;45,46,47
77,78,79;78,79,80,81,82
33,35;3,18,26,35

Sample Output:


22
14

78, 79
35

I wanted to take advantage of the fact the lists were sorted, but I fear my efforts only served to render my code convoluted and inefficient. What do you think?

\$\endgroup\$
  • \$\begingroup\$ Looking at this again the second part of the for loop should be i < foo.length && j < bar.length I added the while loop before posting, but I realized that's needed as well as an adjustment to my else otherwise there are cases where this will throw ArrayIndexOutOfBoundsException \$\endgroup\$ – Legato Feb 15 '15 at 20:08
6
\$\begingroup\$

This is a fine implementation. It's well-formatted and nicely written. I find the idea of using a LinkedHashSet quite clever and interesting. There are a couple of points to improve though.

You have a bug

Do you notice something fishy here?

while (foo[i] > bar[j] && j < bar.length) {
    j++;
}
if (foo[i] < bar[j]) {

The condition in the while checks foo[i] > bar[j] before j < bar.length. So when j reaches bar.length, this will throw an ArrayIndexOutOfBoundsException.

Flipping the && may seem like an obvious remedy. But it won't be enough, because of the next if statement after the while loop, you'll again have the problem if j has already reached bar.length.

An example input to demonstrate this issue: 33;3,4

Unit testing

It's always handy to have some unit tests around when solving challenges like this. For example:

@Test
public void test_9_10_11_x_33_34_35() {
    assertEquals("", findIntersection("9,10,11;33,34,35"));
}

@Test
public void test_3_7_8_22_x_11_22() {
    assertEquals("22", findIntersection("3,7,8,22;11,22"));
}

@Test
public void test_11_12_13_14_x_14_15_16() {
    assertEquals("14", findIntersection("11,12,13,14;14,15,16"));
}

@Test
public void test_20_21_22_x_45_46_47() {
    assertEquals("", findIntersection("20,21,22;45,46,47"));
}

@Test
public void test_77_78_79_x_78_79_80_81_82() {
    assertEquals("78,79", findIntersection("77,78,79;78,79,80,81,82"));
}

@Test
public void test_33_35_x_3_18_26_35() {
    assertEquals("35", findIntersection("33,35;3,18,26,35"));
}

@Test
public void test_33_x_3_4() {
    assertEquals("", findIntersection("33;3,4"));
}

An alternative implementation

Consider this alternative implementation that passes all the tests:

private String findIntersection(String input) {
    String[] parts = input.split(";");
    String[] arr1 = parts[0].split(",");
    String[] arr2 = parts[1].split(",");
    return findIntersection(arr1, arr2);
}

private String findIntersection(String[] arr1, String[] arr2) {
    StringBuilder builder = new StringBuilder();
    for (int pos1 = 0, pos2 = 0; pos1 < arr1.length && pos2 < arr2.length; ) {
        int value1 = Integer.parseInt(arr1[pos1]);
        int value2 = Integer.parseInt(arr2[pos2]);

        if (value1 == value2) {
            builder.append(value1).append(",");
            ++pos1;
            ++pos2;
        } else if (value1 < value2) {
            ++pos1;
        } else {
            ++pos2;
        }
    }
    if (builder.length() == 0) {
        return "";
    }
    return builder.substring(0, builder.length() - 1);
}

This implementation has an advantage and disadvantage compared to yours:

  • Advantages:

    • It doesn't always convert all input values to integers. For example when you have a long list and a short list, and it turns out that they cannot have an intersection, the rest of the long list will not be converted to integers
    • It should be faster to generate the output from a StringBuilder than from a LinkedHashSet
  • Disadvantage: in common cases it converts input values to numbers twice. This is because in every step of the while loop, when only one of the positions advance, then on the next step the other number will be converted to integer again.

There is possibly one more advantage: it's not clear if in the output the values should be separated by single commas, or by comma + space as in yours (and in the output of Set.toString). Since the values are separated by , in the input, I would assume the same rule for the output as well, but I could be wrong. But if I'm right, then to get the right output you would have to strip the spaces from the result of the Set.toString call.

\$\endgroup\$
  • 1
    \$\begingroup\$ Didn't realize I could leave the right part of the for loop empty, that certainly solves the issue. Coming up with unit tests and testing rigorously is a weakness I'll try to work on in the future. Thanks again. \$\endgroup\$ – Legato Feb 15 '15 at 21:33
  • \$\begingroup\$ What happened to parametrized tests? :) \$\endgroup\$ – Simon Forsberg Feb 15 '15 at 23:57
4
\$\begingroup\$

First of all, I have to say that the code formatting is very clean. It's been a long while since I read such well-formatted code. It's probably even cleaner than my own code, and definitely cleaner than my apartment.

It is good to take advantage of the specification that the inputs are sorted. Overall you have done so nicely, but I have a few comments.

int[] foo, int[] bar

Please, oh please, no such variable names! I would prefer input1 and input2 or something like that. foo and bar are names which is okay to use in example code, but not in actual code like this.

The choice of choosing a Set<Integer> to store the results is not that optimal when you want the end result as a String. Here I would definitely go for StringBuilder, which also saves you the handling of an edge-case. In fact, I believe your current handling of intersection.isEmpty() isn't necessary either, as an empty set will have the toString value {} which thanks to your substring call will be converted to an empty string.

StringBuilder result = new StringBuilder();
    ...
        if (result.length() > 0) {
            result.append(',');
        }
        result.append(bar[j++]);
    ...
return result.toString();

Also, this part can be simplified:

if (foo[i] < bar[j]) {
    continue;
} else {
    intersection.add(bar[j++]);
}

to:

if (foo[i] >= bar[j]) {
    intersection.add(bar[j++]);
}

Although you probably would want to check for == instead of >= there.

\$\endgroup\$
  • \$\begingroup\$ Although the challenge doesn't explicitly specify the possible their possible presence, I opted to use a LinkedHashSet over a StringBuilder to prevent printing duplicates. I see what you mean for the substring call equivalence, but isn't this method faster? As for foo and bar, I recently discovered why they were used all over the place and I think that tempted me, haha I won't repeat that again. \$\endgroup\$ – Legato Feb 15 '15 at 19:50
  • \$\begingroup\$ Really happy to hear that the code is clean and readable, that's largely a result of you and other fellow CRers, Simon. \$\endgroup\$ – Legato Feb 15 '15 at 20:13
  • \$\begingroup\$ @Legato The specification says that it's lists you are working with, I interpret that as that the intersection should be able to contain duplicates as well. If both lists have two instances of 24, then that's two duplicates. \$\endgroup\$ – Simon Forsberg Feb 15 '15 at 20:40
  • \$\begingroup\$ @SimonAndréForsberg the challenge is titled "Print set intersections", and the sample outputs don't have duplicates \$\endgroup\$ – janos Feb 15 '15 at 20:55
  • \$\begingroup\$ @janos That's a valid point. But just because the sample outputs don't have duplicates doesn't mean that they shouldn't be able to have. I guess both approaches are okay in this case. \$\endgroup\$ – Simon Forsberg Feb 15 '15 at 20:58
3
\$\begingroup\$

The following is more applicable assuming the exclusion of duplicates, which I note since as @SimonAndreForsberg says it isn't obvious, and none of the input tests used even include duplicates, so there's no way to know for sure.

Java Collection have a retainAll method. I hadn't used it before, but noticing its application to this problem led to:

  • Altering toIntArray to convert a string array toIntSet implementing LinkedHashSet to preserve order
  • Simply calling retainAll when finding intersection.

The result:

private static String findIntersection(Set<Integer> a, Set<Integer> b) {
        StringBuilder result = new StringBuilder();
        a.retainAll(b);

        for (int n : a) {
            result.append(',').append(n);
        }

        return result.length() == 0 ? "" : result.toString().substring(1);
    }

private static Set<Integer> toIntSet(String[] array) {
    Set<Integer> nums = new LinkedHashSet<>();

    for (int i = 0; i < array.length; i++) {
        nums.add(Integer.parseInt(array[i]));
    }

    return nums;
}

This suffers no edge-case bugs unlike the originally posted code, but what I realized is retainAll is painfully inefficient.

So, I began to redesign it accounting for the fact that numbers are sorted and I'm preserving such, but then @janos posted his answer, his answer coupled with the fact that none of the input cases contained negative integers led to this:

private static String findIntersection(String[] arr1, String[] arr2) {
    StringBuilder result = new StringBuilder();
    int val1 = Integer.parseInt(arr1[0]);
    int val2 = Integer.parseInt(arr2[0]);

    for (int i = 0, j = 0; val1 != -1 && val2 != -1; ) {

        if (val1 == val2) {
            result.append(',').append(val1);
            val1 = ++i < arr1.length ? Integer.parseInt(arr1[i]) : -1;
            val2 = ++j < arr2.length ? Integer.parseInt(arr2[j]) : -1;
        } else if (val1 < val2) {
            val1 = ++i < arr1.length ? Integer.parseInt(arr1[i]) : -1;
        } else {
            val2 = ++j < arr2.length ? Integer.parseInt(arr2[j]) : -1;
        }
    }

    return result.length() == 0 ? "" : result.substring(1);
}

Which foregoes the disadvantage of his suggestion. It's a unique case that allows this to work, but is applicable elsewhere for Objects and using null

\$\endgroup\$
  • \$\begingroup\$ Nice answer! +1 I'll try to find a cleaner way to overcome the disadvantage I mentioned, later tonight \$\endgroup\$ – janos Feb 16 '15 at 8:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.